MetaMath '22

U ovom predavanju proći ćemo jedan od osnovnih teorema u teoriji brojeva; Mali Fermatov teorem te njegovo poopćenje Eulerov teorem. \textbf{Teorem 1.} $(\textbf{Mali Fermatov teorem})$ Neka je $a$ cijeli broj i $p$ prost broj koji ne dijeli $a$. Tada vrijedi: $$ a^{p-1} \equiv 1 \pmod{p} $$ Kako su $a$ i $p$ relativno prosti vrijedi: $$ a^{p-1} \equiv 1 \pmod{p} \Leftrightarrow a^{p} \equiv a \pmod{p} $$ Također, ukoliko $p \mid a$, onda imamo $ a^{p} \equiv a \equiv 0 \pmod{p}. $ Zato tvrdnju malog Fermatovog teorema možemo i ovako izreći: \\ Za svaki prost broj $p$ i svaki prirodan broj $a$ vrijedi: $$a^{p} \equiv a \pmod{p}$$ \\ Dokaz MFT-a možete pogledati \href{https://www.skoljka.org/media/attachment/1/00142_43tjgvkhxlye0667qrk6/Osijek_2019_2020__S5.pdf}{ovdje}. \textbf{Primjer 1.} Ako su $p$ i $q$ različiti prosti brojevi, dokažite da je broj $p^{q-1} + q^{p-1} -1$ djeljiv sa $pq$. \\ \textbf{Rješenje:} Po malom Fermatovom teoremu imamo $p \mid q^{p-1} -1$, $q \mid p^{q-1} -1$, a odavde slijedi $p \mid p^{q-1} + q^{p-1} -1$, $p \mid p^{q-1} + q^{p-1} -1$. Budući da su $p$ i $q$ relativno prosti, slijedi tvrdnja zadatka. Za rješenje upišite 1.