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

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

Доказательство. 1. Сведём задачу к числам 0  a < m. Для этого разделим a с остатком на m : a = mq + r (0  r < m). При этом по свойству наибольшего общего делителя имеем

НОД(r, m) = НОД(a – mq, m) = НОД(a, m) = 1,

т.е. r удовлетворяет условию теоремы. Если уже доказано, что r^(m)  1 (mod m), то ввиду a  r (mod m) получим a^(m)  r^(m)  1 (mod m).

Таким образом, можно предполагать, что 0  a < m.

2. Пусть M = {0, 1, 2, … , m – 1} и a₁ , … , a_k – все взаимно простые элементы множества M, из которых образуем множество M₁ . По определению функции Эйлера k = (m), а по условию теоремы имеем a  M₁ .

3. Рассмотрим элементы b₁ = aa₁ , … , b_k = aa_k . По свойствам взаимно простых чисел все эти элементы взаимно просты с m. Пусть r₁ , … , r_k – остатки от деления чисел b₁ , … , b_k на m : b_i = mq_i + r_i (0  r_i < m, 1  i  k). Тогда r_i  M (1  i  k), и кроме того,

НОД(r_i , m) = НОД(b_i – mq_i , m) = НОД(b_i , m) = 1,

так что r_i  M₁ (1  i  k).

4. Докажем, что среди чисел r₁ , … , r_k нет одинаковых. Действительно, если r_i = r_j , то b_i = mq_i + r_i , b_j = mq_j + r_i (0  r_i < m). Тогда b_i  r_i  b_j (mod m), т.е. aa_i  aa_j , a(a_i – a_j)  0 (mod m) и ввиду НОД(a, m) = 1 по свойствам сравнений верно a_i – a_j  0, a_i  a_j (mod m), что значит a_i = a_j , что возможно только при i = j.

5. Итак, все числа r₁ , … , r_k различны, их число k = (m) и все они принадлежат k-элементному множеству M₁ = {a₁ , … , a_k}. Это значит, что r₁ , … , r_k – это те же числа a₁ , … , a_k , возможно, в другом порядке. Поэтому

a₁ … a_k = r₁ … r_k  b₁ … b_k = (aa₁) … (aa_k) = a^ka₁ … a_k (mod m).

Значит, a₁ … a_k  a^ka₁ … a_k (mod m), (a^(m) – 1)a₁ … a_k (mod m). Учитывая, что a₁ … a_k взаимно просто с m (т.к. все a_i взаимно просты с m), получим по свойствам сравнений a^(m) – 1  0 (mod m).

Теорема Эйлера доказана.

Упражнение. Пусть m = – каноническое разложение натурального числа m, . Тогда для любого целого числа a выполнено сравнение a^(a^(m) – 1))  0 (mod m).

Теорема (малая теорема Ферма). Для любого простого числа p и целого числа a , не делящегося на p, имеет место сравнение a ^p–1  1 (mod p).

Доказательство следует из теоремы Эйлера при m = p с учётом равенства (p) = р – 1.

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

Доказательство следует из теоремы Ферма: a ^p – a  a(a ^p–1 – 1)  0 (mod p) как для a, делящегося на p, так и для взаимно простого с p.

Упражнения: 1. Докажите, что для любого целого a выполняется сравнение a⁵⁶¹  a (mod 561), но число 561 – не простое. Таким образом, обращение теоремы Ферма не верно.

2. Докажите, что 561 – наименьший контрпример к обращению теоремы Ферма.

Теоремы Эйлера и Ферма можно использовать для нахождения остатков некоторых арифметических выражений, значения которых трудно вычислить.

I. Остатки полиномиальных выражений. Пусть требуется найти остаток от деления на заданное число m некоторого выражения P(a₁ , … , a_n), полученного из целых чисел а₁ , … , а_n с помощью операций сложения, вычитания и умножения.

Для решения этой задачи достаточно, исходя из значений а_i (mod m), найти значение P(a₁ , … , a_n) по модулю m.

Примеры: 1. Найти остаток от деления 123349 – 88560 + 893² на 4.

Вычислим значения всех участвующих в данном равенстве чисел по модулю 4: 123  –1 (mod 4), 349  1 (mod 4), 88  0 (mod 4), 893  1 (mod 4). Поэтому по свойствам сравнений имеем

123349 – 88560 + 893²  (–1)1–0560+1² = 0 (mod 4).

Значит, исходное выражение делится на 4, т.е. искомый остаток равен 0.

2. Найти остаток от деления на 6 выражения

–3356299 – 333⁸5551 – 325(–287 + 679825).

