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

---

Если ${\displaystyle p}$ — простое число, то число ${\displaystyle (p-1)!+1}$ делится на ${\displaystyle p}$. Обратно: если ${\displaystyle (p-1)!+1}$ делится на ${\displaystyle p}$, то ${\displaystyle p}$ — простое число.

Эта теорема, в основном, имеет теоретическое значение, поскольку факториал ${\displaystyle (p-1)!}$ вычислить довольно трудно. Проще вычислить ${\displaystyle a^{p-1}}$, поэтому элементарные тесты, определяющие, является ли число простым, основаны на теореме Ферма, а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту ${\displaystyle p!}$ потребуется около суток вычислений на процессорах SPARC, а числа с десятками тысяч цифр проходят тест на простоту с использованием теоремы Ферма меньше чем за час. Но, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием для простоты.

Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 1000 г.н.э,^[1] и в 1770 году Варинг сформулировал эту теорему в своём сочинении «Meditationes Algebraicae», опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику Вильсону^[англ.]. Доказательство теоремы он опубликовал только в третьем издании своего Meditationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем^[2].

Наконец, Эйлер в «Opusc. Analyt», Т. 1, р. 329 дал доказательство, Гаусс обобщил теорему Вильсона на случай составного модуля. Имеются данные о том, что Лейбниц знал о результате ещё столетием раньше, но никогда не публиковал его.

В таблице посчитаны значения ${\displaystyle (p-1)!}$ для p от 2 до 31, а также остаток от деления ${\displaystyle (p-1)!}$ на p (остаток от деления m на p обозначается как m mod p). Зелёным цветом выделены простые числа.

---