1 - Sustavi Ostataka Teorem
Avg:
Avg:
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



Posebno, ako je



Dokaz
Koristit ćemo tvrdnju iz drugog zadatka iz ovog predavanja. (Pokušajte ga riješiti prije nego što nastavite čitati).
Kako su i



Dakle,

Ako pokratimo



Ako je



