Eulerov teorem

Eulerov teorem je jedan od najvažnijih teorema u elementarnoj teoriji brojeva, a tvrdi da je $a^{\phi (n)}\equiv 1(\mathrm{mod}n),$ gdje je s $\phi (n)$ označena 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^{\prime }=\{a{k}_1,a{k}_2,...,a{k}_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^{\prime }$ kongruenta modulo $n,$ odnosno $a{k}_i\equiv a{k}_j(\mathrm{mod}n)$ za $i\ne 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^{\prime }$ relativno prosti s $n.$ Prema teoremu o dijeljenju s ostatkom možemo pisati $a{k}_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 $d\mid a{k}_i,$ a vrijedi $M(k_i,n)=1,\mathrm{\forall }i=\{1,2,...,r\},M(a,n)=1.$ Dakle, $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 $P=k_1\cdot k_2\cdot ...\cdot k_r.$ Prema lemi, vrijedi bijekcija $a{k}_i\equiv k_j(\mathrm{mod}n).$ Množeći svih $r$ kongruencija dobivamo $a^r\cdot P\equiv P(\mathrm{mod}n).$ Budući da je $M(n,P)=1$ i $r=\phi (n),$ slijedi $a^{\phi (n)}\equiv 1(\mathrm{mod}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 $a\equiv x(\mathrm{mod}n),$ gdje je $x\in S.$

(Uočimo da tada očigledno vrijedi i $n\equiv x^{\prime }(\mathrm{mod}a),x^{\prime }\in S^{\prime }$ gdje je $S^{\prime }$ skup svih relativno prostih brojeva s $a$ u $[1,a].$)

Dokaz. Pretpostavimo suprotno, tj. da je $a\equiv y(\mathrm{mod}n),(y,n)=d>1$ uz $y\in \{1,2,...,n-1\}.$ No, onda očito (prema Teoremu o dijeljenju s ostatkom) postoji $q\in \mathbb{N}$ takav da je $a=qn+y.$ Kako $d|y,n$ iz posljednje jednadžbe slijedi $d|a,$ što povlači $d=1.$ Uočimo da su onda i brojevi $...,a+n,a,...,y,y-n,...$ svi redom relativno prosti s $n.$

Drugim riječima, broj $a$ relativno prost s $n>1$ daje ostatak, $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 $[0,n-1)$. (Time bismo eventualno mogli dobiti 0, ali samo ako je $a$ višekratnik od $n$.)

Uzmimo $n=30$, $a=123$. Očito je $(30,123)=3$ pa će biti $123\equiv 123-30\equiv 123-2\cdot 30(\mathrm{mod}30)$ i tako sve do $123\equiv 3(\mathrm{mod}30)$.

S druge strane, uzmimo $b=127.$ Očito je $(30,127)=1$ te vrijedi $127\equiv 127-4\cdot 30(\mathrm{mod}30)$ pa je zaista $127\equiv 7(\mathrm{mod}30)$, a 7 i 30 su relativno prosti.

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

Slučaj kada je $a=p-1$

Brojevi $p-1,p$ su relativno prosti za svaki prosti broj $p$. Naime, pretpostavimo da $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 ${(p-1)}^{p-1}\equiv 1(\mathrm{mod}p)$.