Теорема Вильсона - Wilsons theorem - Wikipedia

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

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

когда именно п простое число. Другими словами, любое число п является простым числом тогда и только тогда, когда (п - 1)! + 1 делится на п.^[1]

История

Эта теорема была сформулирована Ибн аль-Хайсам (ок. 1000 г. н.э.),^[2] а в 18 веке Джон Уилсон.^[3] Эдвард Уоринг объявил теорему в 1770 году, хотя ни он, ни его ученик Вильсон не смогли ее доказать. Лагранж дал первое доказательство в 1771 году.^[4] Есть свидетельства того, что Лейбниц также знал о результате столетием раньше, но никогда не публиковал его.^[5]

Пример

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

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

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

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

Оба приведенных ниже доказательства (для простых модулей) используют тот факт, что классы вычетов по модулю простого числа являются поле —Смотрите статью основное поле Больше подробностей.^[6] Теорема Лагранжа, который утверждает, что в любом поле a многочлен из степень п имеет самое большее п корни, требуется для обоих доказательств.

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

Если п составно делится на некоторое простое число q, куда 2 ≤ q ≤ п − 2. Если (п − 1)! соответствовали −1 (mod п) то оно также было бы конгруэнтно −1 (mod q). Но (п - 1)! ≡ 0 (модq).

На самом деле, правда больше. За исключением 4, где 3! = 6 ≡ 2 (mod 4), если п составно, то (п - 1)! конгруэнтно 0 (modп). Доказательство разбивается на два случая: во-первых, если п можно разложить на множители как произведение двух неравных чисел, п = ab, где 2 ≤а < б ≤ п - 2, затем оба а и б появится в продукте 1 × 2 × ... × (п − 1) = (п − 1)! и (п - 1)! будет делиться на п. Если п не имеет такой факторизации, то это должен быть квадрат некоторого простого q, q > 2. Но тогда 2q < q² = п, обе q и 2q будут факторы (п - 1) !, и снова п делит (п − 1)!.

Основной модуль

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

Результат тривиален, когда п = 2так что предположим п нечетное простое число, п ≥ 3. Поскольку классы вычетов (mod п) - поле, каждое ненулевое а имеет единственный мультипликативный обратный, а⁻¹. Теорема Лагранжа означает, что единственные значения а для которого а ≡ а⁻¹ (мод п) находятся а ≡ ± 1 (мод. п) (потому что соответствие а² ≡ 1 может иметь не более двух корней (mod п)). Следовательно, за исключением ± 1, множители (п − 1)! могут быть расположены неравными парами,^[7] где произведение каждой пары ≡ 1 (мод п). Это доказывает теорему Вильсона.

Например, если п = 11,

${\displaystyle 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}}.}$

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

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

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

грамм имеет степень п − 1, ведущий термин Икс^{п − 1}, и постоянный член (п − 1)!. Его п − 1 корни 1, 2, ..., п − 1.

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

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

час также имеет степень п − 1 и ведущий термин Икс^{п − 1}. По модулю п, Маленькая теорема Ферма говорит, что у него тоже есть п − 1 корни, 1, 2, ..., п − 1.

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

${\displaystyle f(x)=g(x)-h(x).}$

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

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

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

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

Умножая обе стороны на (п − 1) дает

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

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

Приложения

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

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

Квадратичные вычеты

Используя теорему Вильсона, для любого нечетного простого числа п = 2м + 1, мы можем переставить левую часть

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

чтобы получить равенство

${\displaystyle 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}}.}$

Это становится

${\displaystyle \prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}{\pmod {p}}}$

или же

${\displaystyle (m!)^{2}\equiv (-1)^{m+1}{\pmod {p}}.}$

Мы можем использовать этот факт, чтобы доказать часть известного результата: для любого простого числа п такой, что п ≡ 1 (мод.4) число (−1) представляет собой квадрат (квадратичный вычет ) мод п. Предположим п = 4k + 1 для некоторого целого числа k. Тогда мы можем взять м = 2k выше, и мы заключаем, что (м!)² конгруэнтно (−1).

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

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

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

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

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

Гаусс доказал, что^[8]

${\displaystyle \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}}}$

куда п представляет собой нечетное простое число и ${\displaystyle \alpha }$ положительное целое число. Ценности м для которых произведение равно −1, - это в точности те, для которых существует примитивный корень по модулю м.

Это далее обобщает тот факт, что в любом конечный абелева группа, либо произведение всех элементов является единицей, либо существует ровно один элемент а из порядок 2 (но не оба). В последнем случае произведение всех элементов равноа.

Смотрите также

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

Примечания

1. Универсальная книга математики. Дэвид Дарлинг, стр. 350.
2. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., «Абу Али аль-Хасан ибн аль-Хайтам», Архив истории математики MacTutor, Сент-Эндрюсский университет.
3. Эдвард Уоринг, Meditationes Algebraicae (Кембридж, Англия: 1770), стр. 218 (на латыни). В третьем (1782 г.) издании Уоринга Meditationes Algebraicae, Теорема Вильсона появляется как проблема 5 на стр. 380. На этой странице Уоринг заявляет: «Hanc maxime elegantem primorum numerorum proprietatem invenit vir claissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger». (Самый выдающийся и наиболее опытный в математике человек, сквайр Джон Уилсон, обнаружил это самое элегантное свойство простых чисел.)
4. Жозеф Луи Лагранж, "Demonstration d'un théorème nouveau Concernt les nombres premiers" (Доказательство новой теоремы о простых числах), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Берлин), т. 2, страницы 125–137 (1771).
5. Джованни Вакка (1899) "Sui manoscritti inediti di Leibniz" (О неопубликованных рукописях Лейбница),Bollettino di bibliografia e storia delle scienze matematiche ... (Вестник библиографии и истории математики), т. 2, страницы 113–116; видеть стр. 114 (на итальянском). Цитаты Вакки из математических рукописей Лейбница, хранящихся в Королевской публичной библиотеке в Ганновере (Германия), т. 3 Б, пачка 11, стр.10:

   Оригинал : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:
   
   «Productus continorum usque ad numerum qui antepraecedit datum divisus per datum reinquit 1 (vel complementum ad unum?) Si datus sit primitivus. Si datus sit Derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem».
   
   Egli non giunse pero a dimostrarlo.

   Перевод : Кроме того, он [Лейбниц] также ознакомился с теоремой Вильсона, как показано в следующем утверждении:
   
   "Произведение всех целых чисел, предшествующих данному целому числу, при делении на данное целое число, оставляет 1 (или дополнение к 1?), Если данное целое число является простым. Если данное целое число является составным, остается число, имеющее общее множитель с заданным целым числом, [которое] больше единицы ".
   
   Однако доказать это ему не удалось.

   См. Также: Джузеппе Пеано, изд., Formulaire de mathématiques, т. 2, вып. 3, стр. 85 (1897).
6. Ландау, два доказательства этого. 78
7. Когда п = 3, единственными множителями являются ± 1
8. Гаусс, Д.А., арт. 78

Рекомендации

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

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

внешняя ссылка

• «Теорема Вильсона», Энциклопедия математики, EMS Press, 2001 [1994]
• Вайсштейн, Эрик В. «Теорема Вильсона». MathWorld.
• Система Мицар доказательство: http://mizar.org/version/current/html/nat_5.html#T22