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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]