MetaMath '25 - Školjka

Vrijeme: 17:19

Mali Fermatov teorem

Dobrodošao u sedmi tjedan MetaMath tečaja! Ovotjedna tema je Mali Fermatov teorem i Eulerov teorem.

Za ovu temu potrebno je osnovno predznanje o modularnoj aritmetici, tj. kongruencijama. Ako se nikad nisi susreo/la s tim nazivom, preporučam da pogledaš ovo predavanje da se upoznaš s kongruencijama, pročitaš svojstva i proučiš nekoliko primjera jednostavnih zadataka.

Na početku ćemo kratkom intuitivnom opservacijom napraviti uvod u mali Fermatov teorem i pokazati njegovu primjenu na nekoliko malih primjera. Zatim ćemo uvesti pojam Eulerove funkcije i na kraju Eulerov teorem koji je ustvari generalizacija malog Fermatovog teorema.

Napomena: Zapis $a \equiv b \pmod n$ , koji uključuje znak $\equiv$ i zagrade oko mod, podrazumijeva kongruenciju modulo $n$ i takva se relacija razlikuje od jednakosti. Pored toga, zapis $a \bmod b$ predstavlja binarnu operaciju čiji je rezultat ostatak pri dijeljenju $a$ brojem $b$ , odnosno jedinstveni nenegativni cijeli broj $r \left(0 \le r < b\right)$ za koji vrijedi $r \equiv a \pmod b$ . Čitatelji upoznati s programiranjem prepoznat će $a\bmod b$ kao operaciju koja je u mnogim programskim jezicima definirana znakom %. Broj $n$ kojim radimo modulo operacije u literaturi se naziva modulus, stoga ću ga tako nazivati i u ovom predavanju.

Zašto uopće promatrati potencije? Kada potenciramo cijele brojeve modulo $n$ , postoji konačno mnogo mogućih rezultata, načelno zato što postoji konačno mnogo ostataka modulo $n$ , oni su od $0$ do $n-1$ . To znači da kad višestruko množiš istim brojem $a$ , niz ostataka će se eventualno ponavljati, tj. napravit će ciklus. Na primjer, modulo $7$ :
$3^1 \equiv 3$
$3^2 \equiv 9 \equiv 2$
$3^3 \equiv 2 \cdot 3 \equiv 6$
$3^4 \equiv 6 \cdot 3 \equiv 18 \equiv 4$
$3^5 \equiv 4 \cdot 3 \equiv 12 \equiv 5$
$3^6 \equiv 5 \cdot 3 \equiv 15 \equiv 1$

Ostatci se ciklički vraćaju na $1$ na šestoj potenciji. Ovo nije slučajnost: kada je modulus $p$ prost broj ( $p = 7$ u našem primjeru), a broj kojeg množimo relativno prost s njim, nikada nećemo pogoditi nulu, jer ne možemo množenjem dva broja relativno prosta s $p$ dobiti broj koji je djeljiv s $p$ . U igri su samo ostatci $1, 2, \ldots, p-1$ - ima ih točno $p-1$ , a ponavljano množenje istim brojem (kao što je u primjeru prikazano s $3$ ) samo se "prebacujemo" s jednog od njih na drugi. Nakon $p-1$ množenja je očekivano da će ciklus tada završiti. Ovo je srž malog Fermatovog teorema. Međutim, to ne znači da se jedinica nužno neće pojaviti i ranije. Na primjer, u potencijama broja $2$ modulo $7$ ostatci će biti redom $2, 4, 1, 2, 4, 1$ . Jedino što je važno je da je na šestom ( $6 = 7-1$ ) mjestu jedinica, a u slučaju da postoje manji ciklusi, kao što je ovdje $2, 4, 1$ , njihova duljina uvijek će biti djelitelj duljine cijelog ciklusa, logično, jer se cijeli ciklus sastoji od nekog broja manjih ciklusa.

Mali Fermatov teorem
Neka je $a$ cijeli broj, a $p$ prost broj. Ako su $a$ i $p$ relativno prosti, tj. $\gcd(a, p)=1$ , onda je $a^{p-1} \equiv 1 \pmod p$

Ideja dokaza:
U dokazu je ključna činjenica da skupovi brojeva $\{1, 2, 3, \ldots, p-1\}$ i $\{a, 2a, 3a, \ldots, (p-1)a\}$ imaju iste ostatke modulo $p$

