MetaMath '24

Riješimo sada prethodni primjer na drugi način. \textbf{Primjer 1.} Odredite ostatak od $2^{200}$ pri dijeljenju sa $7$. Iskoristimo mali Fermatov teorem: znamo da je $2^6 \equiv 1 \pmod{7}$. Onda je i $$2^{6k} \equiv (2^6)^k \equiv 1^k \equiv 1 \pmod{7}$$ za sve $k \in \mathbb{N}$. Posebno, ponovno zbog $200 = 198 + 2$, imamo $$2^{200} \equiv 2^{198} \cdot 2^2 \equiv 4 \pmod{7}$$ Prednost ovog pristupa je što nismo morali ručno računati potencije. Međutim, također možemo primijetiti jednu bitnu stvar: u ovom smo slučaju imali i $2^3 \equiv 1 \pmod{7}$ i $2^6 \equiv 1 \pmod{7}$. Donekle česta greška je pretpostaviti da je onaj $p - 1$ iz Fermatovog teorema najmanji mogući eksponent koji potenciranjem daje ostatak $1$ --- to općenito nije istina. Taj teorem nam samo daje neki eksponent za koji to vrijedi, ne nužno najmanji. Ako znate nešto o periodima, možete razmišljati o $p - 1$ kao jednom periodu potencije modulo $p$, ali to nije uvijek istovremeno i temeljni period. Upišite 1 za nastavak.