Eulerov teorem

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

Isto tako, teorem je blisko povezan s tzv. Malim Fermatovim teoremom, stavljajući [math]\displaystyle{ n = p, }[/math] za neki prosti broj [math]\displaystyle{ p. }[/math]

Dokaz

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

Lema. Neka je [math]\displaystyle{ S }[/math] skup svih relativno prostih brojeva s [math]\displaystyle{ n }[/math] u intervalu [math]\displaystyle{ [1, n]. }[/math] Možemo pisati [math]\displaystyle{ S = \{k_1, k_2, ..., k_r\}. }[/math] Za skup [math]\displaystyle{ S }[/math] kažemo da je reducirani sustav ostataka modulo n.

Svi elementi skupa [math]\displaystyle{ S'= \{ak_1, ak_2, ..., ak_r\} }[/math] za [math]\displaystyle{ a \in \mathbb{N}, M(a, n) = 1 }[/math] su međusobno nekongruentni modulo [math]\displaystyle{ n }[/math] i daju ostatke kao elementi skupa [math]\displaystyle{ S, }[/math] pri dijeljenju s [math]\displaystyle{ n, }[/math] ali ne nužno u tom poretku.

Pretpostavimo da su neka dva elementa skupa [math]\displaystyle{ S' }[/math] kongruenta modulo [math]\displaystyle{ n, }[/math] odnosno [math]\displaystyle{ ak_i \equiv ak_j \pmod n }[/math] za [math]\displaystyle{ i \neq j. }[/math] Tada očito [math]\displaystyle{ n \mid a(k_i - k_j), }[/math] no [math]\displaystyle{ |k_i - k_j| \lt n, }[/math] što je kontradikcija.

Sada ćemo dokazati drugi dio leme. Očito su svi elementi skupa [math]\displaystyle{ S' }[/math] relativno prosti s [math]\displaystyle{ n. }[/math] Prema teoremu o dijeljenju s ostatkom možemo pisati [math]\displaystyle{ ak_i = qn + r, q, r \in \mathbb{N}, 0 \lt r \lt n }[/math] (*). Dokazujemo da mora vrijediti [math]\displaystyle{ M(n, r) = 1, }[/math] čime je tvrdnja zapravo dokazana. Pretpostavimo suprotno, [math]\displaystyle{ M(n, r) = d, d \gt 1. }[/math] Tada iz (*) slijedi [math]\displaystyle{ d \mid qn + r. }[/math] Onda očito [math]\displaystyle{ d \mid ak_i, }[/math] a vrijedi [math]\displaystyle{ M(k_i, n) = 1, \forall i = \{1, 2, ..., r\}, M(a, n) = 1. }[/math] Dakle, [math]\displaystyle{ d = 1, }[/math] čime je lema dokazana.

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

Koristeći ovu lemu nije teško dokazati Eulerov teorem. Označimo s [math]\displaystyle{ P = k_1 \cdot k_2 \cdot ... \cdot k_r. }[/math] Prema lemi, vrijedi bijekcija [math]\displaystyle{ ak_i \equiv k_j \pmod n. }[/math] Množeći svih [math]\displaystyle{ r }[/math] kongruencija dobivamo [math]\displaystyle{ a^r \cdot P \equiv P \pmod n. }[/math] Budući da je [math]\displaystyle{ M(n, P) = 1 }[/math] i [math]\displaystyle{ r = \varphi{(n)}, }[/math] slijedi [math]\displaystyle{ a^{\varphi{(n)}} \equiv 1 \pmod n, }[/math] što je i trebalo dokazati.

Kongruentnost relativno prostih brojeva

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

Neka je [math]\displaystyle{ S }[/math] skup svih relativno prostih brojeva s brojem [math]\displaystyle{ n }[/math] u intervalu [math]\displaystyle{ [1, n]. }[/math] Ako je [math]\displaystyle{ (a, n) = 1, }[/math] tada je [math]\displaystyle{ a \equiv x \pmod n, }[/math] gdje je [math]\displaystyle{ x \in S. }[/math]

(Uočimo da tada očigledno vrijedi i [math]\displaystyle{ n \equiv x' \pmod a, x' \in S' }[/math] gdje je [math]\displaystyle{ S' }[/math] skup svih relativno prostih brojeva s [math]\displaystyle{ a }[/math] u [math]\displaystyle{ [1, a]. }[/math])

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

Drugim riječima, broj [math]\displaystyle{ a }[/math] relativno prost s [math]\displaystyle{ n \gt 1 }[/math] daje ostatak, [math]\displaystyle{ a -kn, k \in \mathbb{Z} }[/math] pri dijeljenju s [math]\displaystyle{ n }[/math] koji je jedan od relativno prostih brojeva s [math]\displaystyle{ n }[/math] u [math]\displaystyle{ [1, n]. }[/math]

Primjeri

Od broja [math]\displaystyle{ a \gt n }[/math] oduzimat ćemo [math]\displaystyle{ n }[/math] onoliko puta dok ne dobijemo broj u intervalu [math]\displaystyle{ [0, n - 1) }[/math]. (Time bismo eventualno mogli dobiti 0, ali samo ako je [math]\displaystyle{ a }[/math] višekratnik od [math]\displaystyle{ n }[/math].)

Uzmimo [math]\displaystyle{ n = 30 }[/math], [math]\displaystyle{ a = 123 }[/math]. Očito je [math]\displaystyle{ (30, 123) = 3 }[/math] pa će biti [math]\displaystyle{ 123 \equiv 123 - 30 \equiv 123 - 2 \cdot 30 \pmod{30} }[/math] i tako sve do [math]\displaystyle{ 123 \equiv 3 \pmod {30} }[/math].

S druge strane, uzmimo [math]\displaystyle{ b = 127. }[/math] Očito je [math]\displaystyle{ (30, 127) = 1 }[/math] te vrijedi [math]\displaystyle{ 127 \equiv 127 - 4 \cdot 30 \pmod{30} }[/math] pa je zaista [math]\displaystyle{ 127 \equiv 7 \pmod {30} }[/math], a 7 i 30 su relativno prosti.

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

Slučaj kada je [math]\displaystyle{ a = p - 1 }[/math]

Brojevi [math]\displaystyle{ p - 1, p }[/math] su relativno prosti za svaki prosti broj [math]\displaystyle{ p }[/math]. Naime, pretpostavimo da [math]\displaystyle{ d|p, d|p - 1, d \gt 1 }[/math]. No, tada [math]\displaystyle{ d | p - (p - 1) = 1 }[/math], kontradikcija. (Ovo vrijedi za bilo koja dva uzastopna prirodna broja.)

Prema Eulerovom teoremu sada slijedi da je [math]\displaystyle{ {(p - 1)}^{p - 1} \equiv 1 \pmod p }[/math].