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

Теорема Вильсона: факториал по простому модулю

Целое число p>1 простое тогда и только тогда, когда (p−1)! ≡ −1 (mod p). Для простого p каждый множитель 1,…,p−1 имеет обратный по модулю p, и почти все пары взаимно сокращаются; остаются только 1 и p−1.

Опубликовано: Обновлено:

Формула

$$p\text{ простое}\iff(p-1)!\equiv-1\pmod p$$
Схема Обратные пары для простого модуля 7
6! по модулю 72 × 4 ≡ 13 × 5 ≡ 11 × 6 ≡ 61 × 1 × 6 ≡ 6 ≡ −1 (mod 7)

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) слишком велика и используется только для небольших кандидатов.

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

  1. Проверьте, что p — целое число больше 1, и задайте остаток r=1 перед началом цикла.
  2. Для k от 2 до p−1 умножайте r на k и заменяйте r остатком r mod p, сохраняя только небольшой остаток.
  3. После цикла сравните r с p−1, то есть с остатком −1 по модулю p в неотрицательном представителе.
  4. Если r=p−1, критерий подтверждает простоту p; если r отличается, p составное и равенство не выполнено.
  5. Для доказательства вручную сгруппируйте ненулевые остатки с их обратными элементами и отдельно найдите решения x²≡1.
  6. Для больших 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

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

Математика

Критерий Эйлера для квадратичных вычетов

$\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p,\qquad \left(\frac ap\right)\in\{-1,0,1\}$

Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.

Математика

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

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

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

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

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

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

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