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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Из теоремы следует:n простое тогда и только тогда, когда \sin(((n-1)!+1)~\pi/n)=0,

а также число Вильсона

Пример[править | править вики-текст]

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

Таблица остатков по модулю n
n (n-1)! (n-1)!\ \bmod\ n
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 265252859812191000000000000000000 30

Доказательство[править | править вики-текст]

Применение[править | править вики-текст]

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

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

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

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}.

В результате

\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, следовательно

\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)! на произведение n1n2...nk всех чисел, меньших n и взаимно простых с n, не проходит: в случае n=8 это произведение равно 1*3*5*7=105, а 106 на 8 не делится. Но оказывается, что или n1n2...nk+1, или n1n2...nk-1 обязательно делится на n.

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

Назовем элемент a группы En особым, если aa=1. В этом случае элемент n-a - тоже особый. Следовательно, группа En содержит четное число особых элементов: (a,n-a) - множество таких элементов, и никакой элемент не может быть парой сам для себя. Пусть n1,n2,...,nk - все элементы группы En, то есть полный набор чисел, меньших n и взаимно простых с n. Множество элементов, не являющихся особыми, разбивается на пары взаимно обратных, поэтому произведение таких элементов равно 1. С другой стороны, произведение особых элементов, составляющих пару (a,n-a), равно n-1. Поскольку (n-1)(n-1)=1, то произведение всех особых элементов равно 1 или n-1, в зависимости от того, четным или нечетным является число пар вида (a,n-a).


Впервые теорема была доказана и обобщена Гауссом, при любом 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 году. В своем сочинении "Meditationes Algebraicae", опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику Вильсону (англ.). Доказательство теоремы он опубликовал только в третьем издании своего Medilationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем. Гаусс обобщил теорему Вильсона на случай составного модуля.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

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