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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

а также число Вильсона

Пример[править | править вики-текст]

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

Таблица остатков по модулю 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 265252859812191000000000000000000 30

Доказательство[править | править вики-текст]

Применение[править | править вики-текст]

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

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

В результате

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

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

Обобщение[править | править вики-текст]

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

Рассмотрим множество En чисел, меньших n и взаимно простых с n. Под произведением двух элементов этого множества ab, будем понимать остаток от деления обычного произведения ab на 'n'. Ясно, что если a, b принадлежит 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, имеет место сравнение:

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

История[править | править вики-текст]

Теорема впервые была сформулирована Уорингом в 1770 году. В своем сочинении «Meditationes Algebraicae», опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику Вильсону (англ.). Доказательство теоремы он опубликовал только в третьем издании своего Medilationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 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