Малая теорема Ферма

Формулировка и основные варианты

Малая теорема Ферма - если целое число не делится на простое число p, то при возведении этого числа в степень p-1 результат сравним по модулю p с единицей.

Стандартную запись этой теоремы обычно дают в виде следующего соотношения: $a^{p-1}\equiv 1\pmod p$. Это выражение удобно использовать, когда известен модуль и основание, взаимно простые.

Существует также эквивалентная форма, удобная для практических расчётов: $a^{p}\equiv a\pmod p$. Она следует из первой формы и часто применяется в задачах, где рассматривают остаток при делении степени числа на простое.

Важно различать условия: теорема требует, чтобы основание было не делимым на рассматриваемое простое. Если это условие нарушено, то в простейшем случае остаётся тривиальная тождественность, которую также полезно иметь в виду при решении задач.

Доказательство через умножение остатков

Один из классических доказательств опирается на набор остатков при умножении на фиксированное число, взаимно простое с модулем. Рассмотрим множители a, 2a, 3a, ..., (p-1)a по модулю p — они порождают тот же набор остатков, что и 1,2,3,...,p-1, только в другом порядке. Это утверждение формализуется через произведение и даёт соотношение вида $a^{p-1}(p-1)!\equiv (p-1)!\pmod p$.

Так как факториал (p-1)! не делится на простое p, его можно сократить в полученном сравнении, что приводит непосредственно к основной формуле теоремы: $a^{p-1}\equiv 1\pmod p$. Именно здесь критично условие взаимной простоты оснований и модуля.

В доказательстве явно используется свойство перестановки остатков: при домножении на a, не имеющее общих делителей с p, ни один остаток не превращается в ноль, и все остатки 1..p-1 как множество сохраняются. Этот приём прост и нагляден, поэтому он часто приводится в школьных курсах.

Доказательство через бином Ньютона (комбинаторный подход)

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

В частности, для любых целых a и b справедливо сравнение {FORMULA_11}, что можно показать, рассмотрев развёртку (a+b)^p и заметив делимость межу коэффициентов на p. Подставив специальный выбор переменных и применяя индукцию, получают форму $a^{p}\equiv a\pmod p$.

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

Примеры и практические вычисления

Если основание делится на модуль, то остаётся тривиальная ситуация: при $a^{\varphi(n)}\equiv 1\pmod n$ соответствующие сравнения превращаются в тождества вида $a^{p}\equiv a\pmod p$. В задачах это полезно учитывать заранее, чтобы не применять теорему в некорректных условиях.

Следствия, применения и обобщения

Малая теорема Ферма лежит в основе простейших тестов на простоту. Если для некоторого предполагаемого простого p найдётся основание a такое, что $a^{n-1}\equiv 1\pmod n$, то p обязательно составное. Этот простой критерий называется тестом Ферма и применяется для быстрой фильтрации кандидатов в простые числа.

Теорема также обобщается на составные модули через теорему Эйлера. Если натуральное n и число a взаимно просты, то справедливо обобщённое соотношение $a^{p-1}\not\equiv 1\pmod p\Rightarrow p\text{ is composite}$. Это расширение имеет важное значение в теории чисел и криптографии, в частности в алгоритмах, основанных на работе с модульной арифметикой.

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

Ограничения метода и псевдопростые числа

Несмотря на полезность теста Ферма, он не является достаточным для гарантии простоты: существуют составные числа, для которых для многих оснований выполняется соотношение $a^{560}\equiv 1\pmod{561}\text{ for all }\gcd(a,561)=1$. Такие числа называются псевдопростыми по базам или кармайкловыми числами в частых случаях.

Например, число 561 обладает свойством, что для любого числа a, взаимно простого с 561, выполняется сравнение $(a+b)^p\equiv a^p+b^p\pmod p$. Это показывает, что полагаться только на один базовый тест Ферма рискованно при проверке простоты, и в практических приложениях применяют более надёжные методы.

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

Заключение и рекомендации к изучению

Малая теорема Ферма — центральная и легко усваиваемая часть школьной теории чисел. Она даёт простые и мощные приёмы для вычисления остатков больших степеней и служит отправной точкой для более глубоких тем, таких как теорема Эйлера и криптография.

Рекомендуется закреплять понимание теоремы на численных примерах, а также изучить оба классических доказательства: через произведение остатков и через бином Ньютона. Это даст как техничное умение применять теорему, так и понимание её причин.

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