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

Теорема о простых числах

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

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

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

История

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

Пример

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

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

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

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

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

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

Простой модуль

Первые два доказательства ниже используют тот факт, что классы вычетов по модулю простого числа являются конечным полем — более подробную информацию см. в статье Простое поле . ^[6]

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

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

Например, для , имеем ${\displaystyle p=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}}.}$$

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

Опять же, результат тривиален для 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.} По модулю p малая теорема Ферма утверждает, что он также имеет те же корни p − 1 , 1, 2, ..., p − 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 (mod p ) . Это теорема Уилсона.

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

Теорему Вильсона можно вывести из частного применения теорем Силова . Пусть p — простое число. Непосредственно выводится, что симметрическая группа имеет ровно элементы порядка p , а именно p -циклы . С другой стороны, каждая силовская p -подгруппа в является копией . Отсюда следует, что число силовских p -подгрупп равно . Третья теорема Силова подразумевает ${\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}}.}$

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

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

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

Приложения

Тесты на простоту

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

При использовании в другом направлении, для определения простоты последующих элементов больших факториалов, это действительно очень быстрый и эффективный метод. Однако его полезность ограничена. ^{[ необходима цитата ]}

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

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

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

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

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

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

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

Гаусс доказал ^{[7] [ необходим непервичный источник ]} , что где p представляет собой нечетное простое число и положительное целое число. То есть, произведение положительных целых чисел, меньших m и взаимно простых с m , на единицу меньше кратного m, когда m равно 4, или степени нечетного простого числа, или удвоенной степени нечетного простого числа; в противном случае произведение на единицу больше кратного m . Значения m , для которых произведение равно −1, являются в точности теми, для которых существует примитивный корень по модулю m . $${\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. Потому что если , то , и если простое число делит , то по лемме Евклида оно делит либо , либо . ${\displaystyle a\equiv a^{-1}{\pmod {p}}}$ ${\displaystyle a^{2}-1\equiv 0{\pmod {p}}}$ ${\displaystyle p}$ ${\displaystyle a^{2}-1=(a-1)(a+1)}$ ${\displaystyle a-1}$ ${\displaystyle a+1}$

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

   Оригинал  : Inoltre egli intravide anche il teorema di Wilson, Come risulta dall'enunciato seguente:
   
   «Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complexum ad unum?) si datus sit primitivus. Si datus sit derivativeus relinquet numerum qui cum dato habeat communem mensuram unitate majorem».
   
   Я не хочу этого делать, но это не так.

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

   См. также: Джузеппе Пеано, изд., Formulaire de mathématiques , vol. 2, нет. 3, стр. 85 (1897 г.).
6. Ландау, два доказательства теоремы 78 ^{[ необходима полная цитата ]}
7. Гаусс, DA, ст. 78

Ссылки

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

• Гаусс, Карл Фридрих; Кларк, Артур А. (1986), Disquisitiones Arithemeticae (2-е исправленное издание), Нью-Йорк: Springer , ISBN 0-387-96254-9(перевод на английский){{citation}}: CS1 maint: postscript (link).
• Гаусс, Карл Фридрих; Мазер, Х. (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) (2-е изд.), Нью-Йорк: Челси, ISBN 0-8284-0191-8(перевод на немецкий){{citation}}: CS1 maint: postscript (link).
• Ландау, Эдмунд (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
• Охана, Эндрю. «Обобщение теоремы Вильсона» (PDF) .