Малая теорема Ферма — один из краеугольных камней теории чисел. Она проста по формулировке, но чрезвычайно мощна в приложениях. Понимание её сути и умение применять — важный навык для решения олимпиадных задач, криптографических алгоритмов и других задач.
Малая теорема Ферма
Визуализация и проверка теоремы
Формулировка теоремы:
Если p — простое число, и a — целое число, не делящееся на p, то:
Или эквивалентно: ap ≡ a (mod p) для любого целого a
Типовые задачи и примеры
Что такое Малая теорема Ферма?
Формулировка теоремы
Классическая форма:
ap-1 ≡ 1 (mod p)
Эквивалентная форма:
ap ≡ a (mod p)
Ключевые моменты
Теорема работает только для простых модулей p
Если a делится на p, то ap-1 ≡ 0 (mod p), а не 1
Теорема часто используется для упрощения вычислений с большими степенями
Историческая справка
Теорема была сформулирована Пьером де Ферма в 1640 году без доказательства. Первое доказательство было опубликовано Леонардом Эйлером в 1736 году.
Описание и практическое применение
Основные области применения
🔢 Криптография (RSA)
МТФ лежит в основе алгоритма RSA — одного из первых алгоритмов с открытым ключом, широко используемого для безопасной передачи данных.
✅ Тесты на простоту
Тест Ферма используется для проверки чисел на простоту (хотя и не является абсолютно надежным).
🧮 Вычисления с большими числами
Упрощение вычислений с огромными степенями по модулю простого числа.
🔐 Нахождение обратных элементов
Быстрое вычисление обратных элементов в конечных полях, что важно в теории кодирования.
Математическое описание
Малая теорема Ферма устанавливает фундаментальное свойство мультипликативной группы конечного поля:
Для любого элемента a этой группы: ap-1 = 1
Пример в криптографии
В алгоритме RSA для шифрования используется формула:
А для дешифрования:
где e·d ≡ 1 (mod φ(n)), и МТФ гарантирует корректность работы.
Алгоритм 1: Нахождение остатка от деления
Пошаговая инструкция
Проверить, что модуль p является простым числом
Убедиться, что основание a не делится на p (иначе ответ 0)
По МТФ: ap-1 ≡ 1 (mod p)
Представить большую степень в виде: k = (p-1)·q + r
Упростить: ak ≡ (ap-1)q·ar ≡ 1q·ar ≡ ar (mod p)
Вычислить ar mod p
Пример применения
Задача: Найти остаток от деления 5100 на 13
Решение по алгоритму:
1) p = 13 — простое ✓
2) 5 не делится на 13 ✓
3) По МТФ: 512 ≡ 1 (mod 13)
4) 100 = 12×8 + 4 ⇒ q = 8, r = 4
5) 5100 = (512)8·54 ≡ 18·54 = 54 (mod 13)
6) 52 = 25 ≡ 12 ≡ -1 (mod 13)
54 = (52)2 ≡ (-1)2 = 1 (mod 13)
Ответ: 1
Типовые задачи: Остатки от деления
Задача 1: Найти остаток от деления 7100 на 11
Решение:
1) p = 11 — простое, 7 не делится на 11 ✓
2) По МТФ: 710 ≡ 1 (mod 11)
3) 100 = 10×10 + 0 ⇒ r = 0
4) 7100 = (710)10 ≡ 110 = 1 (mod 11)
Ответ: 1
Задача 2: Найти остаток от деления 32024 на 17
Решение:
1) p = 17 — простое, 3 не делится на 17 ✓
2) По МТФ: 316 ≡ 1 (mod 17)
3) 2024 = 16×126 + 8 ⇒ q = 126, r = 8
4) 32024 = (316)126·38 ≡ 1126·38 = 38 (mod 17)
5) Вычисляем: 32 = 9, 34 = 81 ≡ 13 ≡ -4, 38 = (34)2 ≡ (-4)2 = 16
Ответ: 16
Задача 3: Найти последнюю цифру числа 13100
Решение:
Последняя цифра — это остаток от деления на 10.
НОД(13, 10) = 1, но 10 — составное число, используем φ(10) = 4
По теореме Эйлера: 134 ≡ 1 (mod 10)
100 = 4×25 ⇒ 13100 = (134)25 ≡ 125 = 1 (mod 10)
Ответ: 1
Алгоритм 2: Нахождение обратного элемента
Следствие из МТФ: Если p простое и p ∤ a, то
Потому что: a·ap-2 ≡ ap-1 ≡ 1 (mod p)
Пошаговая инструкция
Проверить, что p — простое и a не делится на p
Найти обратный элемент по формуле: a-1 ≡ ap-2 (mod p)
Вычислить ap-2 mod p, используя алгоритм быстрого возведения в степень
Проверить результат: a·(a-1) ≡ 1 (mod p)
Пример: Решить сравнение 3x ≡ 1 (mod 11)
Решение:
1) p = 11 — простое, 3 не делится на 11 ✓
2) 3-1 ≡ 39 (mod 11) (т.к. 11-2 = 9)
3) Вычисляем 39 mod 11:
32 = 9, 34 = 81 ≡ 4, 38 ≡ 42 = 16 ≡ 5
39 = 38·3 ≡ 5·3 = 15 ≡ 4 (mod 11)
4) Проверка: 3×4 = 12 ≡ 1 (mod 11) ✓
5) Тогда x ≡ 4 (mod 11)
Ответ: x ≡ 4 (mod 11)
Алгоритм 3: Доказательство делимости
Пошаговая инструкция
Записать условие делимости как сравнение по модулю p
Применить МТФ в форме: ap ≡ a (mod p)
Преобразовать выражение, используя это сравнение
Показать, что результат ≡ 0 (mod p)
Задача 1: Может ли число 215 — 1 делиться на 15?
Решение:
15 = 3×5 (составное число). Проверим делимость на каждый множитель.
1) Делимость на 3: По МТФ: 22 ≡ 1 (mod 3)
15 = 2×7 + 1 ⇒ 215 = (22)7·2 ≡ 17·2 = 2 (mod 3)
215 — 1 ≡ 2 — 1 = 1 (mod 3) ⇒ НЕ делится на 3
2) Уже на этом этапе ясно, что 215 — 1 не делится на 15
Ответ: Нет, не может
Задача 2: Доказать, что n7 — n делится на 42
Решение:
42 = 2×3×7 (все простые числа)
Докажем делимость на каждый простой множитель:
1) На 7: По МТФ: n7 ≡ n (mod 7) ⇒ n7 — n ≡ 0 (mod 7)
2) На 3: n3 ≡ n (mod 3) ⇒ n7 = (n3)2·n ≡ n2·n = n3 ≡ n (mod 3)
3) На 2: n2 ≡ n (mod 2) ⇒ n7 ≡ n (mod 2)
Во всех случаях n7 ≡ n (mod p) для p=2,3,7
Следовательно, n7 — n делится на 2, 3 и 7, а значит и на 42.
Сложные задачи на делимость
Задача: Доказать, что n13 — n делится на 2730
Решение:
2730 = 2×3×5×7×13 (все простые числа)
Докажем делимость на каждый из простых множителей:
1) На 13: По МТФ: n13 ≡ n (mod 13) ⇒ n13 — n ≡ 0
2) На 7: n7 ≡ n (mod 7) ⇒ n13 = n7·n6 ≡ n·n6 = n7 ≡ n (mod 7)
3) На 5: n5 ≡ n (mod 5) ⇒ n13 = (n5)2·n3 ≡ n2·n3 = n5 ≡ n (mod 5)
4) На 3: n3 ≡ n (mod 3) ⇒ n13 = (n3)4·n ≡ n4·n = n5 = n3·n2 ≡ n·n2 = n3 ≡ n (mod 3)
5) На 2: n2 ≡ n (mod 2) ⇒ n13 ≡ n (mod 2)
Таким образом, n13 ≡ n (mod p) для всех p=2,3,5,7,13
Следовательно, n13 — n делится на каждый из этих простых чисел, а значит и на их произведение 2730.
Задача 3: Доказать, что 1012 — 1 делится на 13
Решение:
1) p = 13 — простое, 10 не делится на 13 ✓
2) По МТФ: 1012 ≡ 1 (mod 13)
3) Тогда 1012 — 1 ≡ 1 — 1 = 0 (mod 13)
4) Что и означает делимость на 13
Доказано.
Общая стратегия для сложных задач
1. Разложите составной модуль на простые множители
2. Докажите делимость на каждый простой множитель отдельно
3. Используйте МТФ для каждого простого модуля
4. Если степень больше p, представьте её через меньшие степени
Практические задания для самостоятельного решения
Задача 1
Найдите остаток от деления 5100 на 13.
Решение: 13 — простое, 512 ≡ 1 (mod 13).
100 = 12×8 + 4 ⇒ 5100 ≡ 54 (mod 13).
52=25≡12≡-1, 54≡(-1)2=1 (mod 13).
Ответ: 1
Задача 2
Докажите, что 1012 — 1 делится на 13.
Решение: p=13 — простое, 10 не делится на 13.
По МТФ: 1012 ≡ 1 (mod 13).
Следовательно, 1012 — 1 ≡ 0 (mod 13).
Задача 3
Решите сравнение: 3x ≡ 1 (mod 11).
Решение: Найдём обратный к 3 по модулю 11.
3-1 ≡ 39 (mod 11) = 4.
Проверка: 3×4=12≡1 (mod 11).
Ответ: x ≡ 4 (mod 11).
Задача 4
Докажите, что n13 — n делится на 2730 для любого целого n.
Подсказка: 2730 = 2×3×5×7×13.
Докажите делимость на каждый простой множитель, используя МТФ.
Частые ошибки и важные предупреждения
Ошибка 1: Применение к составному модулю
Неправильно: Использовать МТФ для модуля, который не является простым.
Правильно: Для составного модуля m использовать теорему Эйлера: aφ(m) ≡ 1 (mod m), если НОД(a, m) = 1.
Ошибка 2: Неучет условия p ∤ a
Неправильно: Считать, что 104 ≡ 1 (mod 5), потому что 5-1=4.
Правильно: Если a делится на p, то ap-1 ≡ 0 (mod p), а не 1.
Пример: 104 mod 5 = 0, так как 10 делится на 5.
Ошибка 3: Путаница с формами теоремы
Запомните:
- ap-1 ≡ 1 (mod p) — работает только если p ∤ a
- ap ≡ a (mod p) — работает для всех a
Проверочный чек-лист
Модуль p — простое число? ✓/✗
Если используете форму ap-1 ≡ 1, проверьте, что p не делит a ✓/✗
Правильно ли представлена степень: k = (p-1)·q + r? ✓/✗
Проверен ли случай, когда a кратно p? ✓/✗
Итоговые рекомендации
1. Всегда проверяйте простоту модуля
2. Помните про две формы МТФ и условия их применения
3. Для сложных задач разбивайте модуль на простые множители
4. Практикуйтесь на различных примерах
Дополнительно
часть 1: https://kvant.mccme.ru/pdf/2000/03/kv0300senderov.pdf
часть 2: https://kvant.ras.ru/pdf/2000/04/kv0400ferm.pdf
Историческая справка
Пьер де Ферма (1601–1665) — французский математик-любитель, один из основоположников теории чисел. Несмотря на то, что он не был профессиональным математиком (по профессии — юрист), его вклад в математику огромен.
Малая теорема Ферма была сформулирована им в 1640 году в письме к своему другу Бернару Френиклю. Ферма написал: «Если p — простое число, а a — целое число, не делящееся на p , то ap−1−1 делится на p ». Он не привёл доказательства, сопроводив это замечанием: «Я бы Вам прислал доказательство, если бы не боялся, что оно слишком длинное» — типичная для Ферма фраза.
Первое известное доказательство теоремы дал Готфрид Лейбниц в неопубликованной рукописи около 1683 года. Позже Леонард Эйлер в 1736 году опубликовал первое строгое доказательство и впоследствии обобщил теорему (теорема Эйлера).