Имеем 3356  2 (mod 6), 299  –1 (mod 6), 333  3 (mod 6), 5551  1 (mod 6), 325  1 (mod 6), 287  –1 (mod 6), 679  1 (mod 6), 825  3 (mod 6). Поэтому получаем

–3356299–333⁸5551–325(–287+679825)  –2(–1)–(3²)⁴1–1(–(–1)+13) 

 2–(3²)²–(–2)  2–3²+ 2  –5  1 (mod 6),

т.е. искомый остаток равен 1.

II. Остатки экспоненциальных выражений. Пусть требуется найти остаток от деления на число m некоторого выражения P(a₁ , … , a_n), полученного из целых чисел а₁ , … , а_n с помощью операций сложения, вычитания, умножения и возведения в большие степени.

Как и ранее, для решения этой задачи достаточно, исходя из значений а_i (mod m), вычислить P(a₁ , … , a_n) (mod m). При вычислении степенных выражений с большими показателями степеней удобно пользоваться теоремами Эйлера и Ферма.

Примеры: 1. Найти остаток от деления числа 3⁵⁴⁶ – 88 на 5.

Так как НОД(3, 5) = 1, то по теореме Эйлера, 3^(5)  1 (mod 5) или 3⁴  1 (mod 5), поскольку (5) = 4. Значит, 3⁵⁴⁶ = (3⁴)¹³⁶3²  1¹³⁶3²   9  4 (mod 5), и 3⁵⁴⁶ – 88  4 – 3  1 (mod 5), так что искомый остаток равен 1.

2. Найти последнюю цифру числа 7 ⁹⁵⁴.

Заметим, что для заданного числа a = в десятичной системе счисления, выполняется сравнение (mod 10 ^s):

.

Таким образом, для нахождения s последних цифр числа a достаточно найти остаток от деления его на 10 ^s. В данном примере нужно искать остаток от деления числа 7 ⁹⁵⁴ на 10.

Поскольку НОД(7, 10) = 1, то можно воспользоваться теоремой Эйлера: 7^(10)  1 (mod 10). Вычисляем (10) = (25) = (2)(5) = 14 = 4 и получаем: 7⁴  1 (mod 10).

Поэтому 7 ⁹⁵⁴ = (7⁴)²³⁸7²  1²³⁸7² = 49  9. Итак, последняя цифра числа 7 ⁹⁵⁴ равна 9.

3. Найти две последние цифры числа 8 ³⁴⁵.

Здесь нужно искать остаток от деления числа 8 ³⁴⁵ на 100 = 10².

Поскольку НОД(8 ³⁴⁵, 100) = НОД(2 ^3345, 2²5²) = 2² = 4  1, непосредственно воспользоваться теоремой Эйлера нельзя. Если 8 ³⁴⁵ = 4y , то 8 ³⁴⁵   4y (mod 100)  428³⁴⁴  4y (mod 100)  28³⁴⁴  y (mod 25), причём 8 уже взаимно просто с 25, и можно использовать теорему Эйлера: 8^(25)  1 (mod 25). Поскольку (25) = (5²) = 5² – 5¹ = 20, то

8 ³⁴⁴  (8 ²⁰) ¹⁷8 ⁴  1¹⁷(8 ²) ²  14 ² = 196  –4 (mod 25).

Таким образом, y  28 ³⁴⁴  2(–4) = –8  17 (mod 25), и 8 ³⁴⁵ = 4y   417 = 68 (mod 100). Итак, число 8 ³⁴⁵ оканчивается на 68.

4. Найти две последние цифры числа 6 ³⁴ – 3⁵⁸.

Действуем аналогично предыдущему: поскольку НОД(6 ³⁴, 100) = 4, имеем 6 ³⁴ = 4x, 6 ³⁴  4x (mod 100)  3²6 ³²  x (mod 25) и 6 ²⁰  1 (mod 25), так что x  3²6 ³²  3²6 ¹²  936 ⁶  911 ⁶  9121 ³  9(–4)³   –964  –914 = –126  –1 (mod 25) и 6 ³⁴  4(–1) = –4  21 (mod 100).

Значительно проще найти остаток от второго слагаемого: 3 ^(100)  1 (mod 100), т.е. 3 ⁴⁰  1 и 3 ⁵⁸  3 ¹⁸ = 81 ⁴3 ²  19 ⁴3 ²  61 ²3 ² = 183 ²   (–17) ² = 289  89 (mod 100). Таким образом, 6 ³⁴ – 3⁵⁸  21 – 89 = – 68   32 (mod 100), т.е. исходное число оканчивается на 32.