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

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

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

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

Эта теорема в основном имеет теоретическое значение, поскольку довольно трудно вычислить факториал (p-1)!. Проще вычислить a^{p-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 (англ.)
  • Ore, O. Number Theory and its History. McGraw-Hill, 1948.
  • Бончковский Р. Н. и Чистяков И. И. Математическое просвещение, выпуск 01