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

В алгебре и теории чисел натуральное теорема Вильсона утверждает, что число n > 1 является простым числом тогда и только тогда, когда произведение всех натуральных чисел меньше n на единицу меньше, чем кратное n . То есть (используя обозначения модульной арифметики ) факториал $(n-1)!=1\times 2\times 3\times \cdots \times (n-1)$ удовлетворяет

$(n-1)!\ \equiv \;-1{\pmod {n}}$

именно тогда, когда n является простым числом. Другими словами, любое целое число n > 1 является простым числом тогда и только тогда, когда ( n − 1)! + 1 делится на n .

История

Теорема была впервые сформулирована Ибн аль-Хайсамом ок. 1000 год нашей эры . Эдвард Уоринг объявил об этой теореме в 1770 году, не доказав ее, отдав должное своему ученику Джону Уилсону за открытие. Лагранж дал первое доказательство в 1771 году. Есть свидетельства того, что Лейбниц также знал об этом результате столетием ранее, но никогда не публиковал его.

Пример

Для каждого значения n от 2 до 30 в следующей таблице показано число ( n − 1)! а остаток при ( n − 1)! делится на n . (В обозначениях модульной арифметики остаток от m деления на n записывается m mod n .) Цвет фона синий для простых значений n и золотой для составных значений.

Таблица факториала и его остатка по модулю n

$n$	$(n-1)!$ (последовательность A000142 в OEIS )	$(n-1)!\ {\bmod {\ }}n$ (последовательность A061006 в OEIS )
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

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

Как двуусловное утверждение (тогда и только тогда), доказательство состоит из двух частей: показать, что равенство не имеет места, когда $n$ является составным, и показать, что оно действительно выполняется, когда $n$ является простым.

Композитный модуль

Предположим, что $n$ является составным. Следовательно, оно делится на некоторое простое число $q$ где $2\leq q<n$. Потому что $q$ делит $n$, есть целое число $k$ такой, что $n=qk$. Предположим ради противоречия, что $(n-1)!$ были конгруэнтны $-1$ модуль ${n}$. Затем $(n-1)!$ также будет соответствовать $-1$ модуль ${q}$: действительно, если $(n-1)!\equiv -1{\pmod {n}}$ затем $(n-1)!=nm-1=(qk)m-1=q(km)-1$ для некоторого целого числа $m$, и, следовательно, $(n-1)!$ на единицу меньше кратного $q$. С другой стороны, поскольку $2\leq q\leq n-1$, один из факторов расширенного продукта $(n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1$ является $q$. Поэтому $(n-1)!\equiv 0{\pmod {q}}$. Это противоречие; поэтому невозможно, чтобы $(n-1)!\equiv -1{\pmod {n}}$ когда $n$ является составным.

На самом деле правда больше. За единственным исключением случая $n=4$, где $3!=6\equiv 2{\pmod {4}}$, если $n$ является составным, тогда $(n-1)!$ конгруэнтно 0 по модулю $n$. Доказательство можно разделить на два случая. Во-первых, если $n$ можно разложить на произведение двух неравных чисел: $n=ab$, где $2\leq a<b<n$, то оба $a$ и $b$ появятся как факторы в продукте $(n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1$ и так $(n-1)!$ делится на $ab=n$. Если $n$ не имеет такой факторизации, то это должен быть квадрат некоторого простого числа $q$ больше 2. Но тогда $2q<q^{2}=n$, так что оба $q$ и $2q$ будут факторами $(n-1)!$, и так $n$ делит $(n-1)!$ и в этом случае тоже.

Главный модуль

Первые два доказательства ниже используют тот факт, что классы вычетов по модулю простого числа являются конечным полем В статье « Простое поле» . - более подробную информацию см.

Элементарное доказательство

Результат тривиален, когда $p=2$, так что предположим $p$ является нечетным простым числом, $p\geq 3$. Поскольку классы вычетов по модулю $p$ образуют поле, каждый ненулевой остаток $a$ имеет уникальную мультипликативную обратную $a^{-1}$. Из леммы Евклида следует что единственные значения $a$ для чего $a\equiv a^{-1}{\pmod {p}}$ являются $a\equiv \pm 1{\pmod {p}}$. Поэтому, за исключением $\pm 1$, факторы в развернутой форме $(p-1)!$ можно разложить по непересекающимся парам так, чтобы произведение каждой пары было конгруэнтно 1 по модулю. $p$. Это доказывает теорему Вильсона.

Например, для $p=11$, у одного есть $$10!=[(1\cdot 10)]\cdot [(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)]\equiv [-1]\cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1{\pmod {11}}.$$

Доказательство с использованием малой теоремы Ферма.

Опять же, результат тривиален для p = 2, поэтому предположим, что p — нечетное простое число, p ≥ 3 . Рассмотрим полином

$g(x)=(x-1)(x-2)\cdots (x-(p-1)).$

g имеет степень p − 1 , старший член x ^{п - 1} и постоянный член ( p − 1)! . Его p − 1 корни равны 1, 2, ..., p − 1 .

Теперь рассмотрим

$h(x)=x^{p-1}-1.$

h также имеет степень p − 1 и старший член x ^{п - 1} . По модулю маленькая p теорема Ферма гласит, что он также имеет те же корни p − 1 , 1, 2, ..., p − 1 .

Наконец, рассмотрим

$f(x)=g(x)-h(x).$

f имеет степень не выше p − 2 (поскольку старшие члены сокращаются), а по модулю p также имеет p − 1 корней 1, 2, ..., p − 1 . Но теорема Лагранжа гласит, что оно не может иметь более p − 2 корней. Следовательно, f должен быть тождественно нулю (mod p ), поэтому его постоянный член равен ( p − 1)! + 1 ≡ 0 (мод п ) . Это теорема Вильсона.

Доказательство с использованием теорем Силова.

Теорему Вильсона можно вывести из частного применения теорем Силова . Пусть p — простое число. Сразу видно, что симметрическая группа $S_{p}$ имеет точно $(p-1)!$ элементы порядка p , а именно p -циклы $C_{p}$. С другой стороны, каждая силовская p -подгруппа в $S_{p}$ является копией $C_{p}$. Отсюда следует, что число силовских p -подгрупп равно $n_{p}=(p-2)!$. Из третьей теоремы Силова следует

$(p-2)!\equiv 1{\pmod {p}}.$

Умножение обеих частей на ( p − 1) дает

$(p-1)!\equiv p-1\equiv -1{\pmod {p}},$

то есть результат.

Приложения

Тесты на примитивность

На практике теорема Вильсона бесполезна как критерий простоты, поскольку вычисление ( n − 1)! по модулю n для больших n является вычислительно сложным , и известны гораздо более быстрые тесты на простоту (действительно, даже пробное деление значительно более эффективно).

Если использовать его в другом направлении, для определения простоты потомков больших факториалов, это действительно очень быстрый и эффективный метод. Однако это имеет ограниченную полезность.

Квадратичные остатки

Используя теорему Вильсона, для любого нечетного простого числа p = 2 m + 1 мы можем переставить левую часть $$1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}$$ чтобы получить равенство $$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}}$$ или $$(m!)^{2}\equiv (-1)^{m+1}{\pmod {p}}.$$ Мы можем использовать этот факт, чтобы доказать часть известного результата: для любого простого числа p такого, что p ≡ 1 (mod 4) , число (−1) является квадратом ( квадратичным вычетом ) по модулю p . Для этого предположим, что p = 4k + 1 для некоторого целого числа k . Тогда мы можем взять m = 2 k выше и сделать вывод, что ( m !) ² конгруэнтно (−1) (mod p ).

