Mali Fermatov teorem
Ako je
tada za svaki
vrijedi
.
Posebno, ako je
relativno prost s
, gornju jednakost možemo zapisati kao
.
Dokaz
Koristit ćemo tvrdnju iz drugog zadatka iz ovog predavanja. (Pokušajte ga riješiti prije nego što nastavite čitati).
Kako su i
i
reducirani sustavi ostataka, umnožak svih njihovih elemenata mora davati isti ostatak pri dijeljenju s
.
Dakle,
.
Ako pokratimo
(znamo da to smijemo jer taj broj sigurno ima inverz modulo
) dobivamo upravo drugu tvrdnju teorema
.
Ako je
relativno prost s
, smijemo cijelu jednadžbu pomnožiti s
, i dobiti prvu tvrdnju teorema. Ako nije, tada je
pa prva tvrdnja sigurno vrijedi.
Ako je
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![a^p \equiv a \pmod p](/media/m/1/a/9/1a937f3beaa1fd23bfc41e5d7104eac5.png)
Posebno, ako je
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![a^{p-1} \equiv 1 \pmod p](/media/m/d/8/7/d87d99c39ed17453ec271acad084d4e3.png)
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\}](/media/m/6/d/d/6dd2cfb799cc6ff638e6427e1d4c9ed3.png)
![\{a,2a,...,(p-1)a\}](/media/m/d/6/0/d606b85a976deb49296e5028d53d5f47.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
Dakle,
![1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \equiv a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a \pmod p](/media/m/6/9/f/69fd791070edb16e409d3da156b7d8dc.png)
Ako pokratimo
![(p-1)!](/media/m/2/3/7/2377214814ffc2748b4d168365f3cdd5.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![a^{p-1} \equiv 1 \pmod p](/media/m/d/8/7/d87d99c39ed17453ec271acad084d4e3.png)
Ako je
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![a \equiv 0 \pmod p](/media/m/6/c/f/6cfcd61ef7b7d8fbbdac339cf0c82a22.png)