Теорема Вильсона - NiNa.Az

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

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

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

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

История

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

Пример

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

Таблица остатков по модулю n

${\displaystyle p}$	${\displaystyle (p-1)!}$	${\displaystyle (p-1)!{\bmod {p}}}$
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40 320	0
10	362 880	0
11	3 628 800	10
12	39 916 800	0
13	479 001 600	12
14	6 227 020 800	0
15	87 178 291 200	0
16	1 307 674 368 000	0
17	20 922 789 888 000	16
18	355 687 428 096 000	0
19	6 402 373 705 728 000	18
20	121 645 100 408 832 000	0
21	2 432 902 008 176 640 000	0
22	51 090 942 171 709 440 000	0
23	1 124 000 727 777 607 700 000	22
24	25 852 016 738 884 980 000 000	0
25	620 448 401 733 239 400 000 000	0
26	15 511 210 043 330 986 000 000 000	0
27	403 291 461 126 605 650 000 000 000	0
28	10 888 869 450 418 352 000 000 000 000	0
29	304 888 344 611 713 870 000 000 000 000	28
30	8 841 761 993 739 702 000 000 000 000 000	0
31	265 252 859 812 191 070 000 000 000 000 000	30
32	8 222 838 654 177 922 000 000 000 000 000 000	0
33	263 130 836 933 693 500 000 000 000 000 000 000	0
34	8 683 317 618 811 886 000 000 000 000 000 000 000	0
35	295 232 799 039 604 160 000 000 000 000 000 000 000	0
36	10 333 147 966 386 145 000 000 000 000 000 000 000 000	0
37	371 993 326 789 901 250 000 000 000 000 000 000 000 000	36

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

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

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

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

Способ 1

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

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

■

Способ 2

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

