Необходимое условие для простоты.

[Руст]

Пусть $n$ нечётное число. Запишем частичную сумму гармонического ряда

$$\sum_{k=1}^{n-1} \frac 1k =\frac{P_n}{Q_n}$$

в виде несократимой дроби.
1. Доказать, что если $n$ простое число, то числитель делится на $n$ (даже на квадрат, если $n>3$).
2. Будет ли $n$ простым, если известно, что $P_n$ делится на $n$.

[maxal]

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

А можно заметить, что $\sum_{k=1}^{n-1} \frac{1}{k} = \frac{c(n,2)}{(n-1)!}$, где $c(n,2)$ - число Стирлинга 1-го рода без знака.

[Руст]

2. Надо проверить $n=p^2$ и убедиться, что если

$$p^3|\sum_{k=1}^{p-1} \frac 1k $$

, то $n|P_n$. Такие простые числа (называемые простыми числами Волстенхольма) имеются. Пока известно два таких числа до одного миллиарда 164843 и 2124679.

[maxal]

Тогда интересно усилить второй вопрос до:

2. Будет ли n простым или степенью простого, если известно, что $P_n$ делится на n?

[Sonic86]

Верно ли, что средний биномиальный коэффициент С(n,2n)-2 делится на n^3 тогда и только тогда, когда n - простое, не 2 и не 3?
Это так называемая теорема Вольстенхольма. У меня есть доказательство для простых n, для четных n, для n, являющихся степенью простых. Очень затрудняюсь в случае нечетных n, имеющих хотя бы 2 различных простых делителя. Можно ограничиться классом n, таких, что НОД(C(n,2n);n)=1. Использовал только простые методы и симметрические многочлены, но - не помогает. Может быть есть какой-то метод, но я его не знаю - подскажите. Если что, не пытайтесь доказывать, что для нечетных n, имеющих хотя бы 2 различных простых делителя, С(n,2n)-2 делится на n - это неверно. Контрпример, кажется для n=923*53, что-то вроде этого.
Если что - есть подробности.

[нг]

Sonic86
На форуме принято записывать формулы, используя нотацию ($\TeX$; введение, справка).

[maxal]

Sonic86 писал(а):

Верно ли, что средний биномиальный коэффициент С(n,2n)-2 делится на n^3 тогда и только тогда, когда n - простое, не 2 и не 3?
Это так называемая теорема Вольстенхольма.

Теорема Вольстенхольма здесь работает только в одну сторону: если $p>3$ - простое, то $\binom{2p}{p}\equiv 2\pmod{p^3}$, но не наоборот.

Тема слита с предыдущей темой об обращении теоремы Вольстенхольма.

[Руст]

maxal писал(а):

Sonic86 писал(а):

Верно ли, что средний биномиальный коэффициент С(n,2n)-2 делится на n^3 тогда и только тогда, когда n - простое, не 2 и не 3?
Это так называемая теорема Вольстенхольма.

Теорема Вольстенхольма здесь работает только в одну сторону: если $p>3$ - простое, то $\binom{2p}{p}\equiv 2\pmod{p^3}$, но не наоборот.

Что касается утверждения Sonic86, обратное утвеждение не имеет отношения к теореме Вольстенхолма. Я уверен, что несложно найти контрпримеры типа $n=p_1p_2...p_k$ с учётом того, что $p^3|C_{mp}^{np}-C_m^k$.
В моём случае с $n|P_n$ (a не $n^2|P_n$) контрпримеры кроме квадратов (или степеней) простых чисел Вольстенхолма в принципе могут быть, однако найти их существенно сложнее. Например можно попытаться найти два простых p,q, таких что $p^2|P_q, \ q^2|P_p$ факторизуя числители для простых аргументов. Если такая пара найдётся, то $n=pq$ контрпример.

[Sonic86]

Перебрал все числа до $10^6$. Кроме ранее найденного $n=27173=29 \cdot 937$ нашел лишь еще одно нетривиальное $n=27789=3 \cdot 59 \cdot 157$. Для них $\binom{2n}{n} \equiv 2 \pmod n$. Странно они разбросаны...

(модераторам)

можно исправить свое старое сообщение?

[maxal]

Sonic86 в сообщении #473543 писал(а):

