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

редактировать

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

{\ Displaystyle (п-1)! \ \ эквив \; - 1 {\ pmod {п}}}

{\ Displaystyle (п-1)! \ \ эквив \; - 1 {\ pmod {п}}}

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

СОДЕРЖАНИЕ

1 История
2 Пример
3 Доказательства
- 3.1 Композитный модуль
- 3.2 Основной модуль упругости
  - 3.2.1 Элементарное доказательство
  - 3.2.2 Доказательство с использованием малой теоремы Ферма
  - 3.2.3 Доказательство с использованием теорем Силова
  - 3.2.4 Доказательство с использованием первообразных корней
4 Приложения
- 4.1 Тесты на первичность
- 4.2 Квадратичные вычеты
- 4.3 Формулы для простых чисел
- 4.4 p-адическая гамма-функция
5 обобщение Гаусса
6 См. Также
7 Примечания
8 ссылки
9 Внешние ссылки

История

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

Пример

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

Таблица факториала и его остаток по модулю n
${\ displaystyle n}$ $п$	${\ Displaystyle (п-1)!}$ $(п-1)!$ (последовательность A000142 в OEIS )	${\ Displaystyle (п-1)! \ {\ bmod {\}} п}$ $(п-1)! \ \ bmod \ п$ (последовательность 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 составное, оно делится на некоторое простое число q, где 2 ≤ q ≤ n - 2. Потому что делит, пусть на какое-то целое. Предположим для противодействия, что ( n - 1)! были сравнимы с −1 (mod n), где n составное. Тогда (n-1)! также будет конгруэнтно −1 (mod q), что означает, что для некоторого целого числа, которое показывает (n-1)! конгруэнтно -1 (mod q). Но ( n - 1)! ≡ 0 (mod q) тем, что q - член в (n-1)! изготовление (n-1)! кратное q. Получено противоречие. ${\ displaystyle q}$ $q$ ${\ displaystyle n}$ $п$ ${\ displaystyle n = qk}$ ${\ displaystyle n = qk}$ ${\ displaystyle k}$ $k$ ${\ Displaystyle (п-1)! \ эквив -1 \ ({\ текст {mod}} \ п)}$ ${\ Displaystyle (п-1)! \ эквив -1 \ ({\ текст {mod}} \ п)}$ ${\ Displaystyle (п-1)! = нм-1 = (qk) м-1 = q (км) -1}$ ${\ Displaystyle (п-1)! = нм-1 = (qk) м-1 = q (км) -1}$ ${\ displaystyle m}$ $м$

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

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

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

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

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

{\ Displaystyle 10! = [(1 \ CDOT 10)] \ CDOT [(2 \ CDOT 6) (3 \ CDOT 4) (5 \ CDOT 9) (7 \ CDOT 8)] \ эквив [-1] \ CDOT [1 \ cdot 1 \ cdot 1 \ cdot 1] \ Equiv -1 {\ pmod {11}}.}

{\ Displaystyle 10! = [(1 \ CDOT 10)] \ CDOT [(2 \ CDOT 6) (3 \ CDOT 4) (5 \ CDOT 9) (7 \ CDOT 8)] \ эквив [-1] \ CDOT [1 \ cdot 1 \ cdot 1 \ cdot 1] \ Equiv -1 {\ pmod {11}}.}

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

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

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

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

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

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

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

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

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

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

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

{\ Displaystyle 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). Это теорема Вильсона.

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

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

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

(п-2)! \ Equiv 1 {\ pmod p}.

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

{\ Displaystyle (п-1)! \ эквив п-1 \ экв-1 {\ pmod {р}},}

(р-1)! \ эквив р-1 \ эквив -1 {\ пмод р},

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

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

Пусть быть первообразный корень из р. Тогда и все остальные имеют обратное мультипликативное значение, потому что. Как пробегает все целые числа взаимно простые с р, мы сделали. ${\ Displaystyle а ^ {\ гидроразрыва {p-1} {2}} \ Equiv -1 {\ pmod {p}}}$ ${\ Displaystyle а ^ {\ гидроразрыва {p-1} {2}} \ Equiv -1 {\ pmod {p}}}$ ${\ Displaystyle а ^ {к}}$ $а ^ {к}$ ${\ displaystyle a ^ {pk-1}}$ ${\ displaystyle a ^ {pk-1}}$ ${\ displaystyle a ^ {k} a ^ {pk-1} = a ^ {p-1} \ Equiv 1 {\ pmod {p}}}$ ${\ displaystyle a ^ {k} a ^ {pk-1} = a ^ {p-1} \ Equiv 1 {\ pmod {p}}}$ ${\ Displaystyle а ^ {к}}$ $а ^ {к}$

Приложения

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

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

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

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

{\ Displaystyle 1 \ CDOT 2 \ CDOTS (п-1) \ \ Equiv \ -1 \ {\ pmod {p}}}

1 \ cdot 2 \ cdots (p-1) \ \ Equiv \ -1 \ \ pmod {p}

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

{\ Displaystyle 1 \ CDOT (п-1) \ CDOT 2 \ CDOT (р-2) \ CDOTS м \ CDOT (PM) \ \ Equiv \ 1 \ CDOT (-1) \ CDOT 2 \ CDOT (-2) \ cdots m \ cdot (-m) \ \ Equiv \ -1 {\ pmod {p}}.}

1 \ cdot (p-1) \ cdot 2 \ cdot (p-2) \ cdots m \ cdot (pm) \ 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}}}

\ prod_ {j = 1} ^ m \ j ^ 2 \ \ Equiv (-1) ^ {m + 1} \ pmod {p}

или

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

(м!) ^ 2 \ Equiv (-1) ^ {м + 1} \ pmod {p}.

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

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

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

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

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

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

Гаусс доказал, что

{\ displaystyle \ prod _ {k = 1 \ attop \ gcd (k, m) = 1} ^ {m} \! \! k \ \ Equiv {\ begin {cases} -1 {\ pmod {m}} amp; {\ text {if}} m = 4, \; p ^ {\ alpha}, \; 2p ^ {\ alpha} \\\; \; \, 1 {\ pmod {m}} amp; {\ text {иначе }} \ end {case}}}

{\ displaystyle \ prod _ {k = 1 \ attop \ gcd (k, m) = 1} ^ {m} \! \! k \ \ Equiv {\ begin {cases} -1 {\ pmod {m}} amp; {\ text {if}} m = 4, \; p ^ {\ alpha}, \; 2p ^ {\ alpha} \\\; \; \, 1 {\ pmod {m}} amp; {\ text {иначе }} \ end {case}}}

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

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

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

Примечания

использованная литература

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

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

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

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