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

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

Невідомі складені числа, що задовольняють теоремі Волстенголма, і існує гіпотеза про те, що їх не існує. Прості числа, що задовольняють аналогічному порівнянню за модулем $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\cdot 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\cdot 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}}}$

Лейдесдорф довів, що для натурального числа $n$, взаємно простого з 6, виконується таке порівняння:

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

Обернення теореми як гіпотеза

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

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

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

• при $k=1$ крім простих чисел, порівнянню задовольняють ще й числа, що утворюють послідовність A082180 з Онлайн енциклопедії послідовностей цілих чисел, OEIS; серед них — квадрати простих чисел і кілька складених чисел (перший нетривіальний непарний приклад: $n=27173=29\cdot 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