Остатки по кругу

[Dmitriy40]

nnosipov в ЛС (далее всё с его разрешения) высказал гипотезу что около $1$ всегда стоит число равное минимальному первообразному корню по модулю $p$ (A001918).
Проверка показала что для всех известных выше решений это так и есть (код на PARI/GP):

? apply(p->lift(znprimroot(p)), [17, 251, 257, 433, 641, 1459, 3457, 3889, 21169, 39367, 54001, 65537, 110251, 114689, 139969, 210913, 246241, 274177])
%1 = [3, 6, 3, 5, 3, 3, 7, 11, 13, 3, 11, 3, 7, 3, 13, 17, 11, 5]

Отдельно проверил что для чисел до 300000 нет решений с меньшими числами около 1.
Полная проверка показала что до 52700 нет других решений кроме этих и соответственно в этих рамках гипотеза выполняется.

Я осмелился расширить его гипотезу исключив число 2 из списка возможных соседей числа 1 даже если именно оно является минимальным первообразным корнем по модулю $p$ - просто по факту наблюдений. Без всяких обоснований.

Запустив проверку в расширенном варианте (около 1 стоит минимальный первообразный корень по модулю простого и он больше 2) нашёл ещё члены этой последовательности: $\{319489, 629857, 746497, 974849, 995329, 1161217\}$. Около $1$ стоят числа соответственно $\{23, 5, 5, 3, 7, 13\}$.

Гарантию отсутствия пропущенных членов могу дать пока только до 52700.

Про доказательство гипотезы (и вообще математику в теме) сказать ничего не могу. Со слов nnosipov это может оказаться весьма непросто.

[maxal]

Dmitriy40
nnosipov
Для произвольного нечётного простого $p$ гипотезу о том, что рядом с единицей не может стоять ничего кроме первообразного корня по модулю $p$, можно доказать так.

Пусть рядом с единицей стоит $q$, не являющееся первообразным корнем.
В моих обозначениях имеем $a_0=1$, $a_1=q$ и $a_k = \frac{q^k}{2^{k^2-k}}$. Покажем, что существуют такие $k<m$, что $m-k < p-1$ и $a_k\equiv a_m\pmod p$, т.е. $q^{m-k}\equiv 2^{(m-k)(m+k-1)}\pmod p$. Зафиксируем первообразный корень $z$ и пусть $q\equiv z^{dt}\pmod p$ и $2\equiv z^{s}\pmod p$, где $d=\gcd(dt,p-1)$. Так как $q$ - не первообразный корень, то $d>1$.
В новых терминах условие $a_k\equiv a_m\pmod p$ равносильно

$$(dt - s(m+k-1))\cdot (m-k) = 0\pmod{p-1}.$$

Если $g:=\gcd(d,s)>1$, то достаточно взять любыe $m,k$ с разностью $m-k=\frac{p-1}g$. В дальнейшем полагаем, что $g=1$.

Если существует нечётный простой делитель $r\mid d$, то положим $m=k+\frac{p-1}{r}$ и потребуем, чтобы $dt - s(m+k-1) = dt - s(2k+\frac{p-1}{r}-1)\equiv 0\pmod r$, что разрешимо относительно $k$, так как $r$ не делит $2s$.

Осталось рассмотреть случай, когда $d$ - это степень 2-ки, а $s$ - нечетно. Пусть $p-1 = 2^u v$, где $v$ - нечетно. Понятно, что $u\geq \nu_2(d)\geq 1$ и поэтому $v<p-1$. Полагаем $m=k+v$ и требуем, чтобы $dt - s(m+k-1) = dt - s(2k+v-1)\equiv 0\pmod{2^u}$, т.е. $\frac{d}2t - s (k+\frac{v-1}2)\equiv 0\pmod{2^{u-1}}$, что разрешимо относительно $k$.

Таким образом, искомые $m,k$ всегда существуют.

[Dmitriy40]

Осталось усилить доказательство (если оно валидное, я не компетентен) до минимального первообразного корня по модулю $p$, как и есть у nnosipov. Т.е. что не бывает корней не дающих решение. Хотя конечно и так неплохо, корней несколько меньше чем $p-1$.

[maxal]

