Теоремы Эйлера и Ферма.

В теории сравнений важную роль играет теорема Эйлера.

ТЕОРЕМА ЭЙЛЕРА. Если целое число а взаимно простое с , то

Доказательство. Пусть

есть приведенная система вычетов по модулю . Тогда согласно предложению 3.4

также есть приведенная система вычетов по модулю . Поэтому произведение чисел (3) сравнимо с произведением чисел (2), т. е.

Произведение взаимно простое с т. Поэтому согласно свойству 1.6 обе части сравнения (4) можно разделить на это произведение, тогда .

ТЕОРЕМА ФЕРМА. Если целое число а не делится на простое число , то .

Эта теорема есть частный случай предыдущей теоремы при . Теорема Ферма часто формулируется иначе.

ВТОРАЯ ФОРМУЛИРОВКА ТЕОРЕМЫ ФЕРМА. Если — простое и а — любое целое число, то .