MetaMath '25

[quote] [b]Eulerov teorem[/b]\\ Ako su $a$ i $n$ relativno prosti brojevi, tada vrijedi $a^{\varphi(n)} \equiv 1 \pmod n$ [b]Ideja dokaza[/b]\\ Analogija s malim Fermatovim teoremom, samo što promatramo reducirani skup ostataka $\{1, 2, 3, \ldots, n-1\}$ [b]Dokaz[/b]\\ Neka su $r_1, r_2, \ldots, r_{\varphi(n)}$ svi brojevi manji od $n$ i relativno prosti s $n$. Primjerice, za $n=12$, to su $1, 5, 7, 11$. Kao i u dokazu malog Fermata, množenje svakog broja nekim brojem $a$ ($\gcd(a,n)=1$) modulo $n$ samo će permutirati te brojeve, tj. tvrdimo da su brojevi $$ar_1, ar_2, \ldots, ar_{\varphi(n)}$$ također svi različiti modulo $n$ i svaki je relativno prost s $n$. Dokaz da su različiti: ako je $ar_i \equiv ar_j \pmod n$, tada je $a(r_i-r_j) \equiv 0 \pmod n$. Budući da je $\gcd(a,n)=1$, slijedi $r_i \equiv r_j \pmod n$, pa $i = j$. Dokaz da su relativno prosti: vrijedi $\gcd(a,n)=1$ i $\gcd(r_i,n)=1$, stoga je sigurno i $\gcd(ar_i, n)=1$, jer nije moguće da množenjem dva broja relativno prosta s $n$ dobijemo umnožak koji nije relativno prost s $n$. Dakle, skup $\{ar_1, ar_2, \ldots, ar_{\varphi(n)}\}$ je isti skup kao i $\{r_1, r_2, \ldots, r_{\varphi(n)}\}$ kada elemente promatramo modulo $n$. Nastavljamo kao i u dokazu MFT: $$(ar_1)\cdot(ar_2)\cdot\ldots\cdot(ar_{\varphi(n)}) \equiv r_1\cdot r_2 \cdot \ldots \cdot r_{\varphi(n)} \pmod n$$ Lijeva strana je $a^{\varphi(n)} \cdot \left(r_1\cdot r_2 \cdot \ldots \cdot r_{\varphi(n)}\right)$, a kako su svi $r_i$ relativno prosti s $n$, tako je i njihov umnožak, pa ga možemo skratiti s obje strane da dobijemo $$a^{\varphi(n)} \equiv 1 \pmod n$$ što je trebalo dokazati. [/quote] \\ Za pojednostavljivanje velikih potencija korisna je sljedeća lema čiji je dokaz ostavljen tebi kao zadatak. [quote] [b]Lema:[/b] Za relativno proste $a$ i $n$ vrijedi $a^b \equiv a^{b\bmod\varphi(n)} \pmod n$ [/quote] \\ Kao rješenje ovog zadatka izračunaj pa upiši $\gcd(10, 36)$.