${\displaystyle (p-1)!\equiv g^{1}g^{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

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

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

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

Геометрическое доказательство достаточности

1. Пусть p — простое число. Перенумеруем вершины правильного p-угольника в порядке обхода контура: 1, 2, 3, ..., p. Если соединим их диагоналями последовательно через одну, потом через две, через три и т. д., то кроме правильного многоугольника 123..., получим ещё (p − 2) многоугольников 135..., 147..., 159... и т. д. Эти (p − 1) многоугольников попарно тождественны, так как при соединении вершин через k и через (p − k − 2) получаем тождественные многоугольники. Число различных правильных многоугольников, полученных этим путём, равно ${\displaystyle (p-1)/2}$;
2. Если соединим вершины в каком-либо другом порядке, например в порядке 13245..., то получим неправильный многоугольник; повёртывая этот многоугольник так, чтобы номера его вершин заменялись следующими по порядку числами (число p заменяется при этом единицей), получим p неправильных многоугольников. В вышеуказанном примере это будут многоугольники 13245..., 24356..., 35467..., ..., 2134... Если таким путём образуем все возможные неправильные многоугольники, то число их будет кратно p, но, как и в случае правильных многоугольников, они по два тождественны; именно две последовательности вершин, прямая и обратная, дают один и тот же многоугольник;
3. Если в последовательности вершин 123... сделать все возможные перестановки (p − 1) вершин 23..., то получим все возможные (правильные и неправильные) многоугольники; их число будет равно ${\displaystyle 1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'}$; они опять будут попарно тождественны, так что действительное их число ${\displaystyle (p-1)!/2}$;
4. Сопоставляя результаты из пунктов 1 и 3, видим, что число неправильных многоугольников будет равно: ${\displaystyle 1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)}$. Из пункта 2, это число должно делиться на p; следовательно (p − 1)! + 1 кратно p.:■

Применение

• Используем теорему Вильсона

${\displaystyle 1\cdot 2\cdots (p-1)\equiv -1{\pmod {p}}.}$

Для нечётного простого p = 2m + 1, получаем

${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\equiv -1{\pmod {p}}.}$

В результате

${\displaystyle \prod _{j=1}^{m}j^{2}\equiv (-1)^{m+1}{\pmod {p}}.}$

Мы можем использовать этот факт для доказательства известного результата: для любого простого p, такого что p ≡ 1 (mod 4) число (−1) является квадратом (квадратичный вычет) по модулю p. Действительно, пусть p = 4k + 1 для некоторого натурального k. Тогда m = 2k, следовательно

${\displaystyle {\biggl (}\prod _{j=1}^{2k}\ j{\biggr )}^{2}=\prod _{j=1}^{2k}j^{2}\equiv (-1)^{2k+1}=-1{\pmod {p}}.}$

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

Обобщение

Используя в качестве образца теорему Эйлера, попытаемся обобщить теорему Вильсона на случай p = n, где n — произвольное натуральное число. Простая замена (p − 1)! на произведение n₁n₂…n_k всех чисел, меньших n и взаимно простых с n, не проходит: в случае n = 8 это произведение равно 1 × 3 × 5 × 7 = 105, а 106 на 8 не делится. Но оказывается, что или n₁n₂…n_k + 1, или n₁n₂…n_k − 1 обязательно делится на n.

Рассмотрим множество E_n чисел, меньших n и взаимно простых с n. Под произведением двух элементов этого множества ab, будем понимать остаток от деления обычного произведения ab на n. Ясно, что если a, b принадлежит E_n, то ab принадлежит E_n. Множество E_n относительно операции умножения является группой. В отличие от случая, когда n — простое, группа E_n может содержать элементы, не равные 1 и (n − 1) такие, что их квадрат равен 1: например если n = 8, то 3 × 3 = 1, 5 × 5 = 1, 7 × 7 = 1. Поэтому в общем случае произведение всех элементов из E_n не равно (n − 1). Покажем, что тогда оно равно 1.

Назовем элемент a группы E_n особым, если aa = 1. В этом случае элемент n − a — тоже особый. Следовательно, группа E_n содержит чётное число особых элементов: (a, n − a) — множество таких элементов, и никакой элемент не может быть парой сам для себя. Пусть n₁, n₂, …, n_k — все элементы группы E_n, то есть полный набор чисел, меньших n и взаимно простых с n. Множество элементов, не являющихся особыми, разбивается на пары взаимно обратных, поэтому произведение таких элементов равно 1. С другой стороны, произведение особых элементов, составляющих пару (a, n − a), равно n − 1. Поскольку (n − 1)(n − 1) = 1, то произведение всех особых элементов равно 1 или n − 1, в зависимости от того, чётным или нечётным является число пар вида (a, n − a).■

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

${\displaystyle \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\neq 4,\;p^{\alpha },\;2p^{\alpha }\,,\end{cases}}}$

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

Позже было найдено ещё одно формальное обобщение теоремы Вильсона (В.Виноград):

${\displaystyle (p-m)!*(m-1)!\equiv (-1)^{m}{\pmod {p}}}$

При ${\displaystyle m=1}$ получается теорема Вильсона.

При ${\displaystyle m=\left({\frac {p+1}{2}}\right)}$ получается ${\displaystyle \left({\frac {p-1}{2}}\right)!^{2}+(-1)^{\left({\frac {p-1}{2}}\right)}\equiv 0{\pmod {p}}}$, т.е.

${\displaystyle \left({\frac {p-1}{2}}\right)!^{2}+1\equiv 0{\pmod {p}}}$, если ${\displaystyle p\equiv 1{\pmod {4}}}$

и

${\displaystyle \left({\frac {p-1}{2}}\right)!^{2}-1\equiv 0{\pmod {p}}}$, если ${\displaystyle p\equiv 3{\pmod {4}}}$

См. также

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

Примечания

1. Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Abu Ali al-Hasan ibn al-Haytham (англ.) — биография в архиве MacTutor.
2. Joseph Louis Lagrange, «Demonstration d’un théorème nouveau concernant les nombres premiers» Архивная копия от 11 мая 2022 на Wayback Machine (Proof of a new theorem concerning prime numbers), Nouveaux Mémoires de l’Académie Royale des Sciences et Belles-Lettres (Berlin), vol. 2, pages 125—137 (1771)

Литература

• Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
• Трост Э. Простые числа, пер. с нем., М., 1959
• Виноградов И. М. Основы теории чисел. — 5 изд.. — М.—Л.: Гостехиздат, 1952.
• R. Crandall, K. Dilcher and C. Pomerance The Prime Glossary (англ.)
• Ore, O. Number Theory and its History. McGraw-Hill, 1948.
• Бончковский Р. Н. и Чистяков И. И. Математическое просвещение, выпуск 01