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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку

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

то

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle a_{2}p+a_{1}\equiv 0{\pmod {p^{2}}}}$

Заметим, что

${\displaystyle a_{1}=\sum \limits _{k=1}^{p-1}{\frac {1}{k}},}$

${\displaystyle a_{2}=\sum \limits _{1\leq i<j\leq p-1}{\frac {1}{ij}}.}$

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

${\displaystyle 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}},}$

а значит ${\displaystyle a_{2}\equiv 0{\pmod {p}}}$ .

Наконец,

${\displaystyle a_{1}\equiv 0{\pmod {p^{2}}}\Leftrightarrow 2a_{1}\equiv 0{\pmod {p^{2}}}}$

${\displaystyle 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}}},}$

поскольку

${\displaystyle \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}}}$ .

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

Обобщения

Верно и более общее утверждение:

${\displaystyle {\binom {ap^{n}}{bp^{n}}}\equiv {\binom {ap^{n-1}}{bp^{n-1}}}{\pmod {p^{3n}}}}$

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

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

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

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

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

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

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

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

См. также

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

Примечания

Ссылки

• Babbage, C. (1819), , The Edinburgh philosophical journal , 1 : 46—49
• Wolstenholme, J. (1862), , The Quarterly Journal of Pure and Applied Mathematics , 5 : 35—39
• McIntosh, R. J. (1995), (PDF) , Acta Arithmetica , 71 (4): 381—389