Теорема Вильсона¶

Теорема Вильсона — классическое утверждение теории чисел, устанавливающее необходимое и достаточное условие простоты натурального числа. В современной формулировке теорема гласит: натуральное число \(n > 1\) является простым тогда и только тогда, когда \((n-1)! \equiv -1 \pmod{n}\).

Иными словами, факториал числа, предшествующего данному, при делении на само это число даёт остаток \(n-1\) в том и только в том случае, если число простое. Для составных чисел это сравнение не выполняется.

¶История

Теорема была впервые опубликована английским математиком Эдвардом Уорингом в 1770 году в его труде «Meditationes Algebraicae». Уоринг приписал открытие своему ученику, Джону Вильсону, в честь которого утверждение и получило своё название. Однако ни Вильсон, ни Уоринг не смогли привести строгого доказательства. Первое доказательство было дано Жозефом Луи Лагранжем в 1771 году. Лагранж также показал, что обратное утверждение (если выполняется сравнение, то число простое) также верно, что превратило теорему в критерий простоты.

Существуют свидетельства, что теорема была известна ещё Готфриду Вильгельму Лейбницу за столетие до публикации Уоринга, однако он не опубликовал своих заметок.

¶Доказательство

¶Необходимость (для простого \(p\))

Рассмотрим поле вычетов \(\mathbb{Z}_p\). Для простого \(p\) каждый ненулевой элемент \(a\) (где \(1 \le a \le p-1\)) имеет единственный обратный элемент \(a^{-1}\) по модулю \(p\). Сравнение \(a \equiv a^{-1} \pmod{p}\) выполняется только для \(a = 1\) и \(a = p-1\), поскольку это эквивалентно \(a^2 \equiv 1 \pmod{p}\), то есть \((a-1)(a+1) \equiv 0 \pmod{p}\).

Таким образом, в произведении \(1 \cdot 2 \cdot \ldots \cdot (p-1)\) все элементы, кроме 1 и \(p-1\), разбиваются на пары взаимно обратных, произведение которых сравнимо с 1 по модулю \(p\). Следовательно, \((p-1)! \equiv 1 \cdot (p-1) \equiv -1 \pmod{p}\).

¶Достаточность (для составного \(n\))

Если \(n\) составное и \(n > 4\), то \(n\) имеет собственный делитель \(d\), такой что \(1 < d < n\). Этот делитель \(d\) входит в произведение \((n-1)!\). Если \(d \ne n/d\), то оба сомножителя присутствуют в факториале, и произведение делится на \(n\). Если же \(n = d^2\) (то есть \(n\) — квадрат простого числа), то \(d\) и \(2d\) входят в \((n-1)!\) (так как \(2d \le n-1\) для \(n > 4\)), и их произведение делится на \(n\). В обоих случаях \((n-1)! \equiv 0 \pmod{n}\), что не сравнимо с \(-1\) по модулю \(n\). Для \(n = 4\) проверяется непосредственно: \(3! = 6 \equiv 2 \pmod{4}\).

¶Свойства и следствия

Теорема Вильсона лежит в основе нескольких важных утверждений теории чисел:

Критерий простоты: хотя теоретически теорема даёт строгий тест на простоту, вычисление факториала для больших \(n\) требует \(O(n)\) операций, что делает её практическое применение неэффективным по сравнению с современными алгоритмами (например, тестом Миллера — Рабина).
Сравнение для простых чисел: из теоремы следует, что для простого \(p\) выполняется \((p-2)! \equiv 1 \pmod{p}\), так как \((p-1)! = (p-1)(p-2)! \equiv -1 \pmod{p}\).
Квадратичные вычеты: теорема используется при доказательстве критерия Эйлера и в исследованиях, связанных с символом Лежандра.

¶Обобщения

Существует несколько обобщений теоремы Вильсона:

Обобщение Гаусса: для любого натурального \(n > 2\) произведение всех положительных чисел, меньших \(n\) и взаимно простых с \(n\), сравнимо с \(-1\) по модулю \(n\), если \(n = 4, p^k\) или \(2p^k\) (где \(p\) — нечётное простое), и с \(+1\) в противном случае.
Теорема Вильсона для конечных полей: произведение всех ненулевых элементов конечного поля \(\mathbb{F}_q\) равно \(-1\) в этом поле.
p-адические обобщения: существуют результаты, связывающие факториалы с p-адическими гамма-функциями.

¶Применение

В практической математике теорема Вильсона находит ограниченное применение из-за вычислительной сложности факториала. Однако она используется:

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

¶Интересные факты

Теорема Вильсона является одним из немногих утверждений, которые дают одновременно необходимое и достаточное условие простоты, не требующее перебора делителей.
Для числа \(p = 563\) вычисление \((p-1)!\) вручную невозможно, однако теорема позволяет утверждать, что остаток от деления на 563 равен 562, что подтверждает простоту числа.
В 1938 году Лео Мозер предложил использовать теорему Вильсона для построения генератора псевдослучайных чисел, однако метод не получил распространения.