Русская Википедия:Теорема Вильсона
Теорема Вильсона — теорема теории чисел, которая утверждает, что Шаблон:Теорема
Эта теорема, в основном, имеет теоретическое значение, поскольку факториал <math>(p-1)!</math> вычислить довольно трудно. Проще вычислить <math>a^{p-1}</math>, поэтому элементарные тесты, определяющие, является ли число простым, основаны на теореме Ферма, а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту <math>p!</math> потребуется около суток вычислений на процессорах SPARC, а числа с десятками тысяч цифр проходят тест на простоту с использованием теоремы Ферма меньше чем за час. Но, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием для простоты.
История
Эта теорема впервые была сформулирована Ибн аль-Хайсамом около 1000 г.н.э,[1] и в 1770 году Варинг сформулировал эту теорему в своём сочинении «Meditationes Algebraicae», опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит его ученику Шаблон:Iw. Доказательство теоремы он опубликовал только в третьем издании своего Meditationes в 1782 году. Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем[2].
Наконец, Эйлер в «Opusc. Analyt», Т. 1, р. 329 дал доказательство, Гаусс обобщил теорему Вильсона на случай составного модуля. Имеются данные о том, что Лейбниц знал о результате ещё столетием раньше, но никогда не публиковал его.
Пример
В таблице посчитаны значения <math>(p-1)!</math> для p от 2 до 31, а также остаток от деления <math>(p-1)!</math> на p (остаток от деления m на p обозначается как m mod p). Зелёным цветом выделены простые числа.
| <math>p</math> | <math>(p-1)!</math> | <math>(p-1)! \bmod p</math> |
|---|---|---|
| 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 |
Доказательство
Применение
- Используем теорему Вильсона
- <math>1\cdot 2\cdots (p-1) \equiv -1 \pmod{p}.</math>
Для нечётного простого Шаблон:Nowrap, получаем
- <math>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}.</math>
В результате
- <math>\prod_{j=1}^m j^2 \equiv (-1)^{m+1} \pmod{p}.</math>
Мы можем использовать этот факт для доказательства известного результата: для любого простого p, такого что p ≡ 1 (mod 4) число (−1) является квадратом (квадратичный вычет) по модулю p. Действительно, пусть p = 4k + 1 для некоторого натурального k. Тогда m = 2k, следовательно
- <math>\biggl( \prod_{j=1}^{2k}\ j \biggr)^{2} = \prod_{j=1}^{2k} j^2 \equiv (-1)^{2k+1} = -1 \pmod{p}.</math>
Теорема Вильсона используется для генерирования простых чисел, но она слишком медленная для практического применения.
Обобщение
Используя в качестве образца теорему Эйлера, попытаемся обобщить теорему Вильсона на случай 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, имеет место сравнение:
- <math>
\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 \ne 4,\;p^\alpha,\;2p^\alpha\, , \end{cases} </math> где <math>p</math> — нечётное простое число, <math>\alpha</math> — натуральный показатель.
Позже было найдено ещё одно формальное обобщение теоремы Вильсона (В.Виноград):
<math>(p-m)!*(m-1)!\equiv(-1)^m\pmod{p}</math>
При <math>m=1</math> получается теорема Вильсона.
При <math>m=\left ( \frac{p+1}{2} \right )</math> получается <math>\left ( \frac{p-1}{2} \right )!^2 + (-1)^\left ( \frac{p-1}{2} \right )\equiv0\pmod{p}</math>, т.е.
<math>\left ( \frac{p-1}{2} \right )!^2 + 1\equiv0\pmod{p}</math>, если <math>p\equiv1\pmod{4}</math>
и
<math>\left ( \frac{p-1}{2} \right )!^2 - 1\equiv0\pmod{p}</math>, если <math>p\equiv3\pmod{4}</math>
См. также
- Мультипликативная группа кольца вычетов
- Теорема Вольстенхольма
- Число Вильсона
- Функция распределения простых чисел
Примечания
Литература
- Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
- Трост Э. Простые числа, пер. с нем., М., 1959
- Шаблон:Книга
- R. Crandall, K. Dilcher and C. Pomerance The Prime GlossaryШаблон:Ref-en
- Ore, O. Number Theory and its History. McGraw-Hill, 1948.
- Бончковский Р. Н. и Чистяков И. И. Математическое просвещение, выпуск 01
- ↑ Шаблон:MacTutor Biography
- ↑ Joseph Louis Lagrange, «Demonstration d’un théorème nouveau concernant les nombres premiers» Шаблон:Wayback (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)
