Теорема Вольстенхольма

Теорема Вольстенхольма (англ. Wolstenholme's theorem) утверждает, что для любого простого числа $p > 3$ выполняется сравнение

$\binom{2p}{p} \equiv 2 \pmod{p^3},$

где $\textstyle\binom{2p}{p}$ — средний биномиальный коэффициент. Эквивалентное сравнение

$\binom{ap}{bp} \equiv \binom{a}{b} \pmod{p^3}.$

Неизвестны составные числа, удовлетворяющие теореме Вольстенхольма, и существует гипотеза о том, что их не существует. Простые, удовлетворяющие аналогичному сравнению по модулю $p^4$ называются простыми Вольстенхольма.

История

Впервые теорема была доказана Джозефом Вольстенхольмом (Joseph Wolstenholme) в 1862 году. В 1819 году Чарльз Беббидж доказал аналогичное сравнение по модулю $p^2$, которое верно для всех простых p. Вторая формулировка теоремы Вольстенхольма была дана Глашиером (J. W. L. Glaisher) под влиянием теоремы Люка.

Как утверждал сам Вольстенхольм, его теорема была получена через пару сравнений с (обобщенными) гармоническими числами:

$1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{p-1} \equiv 0 \pmod{p^2},$

$1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{(p-1)^2} \equiv 0 \pmod p.$

Простые Вольстенхольма

Простое p называется простым Вольстенхольма тогда и только тогда, когда:

$\binom{2p}{p} \equiv 2 \pmod{p^4}.$

До сих пор известно только 2 простых Вольстенхольма: 16843 и 2124679 (последовательность A088164 в OEIS); остальные такие простые, если они существуют, превосходят $10^9$.

Предположительно $\textstyle\frac{\binom{2p}{p}-2}{p^3} \mod p$ ведет себя как псевдослучайное число равномерно распределённое в отрезке $[0,p-1]$. Эвристически предполагается, что количество простых Вольстенхольма в интервале $(K,N)$ оценивается как $\ln \ln N - \ln \ln K$. Из этих эвристических соображений следует, что следующее простое Вольстенхольма лежит между $10^9$ и $10^{24}$.

Сходные эвристические аргументы утверждают, что не существует простых, для которых сравнение выполняется по модулю $p^5$.

Доказательство

Существует несколько способов доказательства теоремы Вольстенхольма.

Комбинаторно-алгебраическое доказательство

Приведем доказательство Глашиера с использованием комбинаторики и алгебры.

Пусть p — простое число, a, b — неотрицательные целые числа. Обозначим $A=(a_{ij})$, $i=1,\dots,a$, $j=1,\dots,p$ множество из a·p элементов, разделенных на a колец $K_i=(a_{ij})$, $j=1,\dots,p$ длины p. На каждом кольце действует группа вращений $C_p \cong \mathbb{Z}_p$. Таким образом, на всем A действует группа $\mathbb{Z}_p^a$. Пусть B — произвольное подмножество множества A из b·p элементов. Множество B можно выбрать $\textstyle\binom{ap}{bp}$ способами. Каждая орбита множества B при действии группы $\mathbb{Z}_p^a$ содержит $p^k$ элементов, где k — число частичных пересечений B с кольцами $K_i$. Существует $\textstyle\binom{a}{b}$ орбит длины 1 и не существует орбит длины p. Таким образом, мы получаем теорему Беббиджа:

$\binom{ap}{bp} \equiv \binom{a}{b} \pmod{p^2}.$

Исключая орбиты длиной $p^2$, мы получаем

$\binom{ap}{bp} \equiv \binom{a}{b}+\binom{a}{2}\left(\binom{2p}{p}-2\right)\binom{a-2}{b-1} \pmod{p^3}.$

Среди прочих последовательностей, это сравнение в случае $a=2$, $b=1$ даёт нам общий случай второй формы теоремы Вольстенхольма.

Переключаемся с комбинаторики на алгебру и применяем полиномиальную аргументацию. Фиксируя b мы получаем сравнение, с полиномами от a в обоих его частях, верное при любых неотрицательных a. Следовательно, сравнение верно при любом целом a. В частности, при $a=-1$, $b=1$ получаем сравнение:

$\binom{-p}{p} \equiv \binom{-1}{1}+\binom{-1}{2}\left(\binom{2p}{p} - 2\right) \pmod{p^3}.$

Поскольку

$\binom{-p}{p} = \frac{(-1)^p}2\binom{2p}{p},$

то

$3\binom{2p}{p} \equiv 6 \pmod{p^3}.$

При $p\neq 3$ сокращаем на 3 и доказательство закончено.

Сходное сравнение по модулю $p^4$:

$\binom{ap}{bp} \equiv \binom{a}{b} \pmod{p^4}$

для всех натуральных a, b верно тогда и только тогда, когда $a=2$, $b=1$, то есть тогда и только тогда, когда p — простое Вольстенхольма.

Теоретико-числовое доказательство

Представим биномиальный коэффициент как отношение факториалов, сократим p! и сократим p в биномиальном коэффициенте и перенесем числитель в правую часть, получаем:

$\prod\limits_{k=1}^{p-1} \equiv (p-1)! \pmod{p^3}$

Левая часть — многочлен от p, перемножим скобки и в полученном многочлене отбросим степени p, большие 3, получим:

$a_2p^2+a_1p+(p-1)! \equiv (p-1)! \pmod{p^3}$

Сокращаем $(p-1)!$ и степень p вместе с модулем и затем на $(p-1)!$:

$a_2p+a_1 \equiv 0 \pmod{p^2}$

Заметим, что

$a_1=\sum\limits_{k=1}^{p-1}\frac{1}{k},$

$a_2=\sum\limits_{1 \leq i < j \leq p-1}\frac{1}{ij}.$

Пусть $T:x \mapsto gx$ — биекция $\mathbb{Z}_p^{+}$ и автоморфизм $\mathbb{Z}_p^{\times}$. Тогда

$a_2=\sum\limits_{1 \leq i < j \leq p-1}\frac{1}{ij} \equiv \sum\limits_{1 \leq i < j \leq p-1}\frac{1}{T(i)T(j)}=\frac{1}{g^2}=\frac{a_2}{g^2} \pmod{p},$

а значит $a_2 \equiv 0 \pmod{p}$.

Наконец,

$a_1 \equiv 0 \pmod{p^2} \Leftrightarrow 2a_1 \equiv 0 \pmod{p^2}$

$2a_1 = \sum\limits_{k=1}^{p-1}\left( \frac{1}{k}+\frac{1}{p-k} \right) = -p\sum\limits_{k=1}^{p-1}\frac{1}{k^2} \equiv 0 \pmod{p^2},$

поскольку

$\sum\limits_{k=1}^{p-1}\frac{1}{k^2} \equiv \left( \sum\limits_{k=1}^{p-1}\frac{1}{k} \right)^2 -a_2 \equiv 0 \pmod p$.

Таким образом, теорема доказана.

Обращение теоремы как гипотеза

Утверждение, обратное к теореме Вольстенхольма, является гипотезой, а именно, если:

$\binom{2n}{n} \equiv 2 \pmod{n^k},$

при k = 3, то n простое. Это значение k является минимальным, для которого неизвестно составных решений сравнения:

• при k = 1, кроме простых чисел, сравнению удовлетворяют еще и числа, образующие последовательность A082180 в OEIS; среди них — квадраты простых чисел и несколько составных чисел (первый нетривиальный начетный пример: n = 27173 = 29·937).
• при k = 2 сравнению удовлетворяют квадраты простых Вольстенхольма (однако составных чисел, не являющихся степенями простых чисел, удовлетворяющих такому сравнению неизвестно).

Если составное число удовлетворяет сравнению, то отсюда еще не следует, что

$\binom{an}{bn} \equiv \binom{a}{b} \pmod{n^k}.$

Даже если обращение теоремы Вольстенхольма верно, его затруднительно использовать в качестве теста простоты, поскольку неизвестен способ вычисления биномиалного коэффициента $\tbinom{2n}{n}$ по модулю $\textstyle n^3$ за полиномиальное время. С другой стороны, будучи истинным, обращение теоремы Вольстенхольма может оказаться полезным для построения диофантова представления простых чисел (см. десятая проблема Гильберта), так же как и, например, теорема Вильсона.

См. также

• Малая теорема Ферма
• Теорема Вильсона
• Простые Вивериха
• Простые Вильсона
• Wall-Sun-Sun prime
• List of special classes of prime numbers

Ссылки

• Babbage, C. (1819), "«Demonstration of a theorem relating to prime numbers»", The Edinburgh philosophical journal Т. 1: 46–49, <http://books.google.com/books?id=KrA-AAAAYAAJ&pg=PA46> 
• Wolstenholme, J. (1862), "«On certain properties of prime numbers»", The Quarterly Journal of Pure and Applied Mathematics Т. 5: 35–39, <http://books.google.com/books?id=vL0KAAAAIAAJ&pg=PA35> 
• McIntosh, R. J. (1995), "«On the converse of Wolstenholme's theorem»", Acta Arithmetica Т. 71 (4): 381–389, <http://matwbn.icm.edu.pl/ksiazki/aa/aa71/aa7144.pdf> 
• Э. Б. Винберг, «Удивительные арифметические свойства биномиальных коэффициентов», Матем. просв., сер. 3, 12, Изд-во МЦНМО, М., 2008, 33-42
• The Prime Glossary: Wolstenholme prime
• Status of the search for Wolstenholme primes