Dokaz
Promotrimo prvih $p-1$ višekratnika broja $a$ : $a, 2a, 3a, \dots, (p-1)a$ . Pokažimo prvo da su svi oni različiti modulo $p$ . Naime, pretpostavimo da su neka dva ista: $ia \equiv ja \pmod p$ za neke $i, j \left(1 \le i, j \le p-1\right)$ . Ta kongruencija ekvivalentna je $a\left(i-j\right) \equiv 0 \pmod p$ . Budući da je $\gcd(a,p)=1$ , jedino je moguće da $p$ dijeli $i-j$ , odnosno $i-j = kp$ za neki $k$ . Ali, $i$ i $j$ nalaze se između $1$ i $p-1$ , zato $i-j$ ne može biti nijedan višekratnik broja $p$ osim nule, stoga je $i=j$ .
Dobili smo da $p-1$ brojeva $a, 2a, 3a, \dots, (p-1)a$ daje različite ostatke modulo $p$ , a dodatno nijedan od tih ostataka nije nula, zaključimo da su ti ostatci upravo $1, 2, 3, \dots, p-1$ u nekom poretku.
Sada možemo zapisati ovu kongruenciju: $a \cdot 2a \cdot 3a \cdot \ldots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \pmod p$ $a^{p-1} (p-1)! \equiv (p-1)! \pmod p$ Vrijedi $\gcd\left(p, (p-1)!\right) = 1$ , dakle, možemo "skratiti" $(p-1)!$ s obje strane kongruencije, pa konačno imamo $a^{p-1} \equiv 1 \pmod p$

Za prost broj $p$ i bilo koji cijeli broj $a$ , uključujući i višekratnike od $p$ , vrjedi $a^p \equiv a \pmod p$

Rješenje ovog zadatka je prvo slovo svake riječi u imenu ovog teorema, sve velika slova bez razmaka (što je popularna skraćenica za ime ovog teorema).

Oprez! Ne vrijedi obrat malog Fermatovog teorema! Ako su $a$ i $n$ relativno prosti takvi da je $a^{n-1} \equiv 1 \pmod n$ , iz toga ne slijedi da je $n$ prost broj. Na primjer, uzmimo $a=7$ i $n=25$ . Vrijedi $\gcd(7,25) = 1$ i $7^{24} \equiv 1 \pmod{25}$ (ovo zahtijeva malo računanja), ali $25 = 5\cdot5$ je složen broj.

Fun fact: S druge strane, ako imamo broj $x$ koji ne znamo je li prost ili složen, te odaberemo neki $a$ njemu relativno prost, računanjem $a^{x-1}$ modulo $x$ , ako rezultat nije $1$ , zaključili smo da $x$ nije prost broj iako ne znamo ništa o njegovim faktorima! Ovo se naziva test prostosti i specifično ovaj je u praksi vrlo slab, neki brojevi (npr. $1729$ ) daju $1$ za sve kandidate $a$ .

