Matematyka.pl

Udowodnić, że jeśli liczba \(\displaystyle{ n> 1}\) jest bezkwadratową, to istnieje liczba pierwsza \(\displaystyle{ p}\) oraz liczba całkowita \(\displaystyle{ m}\) takie, iż \(\displaystyle{ p}\) dzieli \(\displaystyle{ n}\) oraz \(\displaystyle{ n}\) dzieli \(\displaystyle{ p^2+ pm^p}\).

pokaże to w przypadku gdy:

\(\displaystyle{ n=pq}\) - to liczby pierwsze

wtedy powinno być:

\(\displaystyle{ n=pq | p^2+pm^p}\)

lub:

\(\displaystyle{ n=pq | q^2+qm^q}\)

można też inaczej to zapisać:

\(\displaystyle{ p+m^p=0 \mod q \vee q+m^q=0 \mod p }\)

wystarczy wykazać, że któraś kongurencja jest rozwiązywalna...

można jeszcze inaczej zapisać:

(*) \(\displaystyle{ m^p=-p \mod q \vee m^q=-q \mod p }\)

z teorii kongurencji wiemy, że równanie:

\(\displaystyle{ x^a=-a \mod p}\)

ma rozwiązanie, jeżeli:

\(\displaystyle{ (-a)^{ \frac{p-1}{(a , p-1)} }=1 \mod p}\)

gdzie:

\(\displaystyle{ (a , p-1)}\) to NWD

wracając do (*) mamy:

\(\displaystyle{ (-p)^{ \frac{q-1}{(p , q-1)} }=1 \mod q}\)

lub:

\(\displaystyle{ (-q)^{ \frac{p-1}{(q , p-1)} }=1 \mod p}\)

ale wiemy skoro n liczba bezkwadratowa, że:

\(\displaystyle{ p<q}\)

na pewno będzie:

\(\displaystyle{ (q , p-1)=1}\)

więc:

\(\displaystyle{ (-q)^{ \frac{p-1}{(q , p-1)} }=(-q)^{p-1}=1 \mod p}\) to ostatnie z małego Fermata....


więc znaczy, że jest rozwiązanie, więc jest i podzielność cnd...

dla większej ilości iloczynu liczb pierwszych dla: \(\displaystyle{ n=p \cdot ... \cdot q}\)

powinno być podobnie...