MetaMath '25

[b]Primjer 1.[/b] Izračunaj $3^{33}$ modulo $7$. (Odredi ostatak pri dijeljenju broja $3^{33}$ sa $7$.) [b]Rješenje:[/b] Budući da je $7$ prost broj i $\gcd(3, 7) = 1$, mali Fermatov teorem govori $3^6 \equiv 1\pmod 7$. Eksponent $33$ možemo zapisati kao $5\cdot6 + 3$ pa imamo: $$ 3^{33} = 3^{5\cdot6 + 3} = 3^{5\cdot 6}\cdot 3^3 = \left(3^6\right)^5\cdot3^3 \equiv 1^5\cdot3^3 \equiv 27 \equiv 6 \pmod 7$$ \\ \\ [b]Primjer 2.[/b] Odredi sve proste brojeve $p$ takve da je $29^p + 1$ djeljiv s $p$. Ideja rješenja: iskoristimo mali Fermatov teorem za $a=29$ [b]Rješenje:[/b] Tvrdnja zadatka zapisana kao kongruencija glasi $29^p + 1 \equiv 0 \pmod p$. \\ Prema malom Fermatovom teoremu imamo $29^p \equiv 29 \pmod p$. \\ Kombiniranjem te dvije kongruencije dobivamo $30 \equiv 0 \pmod p$ iz čega slijedi da je $p$ djelitelj broja $30$. Provjerom potvrdimo da brojevi $p = 2, 3, 5$ doista zadovoljavaju traženu tvrdnju Rješenje ovog zadatka je isto kao i rješenje prvog primjera.