Bdtyk

Теорема Вильсона — теорема теории чисел, которая утверждает, что

Натуральное число $p>1$ является простым тогда и только тогда, когда $(p-1)!+1$ делится на $p$ .

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

Из теоремы следует: p простое тогда и только тогда, когда

{displaystyle sin(((p-1)!+1)~pi /p)=0}

.

Содержание

1 История

2 Пример

3 Доказательство
- 3.1 Необходимость
- 3.2 Достаточность
- 3.3 Геометрическое доказательство необходимости

4 Применение

5 Обобщение

6 См. также

7 Примечания

8 Литература

История |

Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 1000 г.н.э,^[1] и в 1770 году Уоринг сформулировал эту теорему в своём сочинении «Meditationes Algebraicae», опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику Вильсону^[en]. Доказательство теоремы он опубликовал только в третьем издании своего Medilationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем^[2].

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

Пример |

В таблице посчитаны значения (p − 1)! для p от 2 до 31, а также остаток от деления (p − 1)! на p (остаток от деления m на p обозначается как m mod p). Зелёным цветом выделены простые числа.

Таблица остатков по модулю n
$p$	$(p-1)!$	${displaystyle (p-1)!{bmod {p}}}$
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
31	265252859812191058636308480000000	30

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

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

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

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

Способ 1

Рассмотрим $(p-1)!$ . Множество ненулевых классов вычетов по простому модулю p по умножению ${mathbb {Z}}_{p}^{{times }}$ является группой, и тогда $(p-1)!$ - это произведение всех элементов группы ${mathbb {Z}}_{p}^{{times }}$ . Поскольку ${mathbb {Z}}_{p}^{{times }}$ - группа, то для каждого её элемента $a$ существует единственный обратный элемент $a^{{-1}}:aa^{{-1}}equiv 1{pmod p}$ . Соответствие $ato a^{{-1}}$ разбивает группу на классы: если $a=a^{{-1}}$ (что равносильно $a^{2}=1$ , то есть $ain {1,-1}$ , поскольку у уравнения второй степени может быть не более двух решений), то класс содержит один элемент $a$ , в противном случае класс состоит из двух элементов - ${a,a^{{-1}}}$ . Значит, если класс содержит один элемент $a$ , то произведение всех его элементов равно $a$ , а если класс содержит 2 элемента, то произведение всех его элементов равно 1. Теперь в произведении $(p-1)!$ сгруппируем элементы по классам, все произведения по 2-элементным классам просто равны 1:

(p-1)!equiv prod limits _{{a^{2}=1}}acdot prod limits _{{a^{2}neq 1}}aequiv prod limits _{{a^{2}=1}}aequiv 1cdot (-1)equiv -1{pmod p}.

■

Способ 2

Группа ${mathbb {Z}}_{p}^{{times }}$ циклична, т. е. существует элемент $g$ такой, что для всякого элемента $a$ существует $k$ такое, что $a=g^{k}$ . Поскольку ${mathbb {Z}}_{p}^{{times }}$ имеет $p-1$ элемент, то $k$ пробегает значения от 0 до $p-1$ , когда $a$ пробегает всю группу вычетов.
Тогда

(p-1)!equiv g^{1}g^{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}.

■

Способ 3

${mathbb {Z}}_{p}^{{times }}$ - поле, поэтому в нем имеет место теорема Безу, т. е. многочлен степени $n$ имеет не более $n$ корней. Рассмотрим многочлены $f(x)=(x-1)ldots (x-(p-1))$ и $g(x)=x^{{p-1}}-1$ . Оба многочлена имеют корни $1,2,ldots ,p-1$ (для $g(x)$ это получается по малой теореме Ферма), степени многочленов равны $p-1$ , старшие коэффициенты одинаковы. Тогда многочлен $h(x)=f(x)-g(x)$ имеет как минимум те же $p-1$ корней, но его степень не более $p-2$ . Значит по теореме Безу $h(x)$ тождественно равен нулю, т. е. для всех $x$ будет $f(x)=g(x)$ , в частности $f(0)=g(0)$ , что равносильно $(-1)^{{p-1}}(p-1)!equiv -1{pmod p}$ . Получаем утверждение теоремы для $p>2$ , т. к. $p-1$ четно и значит $(-1)^{{p-1}}=1$ .■

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

Если $p$ составное и ${displaystyle pneq 4}$ , то ${displaystyle (p-1)!equiv 0{pmod {p}}}$ , а при ${displaystyle p=4}$ получаем $(4-1)!equiv 2{pmod 4}$ .

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

Пусть p — простое число. Перенумеруем вершины правильного p-угольника в порядке обхода контура: 1, 2, 3, ..., p. Если соединим их диагоналями последовательно через одну, потом через две, через три и т. д., то кроме правильного многоугольника 123..., получим ещё (p − 2) многоугольников 135..., 147..., 159... и т. д. Эти (p − 1) многоугольников попарно тождественны, так как при соединении вершин через k и через (p − k − 2) получаем тождественные многоугольники. Число различных правильных многоугольников, полученных этим путём, равно $(p-1)/2$ :