Dmitriy40
Если один первообразный корень работает, то работает и всякий другой, так как из неразрешимости $(t - s(m+k-1))(m-k)\equiv 0\pmod{p-1}$ для $m-k<p-1$ следует неразрешимость $(t' - s'(m+k-1))(m-k)\equiv 0\pmod{p-1}$, где $(t',s')$ получаются из $(t,s)$ умножением на любое число взаимно простое с $p-1$, что соответствует замене первообразного корня $q= z^t\bmod p$ на первообразный же корень $q':=z^{t'}\bmod p$.

-- Tue Sep 03, 2024 15:05:10 --

Кстати, не обязательно генерировать вычеты по кругу и проверять их попарное различие. Можно проверить разрешимость $(t - s(m+k-1))(m-k)\equiv 0\pmod{p-1}$ для $m-k<p-1$, непосредственно прогнав $\gcd(m-k,p-1)$ по различным собственным делителям $d\mid p-1$, полагая $m-k=de$, где $\gcd(de,p-1)=d<p-1$, и для каждой такой пары $(d,e)$ проверить разрешимость сравнения $t-s(2k+de-1)\equiv 0\pmod{\frac{p-1}d}$. Если для какого-то $d$ последнее сравнение разрешимо, то проверка провалена, а иначе $p$ - хорошое и искомая расстановка вычетов возможна.

-- Tue Sep 03, 2024 15:15:09 --

PS. Ну а сравнение разрешимо, если и только если $\gcd(\frac{p-1}d,2s)\mid t-s(de-1)$.

[maxal]

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

PS. Ну а сравнение разрешимо, если и только если $\gcd(\frac{p-1}d,2s)\mid t-s(de-1)$.

Продолжим. Наша цель определить хорошесть заданного нечётного простого $p$. В виду свободы выбора первообразного корня, можно считать, что $s = \frac{p-1}{\mathrm{ord}_p(2)}\mid p-1$. Тогда, так как $t$ соответствует первообразному корню, то $\gcd(s,t)=\gcd(p-1,s,t)=\gcd(p-1,t)=1$.

Пусть $r$ - это максимальный делитель $p-1$ имеющий тот же радикал, что и $2s$. Если $r<p-1$, то $p$ - плохое, что доказывается выбором $(d,e)=(r,1)$. Поэтому для хорошего $p$ с необходимостью имеем, что радикалы $p-1$ и $2s$ совпадают. Будем считать, что это условие выполнятся.

Далее, делимости нет если $de$ нечётно, так как $2\mid \gcd(\frac{p-1}d,2s)$, но $t-s(de-1)\equiv t\equiv 1\pmod2$. Поэтому для плохого $p$, свидетельствующее $d$ будет чётно.

Наконец, если $\gcd(\frac{p-1}d,2s)$ содержит простой делитель числа $s$, то он не делит $t$ и плохой делимости не будет. Оставшийся плохой случай, это - нечётное $s$ и четное $\frac{p-1}d$ взаимно-простое с $s$, что имеет место для $p\equiv 1\pmod4$ и, например, $(d,e)=(\frac{p-1}2,1)$.

Итак, $p$ - хорошее только если для $s:=\frac{p-1}{\mathrm{ord}_p(2)}$ выполняется $\mathrm{rad}(p-1)=\mathrm{rad}(2s)$, за исключением случая, когда $p\equiv 1\pmod4$ и $s\equiv1\pmod2$.

? forprime(p=3,10^8, s=(p-1)/znorder(Mod(2,p)); if(vecprod(factor(p-1)[,1])==vecprod(factor(2*s)[,1]) && (p%4!=1 || s%2!=1),print1(p,", ")) )
3, 17, 251, 257, 433, 641, 1459, 3457, 3889, 21169, 39367, 54001, 65537, 110251, 114689, 139969, 210913, 246241, 274177, 319489, 629857, 746497, 974849, 995329, 1161217, 1299079, 1492993, 1769473, 2020001, 2424833, 2555521, 2654209, 5038849, 5304641, 5419387, 5746001, 6049243, 6561001, 6700417, 6858433, 8039359, 8503057, 10113049, 10194337, 10775777, 11337409, 12400001, 12644353, 13381633, 13631489, 14155777, 17360407, 26017793, 26232337, 26891201, 27993601, 28311553, 28934011, 33436801, 33975937, 36720001, 39051073, 40960001, 45592577, 47904049, 56337751, 63700993, 63766529, 75600001, 93312001, 96468751, 

[Dmitriy40]

maxal

[nnosipov]

maxal
Здорово! Рад, что все получилось довести до ума.