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 $d\mid ak_{i},$ a vrijedi $M(k_{i},n)=1,\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 $ak_{i}\equiv k_{j}{\pmod {n}}.$ Množeći svih $r$ kongruencija dobivamo $a^{r}\cdot P\equiv P{\pmod {n}}.$ Budući da je $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 $a\equiv x{\pmod {n}},$ gdje je $x\in S.$

(Uočimo da tada očigledno vrijedi i $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 $a\equiv y{\pmod {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{\pmod {30}}$ i tako sve do $123\equiv 3{\pmod {30}}$.

S druge strane, uzmimo $b=127.$ Očito je $(30,127)=1$ te vrijedi $127\equiv 127-4\cdot 30{\pmod {30}}$ pa je zaista $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 $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{\pmod {p}}$.