WikiSysop: Bot: Automatski unos stranica

2021-12-09T17:13:17Z

Bot: Automatski unos stranica

Nova stranica

'''Eulerov teorem''' je jedan od najvažnijih [[teorem]]a u elementarnoj [[Teorija brojeva|teoriji brojeva]], a tvrdi da je <math> a^{\varphi{(n)}} \equiv 1 \pmod n, </math> gdje je <math> \varphi{(n)} </math> [[Eulerova funkcija]], odnosno funkcija koja svakom [[Prirodni broj|prirodnom broju]] pridružuje broj prirodnih brojeva koji su manji ili jednaki s <math> n </math> i [[Prosti broj|relativno prosti]] s <math> n.</math><ref>{{Citiranje knjige|title=Uvod u teoriju brojeva|author=Andrej Dujella|authorlink=Andrej Dujella|date=2008.|url=https://web.archive.org/web/20210407155741/https://www.mathos.unios.hr/images/homepages/mirela/UUTB/utblink.pdf|format=PDF|publisher=Prirodoslovno-matematički fakultet|location=Zagreb}}</ref>

Isto tako, teorem je blisko povezan s tzv. ''Malim [[Pierre de Fermat|Fermat]]ovim teoremom'', stavljajući <math> n = p, </math> za neki prosti broj <math> p. </math>

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

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

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

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

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

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

Koristeći ovu lemu nije teško dokazati Eulerov teorem. Označimo s <math> P = k_1 \cdot k_2 \cdot ... \cdot k_r. </math> Prema lemi, vrijedi bijekcija <math> ak_i \equiv k_j \pmod n. </math> Množeći svih <math> r </math> kongruencija dobivamo <math> a^r \cdot P \equiv P \pmod n. </math> Budući da je <math> M(n, P) = 1 </math> i <math> r = \varphi{(n)}, </math> slijedi <math> 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> S </math> skup svih relativno prostih brojeva s brojem
<math> n </math> u intervalu <math> [1, n]. </math> Ako je <math> (a, n) = 1, </math>
tada je <math> a \equiv x \pmod n, </math> gdje je <math> x \in S. </math>

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

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

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

==== Primjeri ====
Od broja <math>a > n</math> oduzimat ćemo <math>n</math> onoliko puta dok ne dobijemo broj u intervalu <math>[0, n - 1)</math>. (Time bismo eventualno mogli dobiti 0, ali samo ako je <math>a</math> višekratnik od <math>n</math>.)

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

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

Uočimo da se ovo lako vidi iz [[Euklidov algoritam|Euklidova algoritma]].

=== Slučaj kada je <math> a = p - 1 </math> ===
Brojevi <math>p - 1, p</math> su relativno prosti za svaki prosti broj <math>p</math>. Naime, pretpostavimo da <math>d|p, d|p - 1, d > 1</math>. No, tada <math>d | p - (p - 1) = 1 </math>, kontradikcija. (Ovo vrijedi za bilo koja dva uzastopna prirodna broja.)

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

==Izvori==
{{izvori}}

[[Kategorija:Teorija brojeva]]

Eulerov teorem - Povijest promjena

WikiSysop: Bot: Automatski unos stranica