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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S=\{k_{1},k_{2},...,k_{r}\}.} Za skup $S$ kažemo da je reducirani sustav ostataka modulo n.

Svi elementi skupa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S'=\{ak_{1},ak_{2},...,ak_{r}\}} za Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a\in \mathbb {N} ,M(a,n)=1} su međusobno nekongruentni modulo $n$ i daju ostatke kao elementi skupa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S,} pri dijeljenju s $n,$ ali ne nužno u tom poretku.

Pretpostavimo da su neka dva elementa skupa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S'} kongruenta modulo $n,$ odnosno Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ak_{i}\equiv ak_{j}{\pmod {n}}} za Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i\neq j.} Tada očito $n\mid a(k_{i}-k_{j}),$ no Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |k_{i}-k_{j}|<n,} što je kontradikcija.

Sada ćemo dokazati drugi dio leme. Očito su svi elementi skupa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S'} relativno prosti s $n.$ Prema teoremu o dijeljenju s ostatkom možemo pisati Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ak_{i}=qn+r,q,r\in \mathbb {N} ,0<r<n} (*). Dokazujemo da mora vrijediti Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M(n,r)=1,} čime je tvrdnja zapravo dokazana. Pretpostavimo suprotno, $M(n,r)=d,d>1.$ Tada iz (*) slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle l} za koji je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M(n,l)=d>1} njegov će ostatak biti djeljiv s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a,n)=1,} tada je $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S'} skup svih relativno prostih brojeva s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $d|y,n$ iz posljednje jednadžbe slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a} relativno prost s $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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} , $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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}}} .