Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

Теорема Вильсона — теорема теории чисел, которая утверждает,что
 Эта теорема в основном имеет теоретическое значение, поскольку довольнотрудно вычислить факториал (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).
 В результате

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

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

Обобщение


 Используя в качестве образца теорему Эйлера, попытаемся обобщить теоремуВильсона на случай p=n, где n — произвольное натуральноечисло. Простая замена (p-1)! на произведениеn\textsubscript1n\textsubscript2\ldotsn\textsubscriptkвсех чисел, меньших n и взаимно простых с n, не проходит:в случае n=8 это произведение равно 1*3*5*7=105, а 106 на 8 неделится. Но оказывается, что илиn\textsubscript1n\textsubscript2\ldotsn\textsubscriptk+1,илиn\textsubscript1n\textsubscript2\ldotsn\textsubscriptk−1обязательно делится на n.
 Рассмотрим множество E\textsubscriptn чисел, меньших nи взаимно простых с n. Под произведением двух элементов этогомножества ab, будем понимать остаток от деления обычногопроизведения ab на 'n'. Ясно, что если a, b принадлежитE\textsubscriptn, то ab принадлежитE\textsubscriptn. Множество E\textsubscriptnотносительно операции умножения является группой. В отличие от случая,когда n — простое, группа E\textsubscriptn можетсодержать элементы, не равные 1 и (n-1) такие, что их квадратравен 1: например если n=8, то 3*3=1, 5*5=1,7*7=1. Поэтому в общем случае произведение всех элементов изE\textsubscriptn не равно (n-1). Покажем, что тогдаоно равно 1.
 Назовем элемент a группы E\textsubscriptn особым, еслиaa=1. В этом случае элемент n-a — тоже особый.Следовательно, группа E\textsubscriptn содержит четное числоособых элементов: (a, n-a) — множество таких элементов, иникакой элемент не может быть парой сам для себя. Пустьn\textsubscript1,n\textsubscript2,\ldots,n\textsubscriptk —все элементы группы E\textsubscriptn, то есть полный наборчисел, меньших 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 \{ne4,\{;p\^\{alpha,\{;2p\^\{alpha\{,, \{end\{cases\} где p — нечётное простое число,α — натуральный показатель.

История


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