Теорема Вильсона - Wilson's theorem

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

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

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

История

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

Пример

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

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

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

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

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

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

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

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

${\ 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}}$${\ Displaystyle (п-1)!}$${\ displaystyle C_ {p}}$${\ displaystyle S_ {p}}$${\ displaystyle C_ {p}}$${\ displaystyle n_ {p} = (p-2)!}$

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

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

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

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

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

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

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

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

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

${\ Displaystyle \ prod _ {J = 1} ^ {m} \ J ^ {2} \ \ Equiv (-1) ^ {m + 1} {\ pmod {p}}}$

или

${\ displaystyle (m!) ^ {2} \ Equiv (-1) ^ {m + 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}} & {\ text {if}} m = 4, \; p ^ {\ alpha}, \; 2p ^ {\ alpha} \\\; \; \, 1 {\ pmod {m}} & {\ text {иначе }} \ end {case}}}$

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

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

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

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

Примечания

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

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

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