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

теорема про прості числа

Теорема Волстенголма (англ. Wolstenholme's theorem) стверджує, що для будь-якого простого числа виконується порівняння

де  — середній біноміальний коефіцієнт. Еквівалентне порівняння

для дав Вільгельм Люнґґрен[en][1].

Невідомі складені числа, що задовольняють теоремі Волстенголма, і існує гіпотеза про те, що їх не існує. Прості числа, що задовольняють аналогічному порівнянню за модулем називають простими числами Волстенголма.

Історія

ред.

Вперше теорему довів Джозеф Волстенголм[en] 1862 року. 1819 року Чарлз Беббідж довів аналогічне порівняння за модулем  , яке правильне для всіх простих p. Інше формулювання теореми Волстенголма дав Глашієр (J. W. L. Glaisher) під впливом теореми Люка.

Як стверджував сам Волстенголм, його теорему отримано через пару порівнянь з (узагальненими) гармонічними числами:

 
 

Прості числа Волстенголма

ред.

Просте число p називають простим числом Волстенголма тоді й лише тоді, коли:

 

Донині відомо тільки 2 простих числа Волстенголма: 16843 і 2124679 (послідовність A088164 з Онлайн енциклопедії послідовностей цілих чисел, OEIS); інші такі прості числа, якщо вони існують, перевершують  [2].

Імовірно   поводиться як псевдовипадкове число, рівномірно розподілене у відрізку  . Евристично припускають, що кількість простих чисел Волстенголма в інтервалі   оцінюється як  . З цих евристичних міркувань випливає, що наступне просте число Волстенголма лежить між   і  .

Подібні евристичні аргументи стверджують, що немає простих чисел, для яких порівняння виконується за модулем  .

Доведення

ред.

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

Комбінаторно-алгебричне доведення

ред.

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

Нехай   — просте число,  ,   — невід'ємні цілі числа. Позначимо  ,  ,   множину з   елементів, поділених на   кілець  ,   довжини  . На кожному кільці діє група обертань  . Таким чином, на всій   діє група  . Нехай   — довільна підмножина множини   з   елементів. Множину   можна вибрати   способами. Кожна орбіта множини   при дії групи   містить   елементів, де   — число часткових перетинів   з кільцями  . Існує   орбіт довжини 1 і немає орбіт довжини  . Таким чином, отримуємо теорему Беббіджа:

 

Виключаючи орбіти завдовжки  , маємо

 

Серед інших послідовностей це порівняння в разі  ,   дає нам загальний випадок другої форми теореми Волстенголма.

Перемикаємося з комбінаторики на алгебру та застосовуємо поліноміальну аргументацію. Фіксуючи  , отримуємо порівняння з поліномами від   в обох його частинах, істинне за будь-яких невід'ємних  . Отже, порівняння істинне за будь-якого цілого  . Зокрема, при  ,   отримуємо порівняння:

 

Оскільки

 

то

 

При   скорочуємо на 3 і доведення закінчено.

Подібне порівняння за модулем  :

 

для всіх натуральних  ,   істинне тоді й лише тоді, коли  ,  , тобто тоді й лише тоді, коли   — просте число Волстенголма.

Теоретико-числове доведення

ред.

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

 

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

 

Скорочуємо   і степінь   разом з модулем і потім на  :

 

Зауважимо, що

 
 

Нехай   — бієкція   та автоморфізм  . Тоді

 

а значить  .

Зрештою,

 
 

оскільки

 .

Отже, теорему доведено.

Узагальнення

ред.

Правильне і загальніше твердження:

 

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

 

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

ред.

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

 

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

  • при   крім простих чисел, порівнянню задовольняють ще й числа, що утворюють послідовність A082180 з Онлайн енциклопедії послідовностей цілих чисел, OEIS; серед них — квадрати простих чисел і кілька складених чисел (перший нетривіальний непарний приклад:  ).
  • при   порівнянню задовольняють квадрати простих чисел Волстенголма (проте складених чисел, які не є степенями простих чисел і задовольняють такому порівнянню, невідомо).

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

 

Навіть якщо обернення теореми Волстенголма істинне, його складно використовувати як тест простоти, оскільки невідомий спосіб обчислення біномного коефіцієнта   за модулем   за поліноміальний час. З іншого боку, в разі істинності, обернення теореми Волстенголма може бути корисним для побудови діофантового подання простих чисел (див. десяту проблему Гільберта), так само, як і, наприклад, теорема Вілсона.

Див. також

ред.

Примітки

ред.
  1. Granville, Andrew (1997), Binomial coefficients modulo prime powers (PDF), Canadian Mathematical Society Conference Proceedings, 20: 253—275, MR 1483922, архів оригіналу (PDF) за 2 лютого 2017
  2. McIntosh, R. J.; Roettger, E. L. (2007), A search for Fibonacci−Wieferich and Wolstenholme primes, Mathematics of Computation, 76 (260): 2087—2094, Bibcode:2007MaCom..76.2087M, CiteSeerX 10.1.1.105.9393, doi:10.1090/S0025-5718-07-01955-2
  3. Leudesdorf, C. (1888). Some results in the elementary theory of numbers. Proc. London Math. Soc. 20: 199—212. doi:10.1112/plms/s1-20.1.199.

Посилання

ред.