Теорема Волстенголма

Теорема Волстенголма (англ. 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\geq 5}$ дав Вільгельм Люнґґрен^[en][1].

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

Вперше теорему довів Джозеф Волстенголм^[en] 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 (послідовність A088164 з Онлайн енциклопедії послідовностей цілих чисел, OEIS); інші такі прості числа, якщо вони існують, перевершують ${\displaystyle 10^{9}}$^[2].

Імовірно ${\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}}$.

Існує кілька способів доведення теореми Волстенголма.

Наведемо доведення Глашієра з використанням комбінаторики та алгебри.

Нехай ${\displaystyle p}$ — просте число, ${\displaystyle a}$, ${\displaystyle b}$ — невід'ємні цілі числа. Позначимо ${\displaystyle A=(a_{ij})}$, ${\displaystyle i=1,\dots ,a}$, ${\displaystyle j=1,\dots ,p}$ множину з ${\displaystyle a\cdot p}$ елементів, поділених на ${\displaystyle a}$ кілець ${\displaystyle K_{i}=(a_{ij})}$, ${\displaystyle j=1,\dots ,p}$ довжини ${\displaystyle p}$. На кожному кільці діє група обертань ${\displaystyle C_{p}\cong \mathbb {Z} _{p}}$. Таким чином, на всій ${\displaystyle A}$ діє група ${\displaystyle \mathbb {Z} _{p}^{a}}$. Нехай ${\displaystyle B}$ — довільна підмножина множини ${\displaystyle A}$ з ${\displaystyle b\cdot p}$ елементів. Множину ${\displaystyle B}$ можна вибрати ${\displaystyle \textstyle {\binom {ap}{bp}}}$ способами. Кожна орбіта множини ${\displaystyle B}$ при дії групи ${\displaystyle \mathbb {Z} _{p}^{a}}$ містить ${\displaystyle p^{k}}$ елементів, де ${\displaystyle k}$ — число часткових перетинів ${\displaystyle B}$ з кільцями ${\displaystyle K_{i}}$. Існує ${\displaystyle \textstyle {\binom {a}{b}}}$ орбіт довжини 1 і немає орбіт довжини ${\displaystyle 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}$ дає нам загальний випадок другої форми теореми Волстенголма.

Перемикаємося з комбінаторики на алгебру та застосовуємо поліноміальну аргументацію. Фіксуючи ${\displaystyle b}$, отримуємо порівняння з поліномами від ${\displaystyle a}$ в обох його частинах, істинне за будь-яких невід'ємних ${\displaystyle a}$. Отже, порівняння істинне за будь-якого цілого ${\displaystyle 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}}}}$

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

Подамо біноміальний коефіцієнт як відношення факторіалів, скоротимо ${\displaystyle p!}$ і скоротимо ${\displaystyle p}$ в біноміальному коефіцієнті і перенесемо чисельник у праву частину, отримуємо:

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

Ліва частина — многочлен від ${\displaystyle p}$, перемножимо дужки і в отриманому многочлені відкинемо степені ${\displaystyle p}$, більші 3, отримаємо:

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

Скорочуємо ${\displaystyle (p-1)!}$ і степінь ${\displaystyle 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 n}$, взаємно простого з 6, виконується таке порівняння:^[3]

${\displaystyle \sum _{i=1 \atop (i,n)=1}^{n-1}{\frac {1}{i}}\equiv 0{\pmod {n^{2}}}.}$

Твердження, обернене до теореми Волстенголма, є гіпотезою, а саме, якщо

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

при ${\displaystyle k=3}$, то ${\displaystyle n}$ просте. Це значення ${\displaystyle k}$ є найменшим, для якого невідомо складених розв'язків порівняння:

• при ${\displaystyle k=1}$ крім простих чисел, порівнянню задовольняють ще й числа, що утворюють послідовність A082180 з Онлайн енциклопедії послідовностей цілих чисел, OEIS; серед них — квадрати простих чисел і кілька складених чисел (перший нетривіальний непарний приклад: ${\displaystyle n=27173=29\cdot 937}$).
• при ${\displaystyle k=2}$ порівнянню задовольняють квадрати простих чисел Волстенголма (проте складених чисел, які не є степенями простих чисел і задовольняють такому порівнянню, невідомо).

Якщо складене число задовольняє порівнянню, то звідси ще випливає, що

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

Навіть якщо обернення теореми Волстенголма істинне, його складно використовувати як тест простоти, оскільки невідомий спосіб обчислення біномного коефіцієнта ${\displaystyle {\tbinom {2n}{n}}}$ за модулем ${\displaystyle \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