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

Теорема Вольстенхольма (англ. 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}$, называются простыми Вольстенхольма.

История

Впервые теорема была доказана Джозефом Вольстенхольмом в 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_{2}p^{2}+a_{1}p+(p-1)!\equiv (p-1)!{\pmod {p^{3}}}$

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

$a_{2}p+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 {ap^{n}}{bp^{n}}}\equiv {\binom {ap^{n-1}}{bp^{n-1}}}{\pmod {p^{3n}}}$

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

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

${\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}$ за полиномиальное время. С другой стороны, будучи истинным, обращение теоремы Вольстенхольма может оказаться полезным для построения диофантова представления простых чисел (см. десятая проблема Гильберта), так же как и, например, теорема Вильсона.

См. также

• Малая теорема Ферма
• Теорема Вильсона
• Простое число Вифериха
• Число Вильсона
• Простое число Фибоначчи — Вифериха
• Список специальных классов простых чисел

Ссылки

• Babbage, C. (1819), "Demonstration of a theorem relating to prime numbers", The Edinburgh philosophical journal, 1: 46—49
• Wolstenholme, J. (1862), "On certain properties of prime numbers", The Quarterly Journal of Pure and Applied Mathematics, 5: 35—39
• McIntosh, R. J. (1995), "On the converse of Wolstenholme's theorem" (PDF), Acta Arithmetica, 71 (4): 381—389
• Э. Б. Винберг, «Удивительные арифметические свойства биномиальных коэффициентов», Матем. просв., сер. 3, 12, Изд-во МЦНМО, М., 2008, 33-42
• The Prime Glossary: Wolstenholme prime
• Status of the search for Wolstenholme primes