Формулы для простых чисел

Теорема Вильсона использовалась для построения формул для простых чисел , но они слишком медленны, чтобы иметь практическую ценность.

p-адическая гамма-функция

Теорема Вильсона позволяет определить p-адическую гамма-функцию .

Обобщение Гаусса

Гаусс доказал что $$\prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}$$ где p представляет собой нечетное простое число, а $\alpha$ положительное целое число. То есть произведение натуральных чисел, меньших m и относительно простых по отношению к m, на единицу меньше, чем кратное m , когда m равно 4, или степени нечетного простого числа, или вдвое большей степени нечетного простого числа; в противном случае произведение на единицу больше, чем кратное m . Значения m, для которых произведение равно −1, — это именно те значения, в которых существует примитивный корень по модулю m .

См. также

• Уилсон Прайм
• Таблица сравнений

Ссылки

« Disquisitiones Arithmeticae» переведена с цицероновской латыни Гаусса на английский и немецкий языки. Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих; Кларк, Артур А. (1986), Disquisitiones Arithemeticae (2-е исправленное издание), Нью-Йорк: Springer , ISBN  0-387-96254-9 (переведено на английский) {{citation}}:CS1 maint:postscript ( ссылка ) .
• Гаусс, Карл Фридрих; Мазер, Х. (1965), Исследования по высшей арифметике (Disquisitiones Arithemeticae и другие статьи по теории чисел) (2-е изд.), Нью-Йорк: Челси, ISBN  0-8284-0191-8 (переведено на немецкий) {{citation}}:CS1 maint:postscript ( ссылка ) .
• Ландау, Эдмунд (1966), Элементарная теория чисел , Нью-Йорк: Челси .
• Оре, Эйстейн (1988). Теория чисел и ее история . Дувр. стр. 259–271 . ISBN  0-486-65620-9 .

Внешние ссылки

• «Теорема Вильсона» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Теорема Вильсона» . Математический мир .
• системы Mizar Доказательство : http://mizar.org/version/current/html/nat_5.html#T22
• Оана, Эндрю. «Обобщение теоремы Вильсона» (PDF) .