Перебрал все числа до $10^6$. Кроме ранее найденного $n=27173=29 \cdot 937$ нашел лишь еще одно нетривиальное $n=27789=3 \cdot 59 \cdot 157$. Для них $\binom{2n}{n} \equiv 2 \pmod n$.

Станности:
1) В OEIS таких указано гораздо больше: A082180.
2) Если же вы исключили степени простых, то почему тогда не нашли $418 = 2\cdot 11\cdot 19$ ?
3) Для $n=27789$ утверждение неверно: $\binom{2\cdot 27789}{27789} \equiv 23010\pmod{27789}$.

P.S. А вот ещё из той же оперы: A080469, A109760, A109769

[Sonic86]

maxal в сообщении #473549 писал(а):

2) Если же вы исключили степени простых, то почему тогда не нашли $418 = 2\cdot 11\cdot 19$ ?

Я четные не искал. Для них не очень интересно.

maxal в сообщении #473549 писал(а):

3) Для $n=27789$ утверждение неверно: $\binom{2\cdot 27789}{27789} \equiv 23010\pmod{27789}$.

Ой! Странно, вроде бы на компе все считалось, я перепроверю...
А! Я опечатался: $27889$, но это тогда $167^2$, а значит его тоже нужно исключить.
Значит до $n \leqslant 10^6$ других нечетных примеров не степеней, кроме $n=29 \cdot 937$ нет.
Для степеней неинтересно искать, поскольку можно доказать, что $\binom{2p^m}{p^m} \equiv 2 \pmod{p^3}$ и $\binom{2p^m}{p^m} \not \equiv 2 \pmod{p^4}$ при условии $\binom{2p}{p} \not \equiv 2 \pmod{p^4}$, а для простых Вольстенхольма быть может даже $\binom{2p^m}{p^m} \equiv 2 \pmod{p^4}$ (последнее не доказывал).

maxal в сообщении #473549 писал(а):

P.S. А вот ещё из той же оперы: A080469, A109760, A109769

Спасибо за ссылки.

[maxal]

Sonic86 в сообщении #473583 писал(а):

Значит до $n \leqslant 10^6$ других нечетных примеров не степеней, кроме $n=29 \cdot 937$ нет.

Следующий пример - это $2001341 = 787\cdot 2543$.

И вот еще одна похожая последовательность: A084699

[Sonic86]

maxal в сообщении #473641 писал(а):

Следующий пример - это $2001341 = 787\cdot 2543$.

Да, тоже нашел но PARI/GP интервал от $2 000 000$ до $2 002 000$ обрабатывает уже довольно долго - примерно 17 минут. Код такой:

A=2000000; C=2002000; B=binomial(2*A-3,A-2); for(k=A,C,B=B*2*(2*k-1)/k; if(Mod(k,2)==1&&!isprime(k)&&!ispower(k)&&Mod(B,k)==1,print(k)))

Хотя он минут 12 наверное только биномиальный коэффициент считал.
Или Вы иначе считали?
Я попробую еще один алгоритм через частичную факторизацию $\binom{2n-1}{n-1}-1$ и перебор его делителей, может получиться найти еще больше.

[maxal]

Sonic86 в сообщении #473647 писал(а):

Или Вы иначе считали?

Иначе - см. секцию III на моей скриптовой станичке http://home.gwu.edu/~maxal/gpscripts/

? binomod(2*2001341,2001341,2001341)
%1 = Mod(2, 2001341)
? ##
  ***   last result computed in 10 ms.

[Руст]

Во первых лучше искать через разложение n на простые множители. Пусть $n=a_1p+a_2p^2+...a_kp^k$ разложение числа $n$ в $p$ -адической системе исчисления, где $p$ - делитель $n$. Если $a_i>\frac{p-1}{2}$, то $\binom{2n}{n}$ делится на p и не годится. Если все $a_i\le \frac{p-1}{2}$, то $\binom{2n}{n}-2=\prod_i\binom{2a_i}{a_i}-2$.
Это легко вычисляется. В случае больших простых делителей с большими цифрами $2a_i<p$ это вычисление можно сократить (по сравнению с умножением по модулю $p$) примерно в десять раз, за счет усложнения алгоритмя и замены умножений на сдвиги в двоичном разряде.