« Vrati se
Mali Fermatov teorem
Ako je p tada za svaki a vrijedi a^p \equiv a \pmod p.
Posebno, ako je a relativno prost s p, gornju jednakost možemo zapisati kao a^{p-1} \equiv 1 \pmod p.

Dokaz
Koristit ćemo tvrdnju iz drugog zadatka iz ovog predavanja. (Pokušajte ga riješiti prije nego što nastavite čitati).
Kako su i \{1,2,...,p-1\} i \{a,2a,...,(p-1)a\} reducirani sustavi ostataka, umnožak svih njihovih elemenata mora davati isti ostatak pri dijeljenju s p.
Dakle,  1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \equiv a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a \pmod p .
Ako pokratimo (p-1)! (znamo da to smijemo jer taj broj sigurno ima inverz modulo p) dobivamo upravo drugu tvrdnju teorema a^{p-1} \equiv 1 \pmod p.
Ako je a relativno prost s p, smijemo cijelu jednadžbu pomnožiti s a, i dobiti prvu tvrdnju teorema. Ako nije, tada je a \equiv 0 \pmod p pa prva tvrdnja sigurno vrijedi.

Slični zadaci