Свойство пары простых чисел

[kthxbye]

Пусть дана пара простых чисел $p$ и $p+2m$.

Пусть также дан вектор $v$ заполненный последовательными натуральными числами $\left\lbrace1,2,3,\cdots,p-1\right\rbrace$.

Пусть элементы вектора подвергаются последовательной замене. На каждом шаге замены мы предвычисляем $A=\gcd(v(i),v(p-i))$, затем увеличиваем на единицу $v(i)$ если $A=1$, в противном случае увеличиваем $v(p-i)$. В конце шага мы увеличиваем $v(i)$ на $2m-1$. Всего последовательно осуществляется $p-1$ шагов.

Докажите, что после полной замены каждый элемент вектора увеличился на $2m$.

Стоит отметить, что существуют также пары $p$ и $p+2m$ где $p$ простое и $p+2m$ составное, для которых результирующий вектор обладает тем же свойством.

Гипотеза (доказать или опровергнуть): число таких составных $p+2m$ для фиксированного $m$ и произвольного $p$ конечно. Если гипотеза верна, то, как минимум для $m=1$ их вообще не существует.

[Dendr]

На самом деле, если $p=2$, то вектор состоит из одного элемента - $\{1\}$. Вследствие взаимной простоты единицы с самой собой (хотя это даже не нужно проверять, поскольку алгоритм так устроен) мы увеличиваем ее сначала на $1$, а потом на $2m-1$, получая "вектор" $\{2m+1\}$. Так что в принципе это работает всегда, для любого $m$. Но это слишком необычный случай, поэтому далее рассматриваются только нечетные $p$.

Ну по сути надо доказать следующее: применение указанной операции к паре $(i, p-i)$ дважды (с перестановкой в процессе) дает $(i+2m, p+2m-i)$. Потому что каждая пара вовлекается в процесс независимо от других.

Заметим, что если сумма двух натуральных чисел равна простому, то они взаимно просты (их общий множитель является и множителем $p$, а поскольку они оба по построению меньше $p$, то этот множитель может быть равен только $1$). Значит $\gcd{(i, p-1)}=1$, и первое применение операции даст $(i+2m, p-i)$. Сумма этих двух чисел равна $p+2m$, и если она проста, то после второго применения операции получим $(i+2m, p+2m-i)$, что и требовалось доказать.

Если $p+2m$ составное, пусть его наименьший простой делитель $q$ (очевидно, он нечетен). Тогда если если среди $p-1$ последовательных чисел $(1+2m, 2+2m, ..., p+2m-1)$ найдется хотя бы одно (а на самом-то деле два) числа с этим делителем, тогда "на выходе" мы будем иметь пару $(i+2m+1, p+2m-i-1)$.
Чтобы этого избежать, нужно, чтобы (во всяком случае) чисел было $p-1<q\le\sqrt{p+2m}$, откуда $p<\frac{\sqrt{8m+5}+3}{2}. То есть, если $m$ - фиксировано, то количество только возможных натуральных кандидатов на $p$ сильно ограничено, а мы же еще накладываем условия: а) простоты $p$, б) составности $p+2m$, в) взаимной простоты $i+2m$ и $p-i$ для всех $i$.

В частности, для $m=1$ необходимое условие $p<3,37$, двойку мы выбросили из рассмотрения, а тройка дает простую пару $(3, 5)$, то есть не годится. А для больших $m$ можно приблизительно оценивать $p<\sqrt{2m}+2$.