Просмотр кода страницы Теорема Вильсона

'''Теорема Вильсона''' — теорема [[Теория чисел|теории чисел]], которая утверждает, что
{{теорема|Если <math>p</math> — простое число, то число <math>(p-1)!+1</math> делится на <math>p</math>. 

Обратно: если <math>(p-1)!+1</math> делится на <math>p</math>, то <math>p</math> — простое число.}}

Эта теорема, в основном, имеет теоретическое значение, поскольку [[факториал]] <math>(p-1)!</math> вычислить довольно трудно. Проще вычислить <math>a^{p-1}</math>, поэтому [[тест простоты|элементарные тесты]], определяющие, является ли число простым, основаны на [[малая теорема Ферма|теореме Ферма]], а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту <math>p!</math> потребуется около суток вычислений на процессорах [[sparc|SPARC]], а числа с десятками тысяч цифр проходят тест на простоту с использованием теоремы Ферма меньше чем за час. Но, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием для простоты.

== История ==
Эта теорема впервые была сформулирована [[Ибн аль-Хайсам]]ом около 1000 г.н.э,<ref>{{MacTutor Biography|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham}}</ref> и в 1770 году [[Варинг, Эдуард|Варинг]] сформулировал эту теорему в своём сочинении «''Meditationes Algebraicae''», опубликованном в Кембридже, где он привёл эту теорему без доказательства. По его словам, теорема принадлежит его ученику {{iw|Джон Вильсон (математик)|Вильсону|en|John Wilson (mathematician)}}. Доказательство теоремы он опубликовал только в третьем издании своего ''Meditationes'' в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году [[Лагранж, Жозеф Луи|Лагранжем]]<ref>Joseph Louis Lagrange, [https://books.google.com/books?id=_-U_AAAAYAAJ&pg=PA125#v=onepage&q&f=false «Demonstration d’un théorème nouveau concernant les nombres premiers»] {{Wayback|url=https://books.google.com/books?id=_-U_AAAAYAAJ&pg=PA125#v=onepage&q&f=false |date=20220511225931 }} (Proof of a new theorem concerning prime numbers), ''Nouveaux Mémoires de l’Académie Royale des Sciences et Belles-Lettres'' (Berlin), vol. 2, pages 125—137 (1771)</ref>.

Наконец, Эйлер в «''Opusc. Analyt''», ''Т. 1, р. 329'' дал доказательство, Гаусс обобщил теорему Вильсона на случай составного модуля. Имеются данные о том, что [[Лейбниц, Готфрид Вильгельм|Лейбниц]] знал о результате ещё столетием раньше, но никогда не публиковал его.

== Пример ==
В таблице посчитаны значения <math>(p-1)!</math> для ''p'' от 2 до 37, а также [[остаток от деления]] <math>(p-1)!</math> на ''p'' (остаток от деления ''m'' на ''p'' обозначается как [[mod (операция)|''m'' mod ''p'']]). <span style="background-color:#E0FFE0">Зелёным цветом</span> выделены простые числа.
{| class="wikitable" style="text-align:right"
|+ Таблица остатков по модулю ''n''
! <math>p</math> !! <math>(p-1)!</math> !! <math>(p-1)! \bmod p</math>
|- style="background-color:#E0FFE0"
| 2 || 1 || 1
|- style="background-color:#E0FFE0"
| 3 || 2 || 2
|- style="background-color:#FFFFFF"
| 4 || 6 || 2
|- style="background-color:#E0FFE0"
| 5 || 24 || 4
|- style="background-color:#FFFFFF"
| 6 || 120 || 0
|- style="background-color:#E0FFE0"
| 7 || 720 || 6
|- style="background-color:#FFFFFF"
| 8 || 5040 || 0
|- style="background-color:#FFFFFF"
| 9 || 40320 || 0
|- style="background-color:#FFFFFF"
| 10 || 362880 || 0
|- style="background-color:#E0FFE0"
| 11 || 3628800 || 10
|- style="background-color:#FFFFFF"
| 12 || 39916800 || 0
|- style="background-color:#E0FFE0"
| 13 || 479001600 || 12
|- style="background-color:#FFFFFF"
| 14 || 6227020800 || 0
|- style="background-color:#FFFFFF"
| 15 || 87178291200 || 0
|- style="background-color:#FFFFFF"
| 16 || 1307674368000 || 0
|- style="background-color:#E0FFE0"
| 17 || 20922789888000 || 16
|- style="background-color:#FFFFFF"
| 18 || 355687428096000 || 0
|- style="background-color:#E0FFE0"
| 19 || 6402373705728000 || 18
|- style="background-color:#FFFFFF"
| 20 || 121645100408832000 || 0
|- style="background-color:#FFFFFF"
| 21 || 2432902008176640000 || 0
|- style="background-color:#FFFFFF"
| 22 || 51090942171709440000 || 0
|- style="background-color:#E0FFE0"
| 23 || 1124000727777607680000 || 22
|- style="background-color:#FFFFFF"
| 24 || 25852016738884976640000 || 0
|- style="background-color:#FFFFFF"
| 25 || 620448401733239439360000 || 0
|- style="background-color:#FFFFFF"
| 26 || 15511210043330985984000000 || 0
|- style="background-color:#FFFFFF"
| 27 || 403291461126605635584000000 || 0
|- style="background-color:#FFFFFF"
| 28 || 10888869450418352160768000000 || 0
|- style="background-color:#E0FFE0"
| 29 || 304888344611713860501504000000 || 28
|- style="background-color:#FFFFFF"
| 30 || 8841761993739701954543616000000 || 0
|- style="background-color:#E0FFE0"
| 31 || 265252859812191058636308480000000 || 30
|- style="background-color:#FFFFFF"
| 32 || 8222838654177922817725562880000000 || 0
|- style="background-color:#FFFFFF"
| 33 || 263130836933693530167218012160000000 || 0
|- style="background-color:#FFFFFF"
| 34 || 8683317618811886495518194401280000000 || 0
|- style="background-color:#FFFFFF"
| 35 || 295232799039604140847618609643520000000 || 0
|- style="background-color:#FFFFFF"
| 36 || 10333147966386144929666651337523200000000 || 0
|- style="background-color:#E0FFE0"
| 37 || 371993326789901217467999448150835200000000 || 36
|}

== Доказательство ==
{{Hider|
  title = Доказательство|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =

=== Достаточность ===

Пусть ''p'' — простое.

; Способ 1
Рассмотрим <math>(p-1)!</math>. Множество ненулевых классов вычетов по простому модулю ''p'' по умножению <math>\mathbb{Z}_p^{\times}</math> является [[Группа (математика)|группой]], и тогда <math>(p-1)!</math> - это произведение всех элементов группы <math>\mathbb{Z}_p^{\times}</math>. Поскольку <math>\mathbb{Z}_p^{\times}</math> - группа, то для каждого её элемента <math>a</math> существует единственный обратный элемент <math>a^{-1}: aa^{-1}\equiv 1 \pmod p</math>. Соответствие <math>a\to a^{-1}</math> разбивает группу на классы: если <math>a= a^{-1}</math> (что равносильно <math>a^2=1</math>, то есть <math>a \in \{1, -1\}</math>, поскольку у уравнения второй степени может быть не более двух решений), то класс содержит один элемент <math>a</math>, в противном случае класс состоит из двух элементов - <math>\{a,a^{-1}\}</math>. Значит, если класс содержит один элемент <math>a</math>, то произведение всех его элементов равно <math>a</math>, а если класс содержит 2 элемента, то произведение всех его элементов равно 1. Теперь в произведении <math>(p-1)!</math> сгруппируем элементы по классам, все произведения по 2-элементным классам просто равны 1:

:<math>(p-1)!\equiv\prod\limits_{a^2=1}a \cdot \prod\limits_{a^2\neq 1}a\equiv\prod\limits_{a^2=1}a\equiv1\cdot (-1)\equiv -1\pmod p.</math>

{{ЧТД}}

; Способ 2
Группа <math>\mathbb{Z}_p^{\times}</math> [[Циклическая группа|циклична]], т. е. существует элемент <math>g</math> такой, что для всякого элемента <math>a</math> существует <math>k</math> такое, что <math>a=g^k</math>. Поскольку <math>\mathbb{Z}_p^{\times}</math> имеет <math>p-1</math> элемент, то <math>k</math> пробегает значения от 0 до <math>p-1</math>, когда <math>a</math> пробегает всю группу вычетов. 
Тогда

:<math>(p-1)!\equiv g^1g^2\ldots g^{p-1}\equiv g^{1+2+\ldots+(p-1)}=g^{\frac{p-1}{2}p}\equiv (-1)^p\equiv -1\pmod p.</math>

{{ЧТД}}

; Способ 3
<math>\mathbb{Z}_p^{\times}</math>  - [[Поле (алгебра)|поле]], поэтому в нем имеет место [[теорема Лагранжа (теория чисел)|теорема Лагранжа]], т. е. многочлен степени <math>n</math> имеет не более <math>n</math> корней. Рассмотрим многочлены <math>f(x)=(x-1)\ldots(x-(p-1))</math> и <math>g(x)=x^{p-1}-1</math>. Оба многочлена имеют корни <math>1,2,\ldots,p-1</math> (для <math>g(x)</math> это получается по [[Малая теорема Ферма|малой теореме Ферма]]), степени многочленов равны <math>p-1</math>, старшие коэффициенты одинаковы. Тогда многочлен <math>h(x)=f(x)-g(x)</math> имеет как минимум те же <math>p-1</math> корней, но его степень не более <math>p-2</math>. Значит по [[Теорема Безу|теореме Безу]] <math>h(x)</math> тождественно равен нулю, т. е. для всех <math>x</math> будет <math>f(x)=g(x)</math>, в частности <math>f(0)=g(0)</math>, что равносильно <math>(-1)^{p-1}(p-1)!\equiv -1\pmod p</math>. Получаем утверждение теоремы для <math>p>2</math>, т. к. <math>p-1</math> четно и значит <math>(-1)^{p-1}=1</math>.{{ЧТД}}

=== Необходимость ===

Если <math>p</math> составное и <math>p\neq 4</math>, то <math>(p-1)!\equiv 0\pmod p</math>, а при <math>p=4</math> получаем <math>(4-1)!\equiv 2\pmod 4</math>.

=== Геометрическое доказательство достаточности ===

# Пусть ''p'' — простое число. Перенумеруем вершины правильного ''p''-угольника в порядке обхода контура: 1, 2, 3, ..., ''p''. Если соединим их диагоналями последовательно через одну, потом через две, через три и т. д., то кроме правильного многоугольника 123..., получим ещё (''p'' − 2) многоугольников 135..., 147..., 159... и т. д. Эти (''p'' − 1) многоугольников попарно тождественны, так как при соединении вершин через ''k'' и через (''p'' − ''k'' − 2) получаем тождественные многоугольники. Число различных правильных многоугольников, полученных этим путём, равно <math>(p-1)/2</math>;
# Если соединим вершины в каком-либо другом порядке, например в порядке 13245..., то получим неправильный многоугольник; повёртывая этот многоугольник так, чтобы номера его вершин заменялись следующими по порядку числами (число ''p'' заменяется при этом единицей), получим ''p'' неправильных многоугольников. В вышеуказанном примере это будут многоугольники 13245..., 24356..., 35467..., ..., 2134... Если таким путём образуем все возможные неправильные многоугольники, то число их будет кратно ''p'', но, как и в случае правильных многоугольников, они по два тождественны; именно две последовательности вершин, прямая и обратная, дают один и тот же многоугольник;
# Если в последовательности вершин 123... сделать все возможные перестановки (''p'' − 1) вершин 23..., то получим все возможные (правильные и неправильные) многоугольники; их число будет равно <math>1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'</math>; они опять будут попарно тождественны, так что действительное их число <math>(p-1)!/2</math>;
# Сопоставляя результаты из пунктов 1 и 3, видим, что число неправильных многоугольников будет равно: <math>1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)</math>. Из пункта 2, это число должно делиться на ''p''; следовательно (''p'' − 1)! + 1 кратно ''p''.:{{ЧТД}}

}}

== Применение ==
* Используем теорему Вильсона

: <math>1\cdot 2\cdots (p-1) \equiv -1 \pmod{p}.</math>

Для нечётного простого {{nowrap|1=''p'' = 2''m'' + 1}}, получаем

: <math>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}.</math>

