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

Теорема Эйлера. Если m> 1 и (а, m) = 1, то l(mod m).

Доказательство. Действительно, если x пробегает приведённую систему вычетов по модулю m: , тогда ах пробегает тоже

приведённую систему вычетов: .

Поскольку числа приведённой системы вычетов набираются из одних и тех же классов, взаимно простых с модулем, то для каждого числа второй системы найдется сравнимое с ним число первой системы.

……………

Перемножаем почленно эти сравнения:

Подчёркнутые произведения состоят из одних и тех же чисел, взаимно простых с модулем. Значит, последнее сравнение можно разделить на подчёркнутое одно и то же число (т.к. оно взаимно просто с модулем). В

результате получаем

Теорема Ферма. Пусть a Z, р— простое. Если (а,р)=1, то

Доказательство следует из теоремы Эйлера при m=р, т.к. р -1.

Следствие. Для любого целого а и простого p (mod р).

Доказательство. 1. Если а не р, то по теореме Ферма

Умножим обе части сравнения на число а, получим

2 2. Если а р, то a 0(modр) и 0(mod р). Следовательно,

Пример. Найти остаток от деления на 52.

Решение. Заметим, что число по модулю m сравнимо со своим остатком от деления на m.

1)Заменим основание степени сравнимым с ним числом 171 15(mod 52), тогда по свойствам сравнений (mod52).

2)Т.к. (15,52) = 1, то =l(mod 52) (теорема Эйлера). Найдем

(52) = 52 = 24, тогда = l(mod 52).

3)Разделим 2147 на 24 с остатком:

Возведем обе части сравнения = l(mod 52) в 89 степень и умножим на . Получим

4)Найдем остаток от деления на 52.

Умножив на 15, получим

Возведем обе части в куб:

Перемножим это сравнение и (mod 52) и получим (mod 52).

тогда (mod52), (mod 52), (mod52), (mod 52). Используя транзитивное свойство сравнений, видим, что остаток от делении на 52 равен 7.