MetaMath '25

[b]Primjer 4.[/b]\\ Dokaži da $51 \mid 10^{32n+9} - 7$ za svaki prirodni $n$. [b]Rješenje:[/b]\\ Moramo pokazati da je $10^{32n+9} \equiv 7 \pmod{51}$. Imamo $\varphi(51) = 32$ i $\gcd(10,51)=1$ pa je po Eulerovom teoremu $10^{32} \equiv 1 \pmod{51}$, a potenciranjem te kongruencije slijedi $10^{32n} \equiv 1 \pmod{51} \Longleftrightarrow 10^{32n+9} \equiv 10^9 \pmod{51}$. Preostaje pokazati da je $10^9 \equiv 7 \pmod{51}$. Počevši od $10^2 = 100 \equiv -2 \Longleftrightarrow 10^8 \equiv 16 \pmod{51}$, stoga je $10^9 \equiv 160 = 3\cdot51 + 7 \equiv 7 \pmod{51}$. \\ \\ [b]Primjer 5.[/b]\\ Odredi zadnje dvije znamenke broja $3^{3^{3^3}}$. [b]Ideja rješenja.[/b]\\ Koristimo ranije spomenutu lemu jer je ovdje eksponent jako velik. [b]Rješenje:[/b]\\ Zadnje dvije znamenke znači odredimo kongruenciju modulo $100$. $3^{3^{3^3}} \equiv 3^{\left(3^{3^3}\bmod \varphi(100)\right)} \pmod {100}$ Imamo $\varphi(100) = 40$ i sada nas zanima $3^{3^3} \equiv \ ? \pmod{40}$ Imamo $\varphi(40) = 16$ pa je $3^{3^3} \equiv 3^{3^3 \bmod 16} \equiv 3^{11} \equiv 27 \pmod{40}$ - to lagano izračunamo koristeći činjenicu da je $3^4 = 81 \equiv 1 \pmod{40}$. Dobili smo da je $3^{3^3} \equiv 27 \pmod{40}$ i vraćanjem u prvu kongruenciju slijedi: $3^{3^{3^3}} \equiv 3^{\left(3^{3^3}\bmod \varphi(100)\right)} = 3^{27} \pmod {100}$ Računanje $3^{27}$ modulo $100$ je jednostavno, ali dugačko, zato ćemo ga izostaviti u ovom rješenju. Tražene dvije znamenke su $87$. \\\\\\ Kao rješenje upiši zbroj svih prostih faktora broja $51$.