В результате

: <math>\prod_{j=1}^m j^2 \equiv (-1)^{m+1} \pmod{p}.</math>

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

: <math>\biggl( \prod_{j=1}^{2k}\ j \biggr)^{2} = \prod_{j=1}^{2k} j^2 \equiv (-1)^{2k+1} = -1 \pmod{p}.</math>

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

== Обобщение ==
Используя в качестве образца [[теорема Эйлера (теория чисел)|теорему Эйлера]], попытаемся обобщить теорему Вильсона на случай ''p'' = ''n'', где ''n'' — произвольное натуральное число. Простая замена (''p'' − 1)! на произведение ''n''<sub>1</sub>''n''<sub>2</sub>…''n''<sub>k</sub> всех чисел, меньших ''n'' и взаимно простых с ''n'', не проходит: в случае ''n'' = 8 это произведение равно 1 × 3 × 5 × 7 = 105, а 106 на 8 не делится. Но оказывается, что или ''n''<sub>1</sub>''n''<sub>2</sub>…''n''<sub>''k''</sub> + 1, или ''n''<sub>1</sub>''n''<sub>2</sub>…''n''<sub>''k''</sub> − 1 обязательно делится на ''n''.

Рассмотрим множество '''E'''<sub>''n''</sub> чисел, меньших ''n'' и взаимно простых с ''n''. Под произведением двух элементов этого множества ''ab'', будем понимать остаток от деления обычного произведения ''ab'' на ''n''. Ясно, что если ''a'', ''b'' принадлежит '''E'''<sub>''n''</sub>, то ''ab'' принадлежит '''E'''<sub>''n''</sub>. Множество '''E'''<sub>''n''</sub> относительно операции умножения является группой. В отличие от случая, когда ''n'' — простое, группа '''E'''<sub>''n''</sub> может содержать элементы, не равные 1 и (''n'' − 1) такие, что их квадрат равен 1: например если ''n'' = 8, то 3 × 3 = 1, 5 × 5 = 1, 7 × 7 = 1. Поэтому в общем случае произведение всех элементов из '''E'''<sub>''n''</sub> не равно (''n'' − 1). Покажем, что тогда оно равно 1.

