Теоремы Эйлера и Ферма.
В теории сравнений важную роль играет теорема Эйлера.
ТЕОРЕМА ЭЙЛЕРА. Если целое число а взаимно простое с 
, то
Доказательство. Пусть
есть приведенная система вычетов по модулю 
. Тогда согласно предложению 3.4
также есть приведенная система вычетов по модулю 
. Поэтому произведение чисел (3) сравнимо с произведением чисел (2), т. е.
Произведение 
взаимно простое с т. Поэтому согласно свойству 1.6 обе части сравнения (4) можно разделить на это произведение, тогда 
.
ТЕОРЕМА ФЕРМА. Если целое число а не делится на простое число 
, то 
.
Эта теорема есть частный случай предыдущей теоремы при 
. Теорема Ферма часто формулируется иначе.
ВТОРАЯ ФОРМУЛИРОВКА ТЕОРЕМЫ ФЕРМА. Если 
— простое и а — любое целое число, то 
.
