Eulerov teorem

Eulerov teorem je jedan od najvažnijih teorema u elementarnoj teoriji brojeva, a tvrdi da je $a^{\varphi {(n)}}\equiv 1{\pmod {n}},$ gdje je $\varphi {(n)}$ Eulerova funkcija, odnosno funkcija koja svakom prirodnom broju pridružuje broj prirodnih brojeva koji su manji ili jednaki s $n$ i relativno prosti s $n.$

Isto tako, teorem je blisko povezan s tzv. Malim Fermatovim teoremom, stavljajući $n=p,$ za neki prosti broj $p.$

Dokaz

Prije samog dokaza iskazat ćemo i dokazati sljedeću lemu.

Lema. Neka je $S$ skup svih relativno prostih brojeva s $n$ u intervalu $[1,n].$ Možemo pisati $S=\{k_{1},k_{2},...,k_{r}\}.$ Za skup $S$ kažemo da je reducirani sustav ostataka modulo n.

Svi elementi skupa $S'=\{ak_{1},ak_{2},...,ak_{r}\}$ za $a\in \mathbb {N} ,M(a,n)=1$ su međusobno nekongruentni modulo $n$ i daju ostatke kao elementi skupa $S,$ pri dijeljenju s $n,$ ali ne nužno u tom poretku.

Pretpostavimo da su neka dva elementa skupa $S'$ kongruenta modulo $n,$ odnosno $ak_{i}\equiv ak_{j}{\pmod {n}}$ za $i\neq j.$ Tada očito $n\mid a(k_{i}-k_{j}),$ no $|k_{i}-k_{j}|<n,$ što je kontradikcija.

Sada ćemo dokazati drugi dio leme. Očito su svi elementi skupa $S'$ relativno prosti s $n.$ Prema teoremu o dijeljenju s ostatkom možemo pisati $ak_{i}=qn+r,q,r\in \mathbb {N} ,0<r<n$ (*). Dokazujemo da mora vrijediti $M(n,r)=1,$ čime je tvrdnja zapravo dokazana. Pretpostavimo suprotno, $M(n,r)=d,d>1.$ Tada iz (*) slijedi $d\mid qn+r.$ Onda očito Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d\mid ak_{i},} a vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M(k_{i},n)=1,\forall i=\{1,2,...,r\},M(a,n)=1.} Dakle, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d=1,} čime je lema dokazana.

Uočimo da ako prirodan broj $m$ daje neki od ostataka iz skupa relativno prostih brojeva s $n$ u intervalu $[1,n]$ on nužno mora biti relativno prost s $n.$ Naime, pomnožimo li bilo koji broj s $l$ za koji je $M(n,l)=d>1$ njegov će ostatak biti djeljiv s $d$ modulo $n.$

Koristeći ovu lemu nije teško dokazati Eulerov teorem. Označimo s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P=k_{1}\cdot k_{2}\cdot ...\cdot k_{r}.} Prema lemi, vrijedi bijekcija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ak_{i}\equiv k_{j}{\pmod {n}}.} Množeći svih Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r} kongruencija dobivamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a^{r}\cdot P\equiv P{\pmod {n}}.} Budući da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M(n,P)=1} i $r=\varphi {(n)},$ slijedi $a^{\varphi {(n)}}\equiv 1{\pmod {n}},$ što je i trebalo dokazati.

Kongruentnost relativno prostih brojeva

Iskazat ćemo i dokazati jedno jednostavno, ali važno svojstvo relativno prostih brojeva.

Neka je $S$ skup svih relativno prostih brojeva s brojem $n$ u intervalu $[1,n].$ Ako je $(a,n)=1,$ tada je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a\equiv x{\pmod {n}},} gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\in S.}

(Uočimo da tada očigledno vrijedi i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\equiv x'{\pmod {a}},x'\in S'} gdje je $S'$ skup svih relativno prostih brojeva s $a$ u $[1,a].$)

Dokaz. Pretpostavimo suprotno, tj. da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a\equiv y{\pmod {n}},(y,n)=d>1} uz Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y\in \{1,2,...,n-1\}.} No, onda očito (prema Teoremu o dijeljenju s ostatkom) postoji $q\in \mathbb {N}$ takav da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a=qn+y.} Kako Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d|y,n} iz posljednje jednadžbe slijedi $d|a,$ što povlači Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d=1.} Uočimo da su onda i brojevi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ...,a+n,a,...,y,y-n,...} svi redom relativno prosti s $n.$

Drugim riječima, broj $a$ relativno prost s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n>1} daje ostatak, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a-kn,k\in \mathbb {Z} } pri dijeljenju s $n$ koji je jedan od relativno prostih brojeva s $n$ u $[1,n].$

Primjeri

Od broja $a>n$ oduzimat ćemo $n$ onoliko puta dok ne dobijemo broj u intervalu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [0,n-1)} . (Time bismo eventualno mogli dobiti 0, ali samo ako je $a$ višekratnik od $n$.)

Uzmimo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=30} , Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a=123} . Očito je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (30,123)=3} pa će biti $123\equiv 123-30\equiv 123-2\cdot 30{\pmod {30}}$ i tako sve do Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 123\equiv 3{\pmod {30}}} .

S druge strane, uzmimo $b=127.$ Očito je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (30,127)=1} te vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 127\equiv 127-4\cdot 30{\pmod {30}}} pa je zaista Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 127\equiv 7{\pmod {30}}} , a 7 i 30 su relativno prosti.

Uočimo da se ovo lako vidi iz Euklidova algoritma.

Slučaj kada je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a=p-1}

Brojevi $p-1,p$ su relativno prosti za svaki prosti broj $p$. Naime, pretpostavimo da Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d|p,d|p-1,d>1} . No, tada $d|p-(p-1)=1$, kontradikcija. (Ovo vrijedi za bilo koja dva uzastopna prirodna broja.)

Prema Eulerovom teoremu sada slijedi da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {(p-1)}^{p-1}\equiv 1{\pmod {p}}} .