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

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

Если — простое число, то число делится на . Обратно: если делится на , то — простое число.


Эта теорема, в основном, имеет теоретическое значение, поскольку факториал вычислить довольно трудно. Проще вычислить , поэтому элементарные тесты, определяющие, является ли число простым, основаны на теореме Ферма, а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту потребуется около суток вычислений на процессорах SPARC, а числа с десятками тысяч цифр проходят тест на простоту с использованием теоремы Ферма меньше чем за час. Но, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием для простоты.

История

править

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

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

Пример

править

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

Таблица остатков по модулю n
     
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
32 8222838654177922817725562880000000 0
33 263130836933693530167218012160000000 0
34 8683317618811886495518194401280000000 0
35 295232799039604140847618609643520000000 0
36 10333147966386144929666651337523200000000 0
37 371993326789901217467999448150835200000000 36

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

править

Применение

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

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

 

В результате

 

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

 

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

Обобщение

править

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

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

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

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

 

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

Позже было найдено ещё одно формальное обобщение теоремы Вильсона (В.Виноград):

 

При   получается теорема Вильсона.

При   получается  , т.е.

 , если  

и

 , если  

См. также

править

Примечания

править
  1. Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Abu Ali al-Hasan ibn al-Haytham (англ.) — биография в архиве MacTutor.
  2. Joseph Louis Lagrange, «Demonstration d’un théorème nouveau concernant les nombres premiers» Архивная копия от 11 мая 2022 на Wayback Machine (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