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

Теорема Вильсона - компактный критерий простоты: число $p$ простое тогда и только тогда, когда $(p-1)! + 1$ делится на $p$. Это двусторонний критерий: в одну сторону он узнаёт простые, в другую - отсеивает составные. Утверждение угадал Лейбниц, переоткрыл Джон Вильсон в 1770-м, а первое доказательство дал Лагранж в 1771 году.

Формулировка

Теорема (Вильсон). Натуральное число $p \geq 2$ простое тогда и только тогда, когда

$$(p-1)! \equiv -1 \pmod{p}$$

Эквивалентная запись: $(p-1)! + 1 \equiv 0 \pmod{p}$, то есть «$(p-1)! + 1$ делится на $p$». Запись $-1$ удобнее, чем $p - 1$, - выражения получаются короче.

Проверим на маленьких числах:

• $p = 2$: $(2-1)! = 1 \equiv -1 \pmod 2$ - верно (так как $-1 \equiv 1 \pmod 2$).
• $p = 3$: $2! = 2 \equiv -1 \pmod 3$ - верно.
• $p = 5$: $4! = 24 = 5 \cdot 5 - 1$, то есть $24 \equiv -1 \pmod 5$ - верно.
• $p = 7$: $6! = 720 = 7 \cdot 103 - 1$, то есть $720 \equiv -1 \pmod 7$ - верно.
• $p = 4$ (составное): $3! = 6 \equiv 2 \pmod 4$ - не $-1$, как и должно быть.

Подставь своё $n$ ниже и сверь $(n-1)! \pmod n$ с правилом Вильсона - мы разберём, простое перед нами число или составное, и сразу проверим утверждение Гаусса для составных.

Прямое утверждение: как простые попадают в $-1$

Идея - спарить числа от $1$ до $p-1$ по обратным в $\mathbb{Z}/p\mathbb{Z}$. Когда $p$ простое, $\mathbb{Z}/p\mathbb{Z}$ - поле, и у каждого ненулевого $a$ есть единственный обратный $a^{-1}$: $a \cdot a^{-1} \equiv 1 \pmod p$.

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

В $(p-1)! = 1 \cdot 2 \cdots (p-1)$ пары для $a \in \{2, \ldots, p-2\}$ дают $1$. Остаются неспаренные $1$ и $p - 1 \equiv -1$. Итого $(p-1)! \equiv -1 \pmod p$.

На $p = 7$: $1$ и $6$ - самообратные; пары $\{2, 4\}$ ($2 \cdot 4 = 8 \equiv 1$) и $\{3, 5\}$ ($3 \cdot 5 = 15 \equiv 1$). Произведение - $6 \equiv -1 \pmod 7$.

Обратное утверждение: как теорема ловит составных

Это часть, которая делает теорему критерием. Пусть $n$ составное и $n > 4$. Покажем, что $(n-1)! \equiv 0 \pmod n$, то есть не $-1$.

Запишем $n = ab$, $1 < a \leq b < n$. Случай $a < b$: оба множителя $a$ и $b$ присутствуют среди $1, 2, \ldots, n-1$, поэтому $n = ab \mid (n-1)!$.

Особый случай $n = a^2$ при $a \geq 3$: тогда $2a \leq a^2 - 1$, и оба множителя $a$ и $2a$ есть в произведении, значит $a^2 \mid (n-1)!$.

Остаётся $n = 4$: $3! = 6 \equiv 2 \pmod 4$, не $0$ и не $-1$. Теорема всё равно отличает $4$ от простого (так как $2 \neq 3 \equiv -1 \pmod 4$), но «$(n-1)! \equiv 0$» здесь не работает.

Обобщение Гаусса для составных $n$

Гаусс уточнил картину. Для составного $n > 4$ верно сильное утверждение:

$$(n-1)! \equiv 0 \pmod{n}, \qquad n \text{ составное}, \; n > 4$$

Доказательство - как выше. Это означает, что разбиение по теореме Вильсона трёхступенчатое:

• $n = 1$: $(1-1)! = 0! = 1$, не подходит ни под одно правило (исключим $n = 1$ из формулировок).
• $n$ простое: $(n-1)! \equiv -1 \pmod n$.
• $n = 4$: $(n-1)! \equiv 2 \pmod n$ - единственное «странное» исключение.
• $n > 4$ составное: $(n-1)! \equiv 0 \pmod n$.

Полезно держать в голове именно эту таблицу - она объясняет, почему частое упрощение «остаток $-1 \Leftrightarrow$ простое, остаток $0 \Leftrightarrow$ составное» работает для всех $n$, кроме $4$.

Исторический контекст: Лейбниц, Вильсон, Лагранж

Формула упоминалась Лейбницем в неопубликованных заметках конца XVII века - он заметил закономерность, но не доказал. В 1770 году Джон Вильсон переоткрыл утверждение; его учитель Эдвард Уоринг опубликовал формулировку без доказательства, отметив, что «доказательство кажется трудным, так как нет обозначения для простых чисел». Через год Лагранж дал первое доказательство - через те же рассуждения об обратных. Эйлер позже передоказал теорему через свою теорию вычетов. Имя за теоремой закрепилось от Вильсона по традиции публикации.

Поэтому обратную часть («если $(p-1)! \equiv -1$, то $p$ простое») часто называют теоремой Лагранжа, хотя в учебниках оба направления собраны под общим именем. Не путать с одноимённой теоремой Лагранжа для групп - это другое утверждение того же автора.

Связь с малой теоремой Ферма

