Теорема Вильсона — теорема теории чисел, которая утверждает, что
Эта теорема, в основном, имеет теоретическое значение, поскольку (p-1)! вычислить довольно трудно. Проще вычислить ap-1, поэтому элементарные тесты, определяющие, является ли число простым, основаны на теореме Ферма, а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту p! потребуется около суток вычислений на процессорах SPARC, а числа с десятками тысяч цифр проходят тест на простоту с использованием теоремы Ферма меньше чем за час. Но, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием для простоты.
История Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 1000 г.н.э, и в 1770 году Варинг сформулировал эту теорему в своём сочинении «Meditationes Algebraicae», опубликованном в Кембридже, где он привёл эту теорему без доказательства. По его словам, теорема принадлежит его ученику . Доказательство теоремы он опубликовал только в третьем издании своего Meditationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем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). Наконец, Эйлер в «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 0 10 0 11 10 12 0 13 12 14 0 15 0 16 0 17 16 18 0 19 18 20 0 21 0 22 0 23 22 24 0 25 0 26 0 27 0 28 0 29 28 30 0 31 30 32 0 33 0 34 0 35 0 36 0 37 36
Доказательство
Применение Используем теорему Вильсона
Для нечётного простого , получаем
В результате
Мы можем использовать этот факт для доказательства известного результата: для любого простого 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, имеет место сравнение:
где — нечётное простое число, — натуральный показатель.
Позже было найдено ещё одно формальное обобщение теоремы Вильсона (В.Виноград):
При получается теорема Вильсона.
При получается , т.е.
, если
и
, если
См. также Мультипликативная группа кольца вычетов Теорема Вольстенхольма Число Вильсона Функция распределения простых чисел
Примечания
Литература Бухштаб А. А. Теория чисел, 2-е издание, М., 1966 Трост Э. Простые числа, пер. с нем., М., 1959
R. Crandall, K. Dilcher and C. Pomerance The Prime Glossary Ore, O. Number Theory and its History. McGraw-Hill, 1948. Бончковский Р. Н. и Чистяков И. И. Математическое просвещение, выпуск 01
Категория:Тесты простоты Категория:Теория чисел Категория:Теоремы о простых числах