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

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

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

История

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

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

Пример

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

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

$p$	$(p-1)!$	$(p-1)!modp$
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0
31	265252859812191058636308480000000	30
32	8222838654177922817725562880000000	0
33	263130836933693530167218012160000000	0
34	8683317618811886495518194401280000000	0
35	295232799039604140847618609643520000000	0
36	10333147966386144929666651337523200000000	0
37	371993326789901217467999448150835200000000	36

Применение

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

$1\cdot 2\cdots (p-1)\equiv -1(\mathrm{mod}p).$

Для нечётного простого Шаблон:Nowrap, получаем

$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(\mathrm{mod}p).$

В результате

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

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

$(\prod _{j=1}^{2k}j{)}^2=\prod _{j=1}^{2k}{j}^2\equiv (-1{)}^{2k+1}=-1(\mathrm{mod}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, имеет место сравнение:

$\prod _{\genfrac{}{}{0ex}{}{k=1}{(k,n)=1}}^{n}k\equiv \{\begin{array}{cc}-1(\mathrm{mod}n),& n=4,p^{\alpha },2p^{\alpha };\\ 1(\mathrm{mod}n),& n\ne 4,p^{\alpha },2p^{\alpha },\end{array}$

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

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

$(p-m)!*(m-1)!\equiv (-1{)}^m(\mathrm{mod}p)$

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

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

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

и

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

См. также

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

Литература

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