Školjka

%V0 [b]Mali Fermatov teorem[/b] 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$. [b]Dokaz[/b] 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.