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

Теорема Вильсона — теорема теории чисел, которая утверждает, что

Натуральное число $p>1$ является простым тогда и только тогда, когда $(p-1)!+1$ делится на p.

Практическое использование теоремы Вильсона для определения простоты числа нецелесообразно из-за сложности вычисления факториала.

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

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

Необходимость

Пусть p - простое.

Способ 1.

Рассмотрим $(p-1)!$. Множество ненулевых классов классов вычетов по простому модулю p по умножению $\mathbb{Z}_p^{\times}$ является группой, и тогда $(p-1)!$ - это произведение всех элементов группы $\mathbb{Z}_p^{\times}$. Поскольку $\mathbb{Z}_p^{\times}$ - группа, то для каждого ее элемента $a$ существует единственный обратный элемент $a^{-1}: aa^{-1}\equiv 1 \pmod p$. Соответствие $a\to a^{-1}$ разбивает группу на классы: если $a= a^{-1}$ (что равносильно $a^2=1$, то есть $a \in \{1, -1\}$, поскольку у уравнения второй степени может быть не более двух решений), то класс содержит один элемент $a$, в противном случае класс состоит из двух элементов - $\{a,a^{-1}\}$. Значит, если класс содержит один элемент $a$, то произведение всех его элементов равно $a$, а если класс содержит 2 элемента, то произведение всех его элементов равно 1. Теперь в произведении $(p-1)!$ сгруппируем элементы по классам, все произведения по 2-хэлементным классам просто равны 1:

$(p-1)!\equiv\prod\limits_{a^2=1}a \cdot \prod\limits_{a^2\neq 1}a\equiv\prod\limits_{a^2=1}a\equiv1\cdot (-1)\equiv -1\pmod p.$

■

Способ 2.

Группа $\mathbb{Z}_p^{\times}$ циклична, т.е. существует элемент $g$ такой, что для всякого элемента $a$ существует $k$ такое, что $a=g^k$. Поскольку $\mathbb{Z}_p^{\times}$ имеет $p-1$ элемент, то $k$ пробегает значения от 0 до $p-1$, когда $a$ пробегает всю группу вычетов. Тогда

$(p-1)!\equiv g^1g^2\ldots g^{p-1}\equiv g^{1+2+\ldots+(p-1)}=g^{\frac{p-1}{2}p}\equiv (-1)^p\equiv -1\pmod p.$

■

Способ 3.

$\mathbb{Z}_p^{\times}$ - поле, поэтому в нем имеет место теорема Безу, т.е. многочлен степени $n$ имеет не более $n$ корней. Рассмотрим многочлены $f(x)=(x-1)\ldots(x-(p-1))$ и $g(x)=x^{p-1}-1$. Оба многочлена имеют корни $1,2,\ldots,p-1$ (для $g(x)$ это получается по малой теореме Ферма), степени многочленов равны $p-1$, старшие коэффициенты одинаковы. Тогда многочлен $h(x)=f(x)-g(x)$ имеет как минимум те же $p-1$ корней, но его степень не более $p-2$. Значит по теореме Безу $h(x)$ тождественно равен нулю, т.е. для всех $x$ будет $f(x)=g(x)$, в частности $f(0)=g(0)$, что равносильно $(-1)^{p-1}(p-1)!\equiv -1\pmod p$. Получаем утверждение теоремы для $p>2$, т.к. $p-1$ четно и значит $(-1)^{p-1}=1$.■

Достаточность

Если $n$ составное и $n\neq 4$, то $(n-1)!\equiv 0\pmod n$, а при $n=4$ получаем $(4-1)!\equiv 2\pmod 4$.

Обобщение

Как было впервые доказано Гауссом, при любом $n>2$ для произведения всех натуральных чисел, не превосходящих n и взаимно-простых с n, имеет место сравнение:

$\prod_{k = 1 \atop (k,n)=1}^{n} \!\!k \equiv \begin{cases} -1 \pmod{n}, & n=4,\;p^\alpha,\;2p^\alpha\, ;\\ \;\;\,1 \pmod{n}, & n \ne 4,\;p^\alpha,\;2p^\alpha\, , \end{cases}$

где $p$ — нечётное простое число, $\alpha$ — натуральный показатель.

История

Теорема впервые была сформулирована Уорингом в 1770 году и принадлежала, по его словам, Вильсону (англ.). Доказал её Лагранж в 1771 году.

См. также

• Мультипликативная группа кольца вычетов
• Теорема Вольстенхольма

Литература

• Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
• Трост Э. Простые числа, пер. с нем., М., 1959
• Виноградов И. М. Основы теории чисел. — 5 изд.. — М.-Л.: Гостехиздат, 1952.