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

Теорема 10. 2 (теорема Эйлера). Для любого целого числа a, взаимно простого с натуральным модулем m, выполняется сравнение

1 (mod m).

Доказательство. Пусть r₁, …, r_k – какая-нибудь приведенная система вычетов по модулю m. Тогда k = (m). Согласно свойства приведенной системы множество чисел аr₁, …, аr_k также составляет приведенную систему вычетов. Это значит, что каждое число второй системы лежит в одном классе с каким-либо единственным числом первой системы вычетов. Поэтому справедливы сравнения

аr₁ ∙ … · аr_k r₁ · … ∙ r_k (mod m) (1)

Так как каждое из чисел r_j взаимно просто с модулем, то сравнение (1) можно сократить на каждое из чисел r_j. В результате получаем сравнение а^k 1(mod m) или 1 (mod m).

Пример. а = 5, m = 9. (5, 9) = 1 1(mod 9), т.к. (9) = (3²) = = 3 · (3 – 1) = 6. Итак, 5⁶ 1(mod 9).

Рассмотрим частный случай теоремы Эйлера, в котором m = p есть простое число. Тогда (p) = p – 1 и получается следующее утверждение.

Теорема 10.3 (малая теорема Ферма). Если целое число а не делится на простое число p, то

1 (mod p).

Теорема 10.4 (следствие малой теоремы Ферма). Для любого простого числа p и целого a выполняется сравнение

(mod p).

Доказательство следует из малой теоремы Ферма:

a ^p – a º a× (a ^p–1 – 1) º 0 (mod p) как для целого числа a, делящегося на p, так и для целого числа а взаимно простого с p.

Рассмотрим теперь некоторые применения доказанных теорем. Примеры: 1. Найти остаток от деления 5²⁴⁷ на 7.

Так как (5, 7) = 1, то по теореме Эйлера, 5^j(7) º 1 (mod 7) или 5⁶ º 1 (mod 7), поскольку (7) = 6. Значит, 5²⁴⁷ = (5⁶)⁴¹ × 5 º 1⁴¹ × 5 º 5 (mod 7). Итак, искомый остаток равен 5.

2. Определим последние три цифры в десятичной записи числа 3²⁰⁰⁷. Для этого достаточно сосчитать остаток от деления 3²⁰⁰⁷ на 1000. Так как (1000) = (8) · (125) = 4 · 100 = 400 и (3, 1000) = 1, то по теореме Эйлера выполняется сравнение 3⁴⁰⁰ º 1 (mod 1000). Отсюда следует

3²⁰⁰⁷ = (3⁴⁰⁰)⁵ · 3⁷ º 3⁷ (mod 1000).

Это сравнение означает, что 3²⁰⁰⁷ и 3⁷ = 2187 имеют одинаковые три последние цифры, и десятичная запись числа 3²⁰⁰⁷ оканчивается цифрами 187.