GrabDuck

Теорема Вильсона — Википедия

:

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

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

Из теоремы следует: n простое тогда и только тогда, когда sin ( ( ( n 1 ) ! + 1 )   π / n ) = 0 {\displaystyle \sin(((n-1)!+1)~\pi /n)=0} ,

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

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

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

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

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

В результате

j = 1 m   j 2   ( 1 ) m + 1 ( mod 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, следовательно

( j = 1 2 k   j ) 2 = j = 1 2 k   j 2   ( 1 ) 2 k + 1   = 1 ( mod p ) . {\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)! на произведение 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, имеет место сравнение:

k = 1 ( k , n ) = 1 n k { 1 ( mod n ) , n = 4 , p α , 2 p α ; 1 ( mod n ) , n 4 , p α , 2 p α , {\displaystyle \prod _{k=1 \atop (k,n)=1}^{n}\!\!k\equiv {\begin{cases}-1{\pmod {n}},&n=4,\;p^{\alpha },\;2p^{\alpha }\,;\\\;\;\,1{\pmod {n}},&n\neq 4,\;p^{\alpha },\;2p^{\alpha }\,,\end{cases}}}

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

Теорема впервые была сформулирована Уорингом в 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