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

Теорема Вольстенхольма утверждает, что для любого простогочисла p>3p>3 выполняется сравнение

(2pp)2(modp3),(2pp)2(modp3),
 где (2pp)(2pp) — средний биномиальный коэффициент.Эквивалентное сравнение

(apbp)(ab)(modp3).(apbp)(ab)(modp3).
 Неизвестны составные числа, удовлетворяющие теореме Вольстенхольма, исуществует гипотеза о том, что их не существует. Простые,удовлетворяющие аналогичному сравнению по модулю p4p4 называютсяпростыми Вольстенхольма.

История


 Впервые теорема была доказана Джозефом Вольстенхольмом (JosephWolstenholme) в 1862 году. В 1819 году Чарльз Беббидж доказаланалогичное сравнение по модулю p2p2, которое верно для всех простыхp. Вторая формулировка теоремы Вольстенхольма была дана Глашиером(J. W. L. Glaisher) под влиянием теоремы Люка.
 Как утверждал сам Вольстенхольм, его теорема была получена через парусравнений с (обобщенными) гармоническими числами:

1+12+13++1p10(modp2),1+12+13++1p10(modp2),
1+122+132++1(p1)20(modp).1+122+132++1(p1)20(modp).

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


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

(2pp)2(modp4).(2pp)2(modp4).
 До сих пор известно только 2 простых Вольстенхольма: 16843 и 2124679 ;остальные такие простые, если они существуют, превосходят 109109.
 Предположительно (2pp)2p3modp(2pp)2p3modp ведетсебя как псевдослучайное число равномерно распределённое в отрезке[0,p1][0,p1]. Эвристически предполагается, что количество простыхВольстенхольма в интервале (K,N)(K,N) оценивается какlnlnNlnlnKlnlnNlnlnK. Из этих эвристических соображений следует, чтоследующее простое Вольстенхольма лежит между 109109 и 10241024.
 Сходные эвристические аргументы утверждают, что не существует простых,для которых сравнение выполняется по модулю p5p5.

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


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

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


 Приведем доказательство Глашиера с использованием комбинаторики иалгебры.
 Пусть p — простое число, a, b — неотрицательныецелые числа. Обозначим A=(aij)A=(aij), i=1,,ai=1,,a, j=1,,pj=1,,pмножество из a·p элементов, разделенных на a колецKi=(aij)Ki=(aij), j=1,,pj=1,,p длины p. На каждом кольце действуетгруппа вращений CpZpCpZp. Таким образом, на всемA действует группа ZapZap. Пусть B —произвольное подмножество множества A из b·p элементов.Множество B можно выбрать (apbp)(apbp) способами.Каждая орбита множества B при действии группы ZapZapсодержит pkpk элементов, где k — число частичных пересеченийB с кольцами KiKi. Существует (ab)(ab) орбитдлины 1 и не существует орбит длины p. Таким образом, мы получаемтеорему Беббиджа:

(apbp)(ab)(modp2).(apbp)(ab)(modp2).
 Исключая орбиты длиной p2p2, мы получаем

(apbp)(ab)+(a2)((2pp)2)(a2b1)(modp3).(apbp)(ab)+(a2)((2pp)2)(a2b1)(modp3).
 Среди прочих последовательностей, это сравнение в случае a=2a=2, b=1b=1даёт нам общий случай второй формы теоремы Вольстенхольма.
 Переключаемся с комбинаторики на алгебру и применяем полиномиальнуюаргументацию. Фиксируя b мы получаем сравнение, с полиномами отa в обоих его частях, верное при любых неотрицательных a.Следовательно, сравнение верно при любом целом a. В частности,при a=1a=1, b=1b=1 получаем сравнение:

(pp)(11)+(12)((2pp)2)(modp3).(pp)(11)+(12)((2pp)2)(modp3).
 Поскольку

(pp)=(1)p2(2pp),(pp)=(1)p2(2pp),
 то

3(2pp)6(modp3).3(2pp)6(modp3).
 При p3p3 сокращаем на 3 и доказательство закончено.
 Сходное сравнение по модулю p4p4:

(apbp)(ab)(modp4)(apbp)(ab)(modp4)
 для всех натуральных a, b верно тогда и только тогда,когда a=2a=2, b=1b=1, то есть тогда и только тогда, когда p —простое Вольстенхольма.

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


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

p1k=1(p1)!(modp3)k=1p1(p1)!(modp3)
 Левая часть — многочлен от p, перемножим скобки и в полученноммногочлене отбросим степени p, большие 3, получим:

a2p2+a1p+(p1)!(p1)!(modp3)a2p2+a1p+(p1)!(p1)!(modp3)
 Сокращаем (p1)!(p1)! и степень p вместе с модулем и затем на(p1)!(p1)!:

a2p+a10(modp2)a2p+a10(modp2)
 Заметим, что

a1=p1k=11k,a1=k=1p11k,
a2=1i<jp11ij.a2=1i<jp11ij.
 Пусть T:xgxT:xgx — биекция Z+pZ+p и автоморфизмZ×pZ×p. Тогда

a2=1i<jp11ij1i<jp11T(i)T(j)=1g2=a2g2(modp),a2=1i<jp11ij1i<jp11T(i)T(j)=1g2=a2g2(modp),
 а значит a20(modp)a20(modp).
 Наконец,

a10(modp2)2a10(modp2)a10(modp2)2a10(modp2)
2a1=p1k=1(1k+1pk)=pp1k=11k20(modp2),2a1=k=1p1(1k+1pk)=pk=1p11k20(modp2),
 поскольку

p1k=11k2(p1k=11k)2a20(modp)k=1p11k2(k=1p11k)2a20(modp).
 Таким образом, теорема доказана.

Обобщения


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

(apnbpn)(apn1bpn1)(modp3n)(apnbpn)(apn1bpn1)(modp3n)

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


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

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

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

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

(anbn)(ab)(modnk).(anbn)(ab)(modnk).
 Даже если обращение теоремы Вольстенхольма верно, его затруднительноиспользовать в качестве теста простоты, поскольку неизвестен способвычисления биномиального коэффициента (2nn) по модулюn3 за полиномиальное время. С другой стороны, будучиистинным, обращение теоремы Вольстенхольма может оказаться полезным дляпостроения диофантова представления простых чисел (см. десятая проблемаГильберта), так же как и, например, теорема Вильсона.