Открыть главное меню

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

Натуральное число является простым тогда и только тогда, когда делится на .

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

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

Содержание

ИсторияПравить

Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 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
     
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 = 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» (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