Математика / Арифметика и теория чисел

Малая теорема Ферма: степени по простому модулю

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Теория чисел Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a

Схема Умножение на 3 переставляет остатки mod 7

Все 6 ненулевых классов встречаются ровно один раз

Обозначения

$p$: простой положительный модуль, целое число
$a$: целое основание, не кратное p, целое число
$p-1$: показатель, заведомо возвращающий единичный остаток, неотрицательное целое
$\equiv$: равенство классов остатков по указанному модулю, логическое отношение

Условия применения

Модуль p должен быть простым, а a не должно делиться на p. Сокращать неотрицательный показатель по модулю p−1 можно именно при этих условиях. Равносильная общая запись aᵖ ≡ a mod p допускает любое целое a, но переход к aᵖ⁻¹ ≡ 1 требует обратимости основания.

Ограничения

Для составного модуля запись с показателем m−1 в общем случае неверна. Обратное утверждение тоже неверно: отдельное выполненное сравнение не доказывает простоту. Теорема задаёт допустимый период степеней, который не обязательно минимален. Отрицательные показатели сначала требуют определить обратный элемент.

Подробное объяснение

Рассмотрим ненулевые остатки 1,2,…,p−1. Умножение каждого из них на a и взятие остатка только переставляет этот набор. Совпадение двух результатов означало бы a(i−j) ≡ 0; поскольку p простое и не делит a, пришлось бы i = j в выбранном диапазоне.

Произведение всех новых остатков поэтому сравнимо с исходным произведением. Получается aᵖ⁻¹·(p−1)! ≡ (p−1)! mod p. Каждый множитель факториала обратим, так что произведение можно сократить и получить aᵖ⁻¹ ≡ 1. Здесь взаимная простота нужна именно для допустимости сокращения.

Для большого n пишут n = q(p−1)+r, где 0 ≤ r < p−1. Тогда aⁿ ≡ (aᵖ⁻¹)ᑫaʳ ≡ aʳ. Это уменьшает показатель, но оставшуюся степень всё равно нужно вычислить, например двоичным методом.

При p > 2 обратный элемент к a можно записать как aᵖ⁻², поскольку умножение на a даёт единицу. При p = 2 единственный ненулевой остаток и так равен единице. Если основание кратно p, у него нет обратного элемента и такое применение теоремы недопустимо.

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

Как пользоваться формулой

Подтвердите простоту p и проверьте, что остаток основания по p ненулевой; не пропускайте оба условия теоремы.
Разделите показатель n на p−1 с остатком и замените его этим остатком только для обратимого основания.
Вычислите небольшую оставшуюся степень по модулю, используя повторные квадраты вместо десятичных приближений.
Для обратного элемента дополнительно проверьте произведение с исходным основанием; не делайте вывода о простоте по одному сравнению.

Историческая справка

Теорема носит имя Пьера де Ферма и относится к развитию теории чисел XVII века. Её современное изложение через перестановку ненулевых остатков делает условие простого модуля и возможность сокращения явными. Позднее теорема Эйлера расширяет эту логику на все обратимые остатки по составному модулю. В учебнике Джонатана Порица оба результата рассматриваются вместе, чтобы показать связь между арифметикой сравнений и умножением классов вычетов. Это отличается от исторической формы отдельного утверждения о степенях: современный язык организует доказательство через структуру множества остатков. Здесь не устанавливается приоритет конкретного варианта доказательства; имя Ферма относится к самой теореме, а не ко всем современным алгоритмам её применения.

Историческая линия формулы

Используется традиционное название «малая теорема Ферма». Показанное доказательство через перестановку ненулевых остатков — современное учебное обоснование. Его не следует автоматически приписывать Ферма или смешивать с другими утверждениями, также носящими его имя.

Пример

Найдём 3¹⁰ mod 7 и обратный элемент к 3 по модулю 7. Число 7 простое и не делит 3, поэтому 3⁶ ≡ 1. Остаток показателя 10 по 6 равен 4; 3¹⁰ ≡ 3⁴. Квадрат 3² ≡ 2, следующий квадрат 3⁴ ≡ 4, значит ответ 4. Для обратного элемента используем 3⁵: 3⁴·3 ≡ 4·3 ≡ 5. Проверка 3·5 = 15 ≡ 1 mod 7. Независимо выпишем первые шесть степеней: остатки 3,2,6,4,5,1. Цикл подтверждает оба результата. Значения относятся к целочисленной арифметике без единиц; число 6 здесь является допустимым периодом, а не универсальным свойством любого модуля.

Частая ошибка

Не используйте p−1 для составного модуля без другой теоремы. Не сокращайте нулевой остаток. Не путайте малую теорему Ферма с утверждением о суммах степеней. Не считайте выполненное сравнение доказательством простоты. Не утверждайте, что минимальный период каждого основания обязательно равен p−1.

Практика

Задачи с решением

Большой показатель

Условие. Найдите 2¹⁰⁰ mod 13.

Решение. 13 простое, 2 обратимо. Остаток 100 по 12 равен 4, значит 2¹⁰⁰ ≡ 2⁴ = 16 ≡ 3 mod 13.

Ответ. 3.

Составной модуль

Условие. Проверьте, можно ли заменить 2⁸ mod 9 единицей по аналогии с теоремой Ферма.

Решение. 9 составное. Прямой расчёт 2⁸ = 256 даёт остаток 4, а не 1. Условие простоты действительно существенно.

Ответ. Нельзя; остаток 4.

Дополнительные источники

https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/03%3A_Primes_Numbers/3.04%3A_Another_Approach_to_Fermat%27s_Little_and_Euler%27s_Theorems
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/An_Introduction_to_the_Theory_of_Numbers_%28Moser%29/01%3A_Chapters/1.05%3A_Congruences

Связанные формулы

Математика

Быстрое возведение в степень по модулю двоичным методом

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

Математика

Теорема Эйлера: сокращение степени по составному модулю

$a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$

Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.

Математика

Линейное сравнение: решения через НОД коэффициента и модуля

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

Математика

Мультипликативный порядок: минимальный период степеней

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.