Назовем элемент ''a'' группы '''E'''<sub>''n''</sub> особым, если ''aa'' = 1. В этом случае элемент ''n'' − ''a'' — тоже особый. Следовательно, группа '''E'''<sub>''n''</sub> содержит чётное число особых элементов: (''a'', ''n'' − ''a'') — множество таких элементов, и никакой элемент не может быть парой сам для себя. Пусть ''n''<sub>1</sub>, ''n''<sub>2</sub>, …, ''n''<sub>''k''</sub> — все элементы группы '''E'''<sub>''n''</sub>, то есть полный набор чисел, меньших ''n'' и взаимно простых с ''n''.
Множество элементов, не являющихся особыми, разбивается на пары взаимно обратных, поэтому произведение таких элементов равно 1. С другой стороны, произведение особых элементов, составляющих пару (''a'', ''n'' − ''a''), равно ''n'' − 1. Поскольку (''n'' − 1)(''n'' − 1) = 1, то произведение всех особых элементов равно 1 или ''n'' − 1, в зависимости от того, чётным или нечётным является число пар вида (''a'', ''n'' − ''a'').{{ЧТД}}

Впервые теорема была доказана и обобщена [[Гаусс, Карл Фридрих|Гауссом]], при ''любом'' ''n'' > 2 для произведения всех натуральных чисел, не превосходящих ''n'' и взаимно простых с ''n'', имеет место сравнение:
: <math>
\prod_{k = 1 \atop (k,n)=1}^{n} \!\!k \equiv
\begin{cases}
-1      \pmod{n},  & n=4,\;p^\alpha,\;2p^\alpha\, ;\\
\;\;\,1 \pmod{n},  & n \ne 4,\;p^\alpha,\;2p^\alpha\, ,
\end{cases} 
</math>
где <math>p</math> — нечётное простое число, <math>\alpha</math> — натуральный показатель.
 
