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

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

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

Пример


 В таблице посчитаны значения (n-1)! для n от 2 до 31, а также остаток от деления (n-1)! на n (остаток от деления m на n обозначается как m mod n). Зелёным цветом выделены простые числа.
n(n1)!(n1)! mod n
211
322
462
5244
61200
77206
850400
9403200
103628800
11362880010
12399168000
1347900160012
1462270208000
15871782912000
1613076743680000
172092278988800016
183556874280960000
19640237370572800018
201216451004088320000
2124329020081766400000
22510909421717094400000
23112400072777760768000022
24258520167388849766400000
256204484017332394393600000
26155112100433309859840000000
274032914611266056355840000000
28108888694504183521607680000000
2930488834461171386050150400000028
3088417619937397019545436160000000
3126525285981219100000000000000000030

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


Применение


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

12(p1)  1 (modp)
  Для нечётного простого , получаем

1(p1)2(p2)m(pm)  1(1)2(2)m(m)  1(modp).
  В результате

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

(j=12k j)2=j=12k j2 (1)2k+1 =1(modp).
  Теорема Вильсона используется для генерирования простых чисел, но она слишком медленная для практического применения.

Обобщение


 Используя в качестве образца теорему Эйлера, попытаемся обобщить теорему Вильсона на случай p=n, где n — произвольное натуральное число. Простая замена (p-1)! на произведение n1n2\ldotsnk всех чисел, меньших n и взаимно простых с n, не проходит: в случае n=8 это произведение равно 1*3*5*7=105, а 106 на 8 не делится. Но оказывается, что или n1n2\ldotsnk+1, или n1n2\ldotsnk−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,\ldots,nk — все элементы группы En, то есть полный набор чисел, меньших n и взаимно простых с n. Множество элементов, не являющихся особыми, разбивается на пары взаимно обратных, поэтому произведение таких элементов равно 1. С другой стороны, произведение особых элементов, составляющих пару (a, n-a), равно n-1. Поскольку (n-1)(n-1)=1, то произведение всех особых элементов равно 1 или n-1, в зависимости от того, четным или нечетным является число пар вида (a, n-a).
 Впервые теорема была доказана и обобщена Гауссом, при любом n\textgreater2 для произведения всех натуральных чисел, не превосходящих 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 — нечётное простое число, α — натуральный показатель.

История


 Теорема впервые была сформулирована Уорингом в 1770 году. В своём сочинении «Meditationes Algebraicae», опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику . Доказательство теоремы он опубликовал только в третьем издании своего Medilationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем. Гаусс обобщил теорему Вильсона на случай составного модуля.