Если соединим вершины в каком-либо другом порядке, например в порядке 13245..., то получим неправильный многоугольник; повертывая этот многоугольник так, чтобы номера его вершин заменялись следующими по порядку числами (число p заменяется при этом единицей), получим p неправильных многоугольников. В вышеуказанном примере это будут многоугольники 13245..., 24356..., 35467..., ..., 2134... Если таким путём образуем все возможные неправильные многоугольники, то число их будет кратно p, но, как и в случае правильных многоугольников, они по два тождественны; именно две последовательности вершин, прямая и обратная, дают один и тот же многоугольник.:

Если в последовательности вершин 123... сделать все возможные перестановки (p − 1) вершин 23..., то получим все возможные (правильные и неправильные) многоугольники; их число будет равно ${displaystyle 1cdot 2cdot 3cdots (p-1)=(p-1)!'}$ ; они опять будут попарно тождественны, так что действительное их число ${displaystyle (p-1)!/2}$ :

Сопоставляя результаты из пунктов 1 и 3, видим, что число неправильных многоугольников будет равно: ${displaystyle 1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)}$ . Из пункта 2, это число должно делиться на p; следовательно (p − 1)! + 1 кратно p.:■

Применение |

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

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

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

{displaystyle 1cdot (p-1)cdot 2cdot (p-2)cdots mcdot (p-m)equiv 1cdot (-1)cdot 2cdot (-2)cdots mcdot (-m)equiv -1{pmod {p}}.}

В результате

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

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

{displaystyle {biggl (}prod _{j=1}^{2k} j{biggr )}^{2}=prod _{j=1}^{2k}j^{2}equiv (-1)^{2k+1}=-1{pmod {p}}.}

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

Обобщение |

Используя в качестве образца теорему Эйлера, попытаемся обобщить теорему Вильсона на случай p = n, где n — произвольное натуральное число. Простая замена (p − 1)! на произведение n₁n₂…n_k всех чисел, меньших n и взаимно простых с n, не проходит: в случае n = 8 это произведение равно 1 × 3 × 5 × 7 = 105, а 106 на 8 не делится. Но оказывается, что или n₁n₂…n_k + 1, или n₁n₂…n_k − 1 обязательно делится на n.

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

Назовем элемент a группы E_n особым, если aa = 1. В этом случае элемент n − a — тоже особый. Следовательно, группа E_n содержит чётное число особых элементов: (a, n − a) — множество таких элементов, и никакой элемент не может быть парой сам для себя. Пусть n₁, n₂, …, n_k — все элементы группы E_n, то есть полный набор чисел, меньших n и взаимно простых с n.
Множество элементов, не являющихся особыми, разбивается на пары взаимно обратных, поэтому произведение таких элементов равно 1. С другой стороны, произведение особых элементов, составляющих пару (a, n − a), равно n − 1. Поскольку (n − 1)(n − 1) = 1, то произведение всех особых элементов равно 1 или n − 1, в зависимости от того, чётным или нечётным является число пар вида (a, n − a).■

Впервые теорема была доказана и обобщена Гауссом, при любом n > 2 для произведения всех натуральных чисел, не превосходящих n и взаимно простых с n, имеет место сравнение:

prod _{{k=1 atop (k,n)=1}}^{{n}}!!kequiv {begin{cases}-1{pmod {n}},&n=4,;p^{alpha },;2p^{alpha },;\;;,1{pmod {n}},&nneq 4,;p^{alpha },;2p^{alpha },,end{cases}}

где $p$ — нечётное простое число, $alpha$ — натуральный показатель.

См. также |

Мультипликативная группа кольца вычетов

Теорема Вольстенхольма

Число Вильсона

Функция распределения простых чисел

Примечания |

↑ Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Abu Ali al-Hasan ibn al-Haytham (англ.) — биография в архиве MacTutor.

↑ Joseph Louis Lagrange, «Demonstration d’un théorème nouveau concernant les nombres premiers» (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)

Литература |

Бухштаб А. А. Теория чисел, 2-е издание, М., 1966

Трост Э. Простые числа, пер. с нем., М., 1959

Виноградов И. М. Основы теории чисел. — 5 изд.. — М.-Л.: Гостехиздат, 1952.

R. Crandall, K. Dilcher and C. Pomerance The Prime Glossary (англ.)

Ore, O. Number Theory and its History. McGraw-Hill, 1948.

Бончковский Р. Н. и Чистяков И. И. Математическое просвещение, выпуск 01

[1] Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Abu Ali al-Hasan ibn al-Haytham (англ.) — биография в архиве MacTutor.

[2] Joseph Louis Lagrange, «Demonstration d’un théorème nouveau concernant les nombres premiers» (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)

搜尋此網誌