Малая теорема Ферма: для простого $p$ и $a \not\equiv 0 \pmod p$ выполнено $a^{p-1} \equiv 1 \pmod p$. Перемножая по всем $a = 1, \ldots, p-1$, получим $((p-1)!)^{p-1} \equiv 1$ - то есть $(p-1)!$ корень степени $p-1$ из единицы. Но таких корней в поле $\mathbb{F}_p$ ровно $p-1$ (все ненулевые элементы), поэтому Ферма сам по себе не выделяет $-1$. Это делает только спаривание. Ферма и Вильсон - соседние, но независимые: Ферма про отдельный $a$, Вильсон - про их полное произведение.

Почему это не практический тест простоты

Формально $(p-1)! \equiv -1 \pmod p$ - настоящий критерий (необходимое и достаточное условие). Но проблема - стоимость: чтобы посчитать $(p-1)! \pmod p$, нужно $p - 2$ умножений по модулю, то есть линейное по $p$ число операций. Современные тесты - Миллер-Рабин, AKS - работают за полилогарифмическое время $(\log p)^k$. Для числа с 1000 знаков ($p \sim 10^{1000}$) Миллер-Рабин делает $\sim 10^7$ операций, а Вильсон потребовал бы $10^{1000}$. Поэтому теорема Вильсона ценна именно теоретически - как критерий, как инструмент для тождеств с факториалами и как кирпич в доказательствах квадратичного закона взаимности.

Типовые задачи

Остаток факториала по простому модулю. Найти $30! \pmod{31}$. По теореме Вильсона $30! \equiv -1 \equiv 30 \pmod{31}$ - без всяких вычислений.

Остаток факториала «с дыркой». Найти $28! \pmod{31}$. Запишем $30! = 28! \cdot 29 \cdot 30$. По Вильсону $30! \equiv -1$, значит $28! \cdot 29 \cdot 30 \equiv -1$. В $\mathbb{Z}/31\mathbb{Z}$: $29 \equiv -2$, $30 \equiv -1$, так что $29 \cdot 30 \equiv 2$. Тогда $28! \equiv -1 \cdot 2^{-1} \equiv -16 \equiv 15 \pmod{31}$.

Различить простое и составное на маленьких $n$. Классическое упражнение и предлог для tool выше - посчитать $(n-1)! \pmod n$ для $n = 4, 6, 7, 8, 9, 11$ и убедиться, что $-1$ возникает только у $7$ и $11$.

Частые ошибки

• «Теорема Вильсона - хороший тест простоты». Нет, на больших $n$ вычисление $(n-1)!$ слишком дорого; используется только как теоретический критерий.
• Забывают исключение $n = 4$. В формуле «$(n-1)! \equiv 0$ для составных» $n = 4$ - единственный составной случай, для которого она не работает: $3! = 6 \equiv 2 \pmod 4$.
• Путают «$-1$» и «$0$». Для простых остаток $-1 \equiv n - 1$, для составных $> 4$ - $0$. Это два разных остатка, не одно и то же.
• Применяют без условия $p$ простое. Прямое утверждение использует, что $\mathbb{Z}/p\mathbb{Z}$ - поле (все ненулевые обратимы). На составных модулях это рассуждение ломается с первого шага.
• «$a^2 \equiv 1$ имеет два корня в любом кольце». Только в поле. В $\mathbb{Z}/8\mathbb{Z}$ корней четыре: $1, 3, 5, 7$ - именно поэтому теорема и не работает по составному модулю.

FAQ

Зачем теорема, если ей нельзя пользоваться как тестом? Она нужна как критерий в доказательствах (тождества с факториалами, шаги в доказательстве квадратичного закона взаимности), как красивое следствие свойств поля $\mathbb{F}_p$, и как простой источник задач на сравнения. Практическая проверка простоты - отдельный класс задач, который решается другими алгоритмами.

Есть ли аналог Вильсона для произвольных колец? Есть обобщение Гаусса для $(\mathbb{Z}/n\mathbb{Z})^\times$: произведение всех обратимых элементов по модулю $n$ равно $-1$ при $n = 1, 2, 4, p^k, 2p^k$ ($p$ - нечётное простое), и равно $1$ во всех остальных случаях. Для простого $p$ это и есть классический Вильсон.

Можно ли вычислять $(n-1)! \pmod n$ быстрее, чем за $n$ операций? Известны вычислительные приёмы (например, через разбиение на блоки и быстрое перемножение), доводящие до $O(\sqrt{n} \log n)$ или около того, но это всё равно куда хуже, чем $O((\log n)^k)$ у Миллера-Рабина. Принципиально полилогарифмического алгоритма для вычисления $(n-1)! \pmod n$ не известно.

Коротко

Теорема Вильсона: $n \geq 2$ простое $\iff (n-1)! \equiv -1 \pmod n$. Прямое направление - Вильсон/Уоринг; обратное и первое доказательство - Лагранж (1771). Доказывается спариванием обратных в поле $\mathbb{F}_p$: единственные самообратные элементы - $1$ и $-1$, остальные пары дают $1$, поэтому $(p-1)! \equiv 1 \cdot (-1) = -1$. Обобщение Гаусса: для составного $n > 4$ получаем $(n-1)! \equiv 0 \pmod n$; единственное исключение - $n = 4$ с остатком $2$. Тестом простоты не служит из-за линейной сложности по $n$ против полилогарифма у Миллера-Рабина. Используется в теории чисел как критерий и инструмент для тождеств с факториалом по простому модулю.