Dobrodošao u sedmi tjedan MetaMath tečaja! Ovotjedna tema je Mali Fermatov teorem i Eulerov teorem. Za ovu temu potrebno je osnovno predznanje o modularnoj aritmetici, tj. kongruencijama. Ako se nikad nisi susreo/la s tim nazivom, preporučam da pogledaš \href{https://umo.mathos.unios.hr/wp-content/uploads/2022/11/Osijek_2022_2023__J2.pdf}{ovo predavanje} da se upoznaš s kongruencijama, pročitaš svojstva i proučiš nekoliko primjera jednostavnih zadataka. Na početku ćemo kratkom intuitivnom opservacijom napraviti uvod u mali Fermatov teorem i pokazati njegovu primjenu na nekoliko malih primjera. Zatim ćemo uvesti pojam Eulerove funkcije i na kraju Eulerov teorem koji je ustvari generalizacija malog Fermatovog teorema. [quote]Napomena: Zapis $a \equiv b \pmod n$, koji uključuje znak $\equiv$ i zagrade oko mod, podrazumijeva kongruenciju modulo $n$ i takva se relacija razlikuje od jednakosti. Pored toga, zapis $a \bmod b$ predstavlja binarnu operaciju čiji je rezultat ostatak pri dijeljenju $a$ brojem $b$, odnosno jedinstveni nenegativni cijeli broj $r \left(0 \le r < b\right)$ za koji vrijedi $r \equiv a \pmod b$. Čitatelji upoznati s programiranjem prepoznat će $a\bmod b$ kao operaciju koja je u mnogim programskim jezicima definirana znakom \%. Broj $n$ kojim radimo modulo operacije u literaturi se naziva \textit{modulus}, stoga ću ga tako nazivati i u ovom predavanju.[/quote] \\ Zašto uopće promatrati potencije? Kada potenciramo cijele brojeve modulo $n$, postoji konačno mnogo mogućih rezultata, načelno zato što postoji konačno mnogo ostataka modulo $n$, oni su od $0$ do $n-1$. To znači da kad višestruko množiš istim brojem $a$, niz ostataka će se eventualno ponavljati, tj. napravit će \textit{ciklus}. Na primjer, modulo $7$: \\ $3^1 \equiv 3$ \\ $3^2 \equiv 9 \equiv 2$ \\ $3^3 \equiv 2 \cdot 3 \equiv 6$ \\ $3^4 \equiv 6 \cdot 3 \equiv 18 \equiv 4$ \\ $3^5 \equiv 4 \cdot 3 \equiv 12 \equiv 5$ \\ $3^6 \equiv 5 \cdot 3 \equiv 15 \equiv 1$ Ostatci se ciklički vraćaju na $1$ na šestoj potenciji. Ovo nije slučajnost: kada je modulus $p$ prost broj ($p = 7$ u našem primjeru), a broj kojeg množimo relativno prost s njim, nikada nećemo pogoditi nulu, jer ne možemo množenjem dva broja relativno prosta s $p$ dobiti broj koji je djeljiv s $p$. U igri su samo ostatci $1, 2, \ldots, p-1$ - ima ih točno $p-1$, a ponavljano množenje istim brojem (kao što je u primjeru prikazano s $3$) samo se "prebacujemo" s jednog od njih na drugi. Nakon $p-1$ množenja je očekivano da će ciklus tada završiti. Ovo je srž malog Fermatovog teorema. Međutim, to ne znači da se jedinica nužno neće pojaviti i ranije. Na primjer, u potencijama broja $2$ modulo $7$ ostatci će biti redom $2, 4, 1, 2, 4, 1$. Jedino što je važno je da je na šestom ($6 = 7-1$) mjestu jedinica, a u slučaju da postoje manji ciklusi, kao što je ovdje $2, 4, 1$, njihova duljina uvijek će biti djelitelj duljine cijelog ciklusa, logično, jer se cijeli ciklus sastoji od nekog broja manjih ciklusa. [quote] [b]Mali Fermatov teorem[/b] \\ Neka je $a$ cijeli broj, a $p$ prost broj. Ako su $a$ i $p$ relativno prosti, tj. $\gcd(a, p)=1$, onda je $a^{p-1} \equiv 1 \pmod p$ [b]Ideja dokaza:[/b] \\ U dokazu je ključna činjenica da skupovi brojeva $\{1, 2, 3, \ldots, p-1\}$ i $\{a, 2a, 3a, \ldots, (p-1)a\}$ imaju iste ostatke modulo $p$ [b]Dokaz[/b] \\ Promotrimo prvih $p-1$ višekratnika broja $a$: $a, 2a, 3a, \dots, (p-1)a$. Pokažimo prvo da su svi oni različiti modulo $p$. Naime, pretpostavimo da su neka dva ista: $ia \equiv ja \pmod p$ za neke $i, j \left(1 \le i, j \le p-1\right)$. Ta kongruencija ekvivalentna je $a\left(i-j\right) \equiv 0 \pmod p$. Budući da je $\gcd(a,p)=1$, jedino je moguće da $p$ dijeli $i-j$, odnosno $i-j = kp$ za neki $k$. Ali, $i$ i $j$ nalaze se između $1$ i $p-1$, zato $i-j$ ne može biti nijedan višekratnik broja $p$ osim nule, stoga je $i=j$. \\ Dobili smo da $p-1$ brojeva $a, 2a, 3a, \dots, (p-1)a$ daje različite ostatke modulo $p$, a dodatno nijedan od tih ostataka nije nula, zaključimo da su ti ostatci upravo $1, 2, 3, \dots, p-1$ u nekom poretku. \\ Sada možemo zapisati ovu kongruenciju: $$a \cdot 2a \cdot 3a \cdot \ldots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \pmod p$$ $$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$$ Vrijedi $\gcd\left(p, (p-1)!\right) = 1$, dakle, %postoji inverz broja $(p-1)!$ modulo $p$ pa ga možemo skratiti. možemo "skratiti" $(p-1)!$ s obje strane kongruencije, pa konačno imamo $$a^{p-1} \equiv 1 \pmod p$$ [/quote] [quote] Za prost broj $p$ i bilo koji cijeli broj $a$, uključujući i višekratnike od $p$, vrjedi $a^p \equiv a \pmod p$ [/quote] Rješenje ovog zadatka je prvo slovo svake riječi u imenu ovog teorema, sve velika slova bez razmaka (što je popularna skraćenica za ime ovog teorema). [quote] [b]Oprez![/b] Ne vrijedi obrat malog Fermatovog teorema! Ako su $a$ i $n$ relativno prosti takvi da je $a^{n-1} \equiv 1 \pmod n$, iz toga ne slijedi da je $n$ prost broj. Na primjer, uzmimo $a=7$ i $n=25$. Vrijedi $\gcd(7,25) = 1$ i $7^{24} \equiv 1 \pmod{25}$ (ovo zahtijeva malo računanja), ali $25 = 5\cdot5$ je složen broj. [/quote] [quote] Fun fact: S druge strane, ako imamo broj $x$ koji ne znamo je li prost ili složen, te odaberemo neki $a$ njemu relativno prost, računanjem $a^{x-1}$ modulo $x$, ako rezultat nije $1$, zaključili smo da $x$ nije prost broj iako ne znamo ništa o njegovim faktorima! Ovo se naziva \textit{test prostosti} i specifično ovaj je u praksi vrlo slab, neki brojevi (npr. $1729$) daju $1$ za sve kandidate $a$. [/quote]