Математика / Арифметика и теория чисел
Теорема Вильсона: факториал по простому модулю
Целое число p>1 простое тогда и только тогда, когда (p−1)! ≡ −1 (mod p). Для простого p каждый множитель 1,…,p−1 имеет обратный по модулю p, и почти все пары взаимно сокращаются; остаются только 1 и p−1.
Формула
2·4 ≡ 1 и 3·5 ≡ 1 по модулю 7; 1 и 6 обратны сами себе. Остаток произведения — 6.
Обозначения
- $p$
- проверяемое целое число, —
- $(p−1)!$
- произведение 1·2·…·(p−1), —
- mod p
- остаток по модулю p, —
Условия применения
p — целое число больше единицы, сравнение выполняется по модулю p, а факториал означает произведение всех чисел от 1 до p−1. Знак −1 можно заменить на p−1 в стандартном представителе остатка.
Ограничения
Теорема даёт эквивалентность, но прямой тест медленный для больших p. Нельзя проверять только несколько множителей или заменять факториал на произвольное произведение: это уже не критерий Вильсона.
Подробное объяснение
Если p простое, у каждого a из 1,…,p−1 существует единственный обратный элемент a⁻¹ по модулю p. В произведении (p−1)! взаимно сокращаются все пары a и a⁻¹, кроме самих себя обратных элементов. Уравнение a²≡1 (mod p) переписывается как (a−1)(a+1)≡0. Так как p простое, один из множителей должен быть кратен p, поэтому среди ненулевых остатков остаются только a=1 и a=p−1. Их произведение равно p−1≡−1.
Обратное утверждение доказывают от противного. Если p составное, выберем делитель d с 1 < d < p. Этот d входит в (p − 1)!, поэтому делит факториал. Но сравнение (p − 1)! ≡ −1 по модулю p означало бы то же сравнение по модулю d, то есть 0 ≡ −1, что невозможно. При p = 2 прямое утверждение проверяется отдельно: 1! = 1 ≡ −1 (mod 2).
Прямое вычисление удобно для маленьких p: последовательно умножают текущий остаток на k и берут modulo p. После последнего шага сравнивают результат с p−1. Стоимость линейна по p, а память постоянна.
Теорема полезна для доказательств, но не заменяет быстрый тест простоты в криптографии или переборе больших чисел. В таких задачах стоимость O(p) слишком велика и используется только для небольших кандидатов.
Как пользоваться формулой
- Проверьте, что p — целое число больше 1, и задайте остаток r=1 перед началом цикла.
- Для k от 2 до p−1 умножайте r на k и заменяйте r остатком r mod p, сохраняя только небольшой остаток.
- После цикла сравните r с p−1, то есть с остатком −1 по модулю p в неотрицательном представителе.
- Если r=p−1, критерий подтверждает простоту p; если r отличается, p составное и равенство не выполнено.
- Для доказательства вручную сгруппируйте ненулевые остатки с их обратными элементами и отдельно найдите решения x²≡1.
- Для больших p оцените стоимость и выберите специальный быстрый тест простоты вместо факториала, потому что линейный цикл слишком долгий.
Историческая справка
Джон Вильсон сформулировал наблюдение в XVIII веке; Эдвард Уоринг сообщил его в 1770 году, а Лагранж дал первое опубликованное доказательство в 1771 году. Поэтому современная атрибуция говорит о теореме Вильсона—Лагранжа, хотя в учебниках закрепилось имя Вильсона. Идея опирается на существование обратных элементов в поле вычетов по простому модулю.
Современная запись через факториал стала стандартным примером связи арифметики сравнений и простоты числа. Исторически важно различать автора наблюдения и автора доказательства, поскольку публикация появилась позже устной формулировки. В вычислительной теории критерий сохраняет значение как точная характеристика, даже когда для практического тестирования выбирают алгоритмы с полиномиальной или вероятностной сложностью.
Историческая линия формулы
Наблюдение связывают с Джоном Вильсоном; опубликованное доказательство дал Жозеф-Луи Лагранж в 1771 году. Поэтому корректна атрибуция Вильсон—Лагранж, а не утверждение об одном авторе всей теоремы. Такое уточнение отделяет историческое наблюдение от опубликованного доказательства.
Пример
Проверим p=5. Последовательно получаем r=1; после умножения на 2: r=2; на 3: r=6 mod 5=1; на 4: r=4. Так как p−1=4, равенство выполнено, и 5 простое. Для p=6: (p−1)!=120, а 120 mod 6=0, тогда как −1 mod 6=5; критерий отвергает 6. Остатки безразмерны, потому что это классы вычетов, а не физические величины. Полный факториал быстро растёт, но взятие модуля сохраняет эквивалентный класс; проверка p=7 даёт 6! mod 7=6. Дополнительно можно проверить p=11: вычисление по шагам даёт остаток 10, совпадающий с −1 mod 11; это ещё один независимый маленький пример.
Частая ошибка
Нельзя считать, что равенство нужно проверять для любого модуля: это критерий именно для p>1. Остаток −1 записывают как p−1, иначе сравнение с неотрицательным результатом цикла выглядит ошибочным. Не следует путать теорему Вильсона с интервалом Вильсона в статистике. Наконец, линейная стоимость делает критерий учебным для больших чисел, а не промышленным тестом простоты.
Практика
Задачи с решением
Проверка p=7
Условие. Найдите 6! mod 7 и решите, проходит ли число 7 критерий Вильсона.
Решение. 6!=720; 720 mod 7=6, а −1 mod 7=6.
Ответ. Да, 7 простое.
Отсев p=8
Условие. Сравните 7! mod 8 с −1 mod 8.
Решение. 7! содержит множители 2 и 4, поэтому 7! mod 8=0; −1 mod 8=7.
Ответ. Равенство не выполнено, 8 составное.
Дополнительные источники
- https://encyclopediaofmath.org/wiki/Wilson_theorem
- https://mathworld.wolfram.com/WilsonsTheorem.html
Связанные формулы
Математика
Критерий Эйлера для квадратичных вычетов
Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.
Математика
Малая теорема Ферма: степени по простому модулю
Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.
Математика
Обратный элемент по модулю через расширенный алгоритм Евклида
Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Математика
Быстрое возведение в степень по модулю двоичным методом
Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.