Позже было найдено ещё одно формальное обобщение теоремы Вильсона (В.Виноград):  

<math>(p-m)!*(m-1)!\equiv(-1)^m\pmod{p}</math>    

При <math>m=1</math> получается теорема Вильсона. 

При <math>m=\left ( \frac{p+1}{2} \right )</math> получается <math>\left ( \frac{p-1}{2} \right )!^2 + (-1)^\left ( \frac{p-1}{2} \right )\equiv0\pmod{p}</math>, т.е. 

<math>\left ( \frac{p-1}{2} \right )!^2 + 1\equiv0\pmod{p}</math>, если <math>p\equiv1\pmod{4}</math>  

и 

<math>\left ( \frac{p-1}{2} \right )!^2 - 1\equiv0\pmod{p}</math>, если <math>p\equiv3\pmod{4}</math>

== См. также ==
* [[Мультипликативная группа кольца вычетов]]
* [[Теорема Вольстенхольма]]
* [[Число Вильсона]]
* [[Функция распределения простых чисел]]

== Примечания ==
{{примечания|2}}

== Литература ==
* ''Бухштаб А. А.'' Теория чисел, 2-е издание, М., 1966
* ''Трост Э.'' Простые числа, пер. с нем., М., 1959
* {{книга |автор=Виноградов И. М. |заглавие=Основы теории чисел |год=1952 |издание=5 изд. |место=М.-Л. |издательство=Гостехиздат |ссылка=http://ilib.mccme.ru/djvu/vinogradov.htm}}
* ''R. Crandall, K. Dilcher and C. Pomerance'' [http://primes.utm.edu/glossary/xpage/WilsonsTheorem.html The Prime Glossary]{{ref-en}}
* ''Ore, O.'' Number Theory and its History. McGraw-Hill, 1948.
* ''Бончковский Р. Н. и Чистяков И. И.'' Математическое просвещение, выпуск 01

{{Внешние ссылки}}
{{rq|refless|isbn}}

[[Категория:Тесты простоты]]
[[Категория:Теория чисел]]
[[Категория:Теоремы о простых числах]]