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

[nnosipov]

Пусть $n>1$ таково, что число Ферма $F_n=2^{2^n}+1$ является простым. Можно ли расставить по кругу все ненулевые остатки от деления на $F_n$ так, чтобы для любых трех последовательных остатков $a$, $b$, $c$ число $b^2-4ac$ делилось на $F_n$?

Комментарий. В оригинале вместо $F_n$ было произвольное простое число $p>3$, а вместо выражения $b^2-4ac$ было выражение $b^2-ac$. Я случайно наткнулся на эту простую задачу на ютубе, но когда пересказывал ее своим студентам, ошибся в условии, машинально написав на доске "дискриминант" $b^2-4ac$. В итоге получилось то, что получилось выше. Если теперь здесь $F_n$ заменить на произвольное простое число $p>3$, то утвердительный ответ будет уже не всегда, а только для $p \in \{17,251,257,433,641,\dots\}$ (эта последовательность простых чисел отсутствует в OEIS).

[Руст]

В оригинале просто, достаточно брать $d^n\mod p$. Здесь геометрическую прогрессию по моду $F_n$ можно немного модернизировать степенями двойки. Благо мало степеней двойки отличных от 1 (точнее $2^{n+1}<2\log_2(F_n)$.

[Батороев]

nnosipov в сообщении #1648604 писал(а):

$p \in \{17,251,257,433,641,\dots\}$ (эта последовательность простых чисел отсутствует в OEIS).

Обратил внимание, что в указанном Вами ряду есть наименьший делитель $641$ первого составного числа Ферма $F_{5}$. Интересно, если продолжить последовательность, то не выйдет она на наименьший делитель $274177$ второго составного числа Ферма $F_{6}$?

[nnosipov]

Батороев в сообщении #1652664 писал(а):

Интересно, если продолжить последовательность, то не выйдет она на наименьший делитель $274177$ второго составного числа Ферма $F_{6}$?

Мне тоже интересно, что там с делителями чисел Ферма. Но я не знаю, как быстро считать члены той последовательности.

[Батороев]

nnosipov
Может, Dmitriy40 Вам сумеет помочь? Он человек отзывчивый... когда сам не сильно занят.

[nnosipov]

Да это скорее праздный интерес. Сама задача-то результат ошибки, из разряда головоломок без особого смысла.

[Батороев]

nnosipov
Ну, так?- Так так!

[Dmitriy40]

Батороев в сообщении #1652664 писал(а):

nnosipov в сообщении #1648604 писал(а):

$p \in \{17,251,257,433,641,\dots\}$ (эта последовательность простых чисел отсутствует в OEIS).

Обратил внимание, что в указанном Вами ряду есть наименьший делитель $641$ первого составного числа Ферма $F_{5}$. Интересно, если продолжить последовательность, то не выйдет она на наименьший делитель $274177$ второго составного числа Ферма $F_{6}$?

Выйдет.

nnosipov
Продолжение последовательности: $p \in \{17,251,257,433,641,1459,3457,3889,\dots\}$.
Следующее значение больше $13000$.

nnosipov в сообщении #1652670 писал(а):

Мне тоже интересно, что там с делителями чисел Ферма. Но я не знаю, как быстро считать члены той последовательности.

По двум соседним числам вектора остатков (перестановки) можно однозначно получить третье число (если знаем $a,b$, то $c=\frac{b^2}{4a}\pmod{p}$, в кольце ненулевых остатков по простому числу деление всегда однозначно). Соответственно для однозначного задания вектора остатков достаточно указать любую пару соседних чисел. Например число рядом с $1$ (без разницы слева или справа, просто будут две зеркальные перестановки). Если допустимых перестановок несколько (а так бывает), можно указать например минимальное число около $1$. Для $p \in \{1459,3457,3889\}$ эти остатки около $1$ будут соответственно $x \in \{3,7,11\}$.
Для $p=274177$ остаток около $1$ например $5$.

Ну и соответственно для проверки простого $p$ достаточно перебрать все остатки $2 \dots p-1$ в любом порядке и попытаться построить вектор остатков без повторов по указанной формуле (считая одно из чисел равным $1$ или любому другому остатку, тогда его исключить из перебора), если получилось (и закольцевалось), то ОК, если нет, значит простое $p$ в последовательность не входит.
$p=274177$ так проверяется мгновенно (тысячные доли секунды или меньше). Простые около $10000$ проверяются на отсутствие в последовательности от долей секунды до десятка секунд. Могу привести код на PARI/GP.

-- 01.09.2024, 22:11 --

$F_4=65537$ тоже попадет в последовательность, около $1$ будет остаток например $3$.

[Dmitriy40]

Ещё несколько чисел из той же последовательности (но без гарантии отсутствия пропущенных): $21169, 39367, 54001, 65537, 110251, 114689, 139969, 210913, 246241, 274177$.
Для всех число около $1$ меньше $20$. Похоже это достаточно общее (частое) условие, что наименьшее число около $1$ может быть очень малым.

[nnosipov]

Dmitriy40
Спасибо за проведенные эксперименты. Я на Maple перебрал все простые $p$ только до 1000. Можно, как выяснилось, до 13000. Проблема в том, как это продвинуть существенно дальше. Здесь надо думать, как для проверки данного $p$ избежать полного перебора, и здесь мне не удалось ничего придумать.

Dmitriy40 в сообщении #1652706 писал(а):

Для $p=274177$ остаток около $1$ например $5$.

Была у меня гипотеза, что для делителей чисел Ферма тоже хватит тройки, но, получается, это не так.

Dmitriy40 в сообщении #1652706 писал(а):

$F_4=65537$ тоже попадет в последовательность, около $1$ будет остаток например $3$.

Для любого простого числа Ферма $F_n$ при $n>1$ сгодится тройка, это и составляет содержание задачи. Доказательство несложное, но его здесь пока никто не написал. (Понятно, что для известных простых $F_n$ утверждение проверяется непосредственно, но речь идет о доказательстве для любого гипотетического простого $F_n$.)

[maxal]

nnosipov в сообщении #1652728 писал(а):

Для любого простого числа Ферма $F_n$ при $n>1$ сгодится тройка, это и составляет содержание задачи. Доказательство несложное, но его здесь пока никто не написал. (Понятно, что для известных простых $F_n$ утверждение проверяется непосредственно, но речь идет о доказательстве для любого гипотетического простого $F_n$.)

Если $a_0=1$, $a_1=3$, $a_{k+1} = a_k^2/(4a_{k-1})$, то в общем виде имеем $a_k = \frac{3^k}{2^{k(k-1)}}$. Нас интересует, когда цикл замкнётся, т.е. минимальное $m>0$ такое, что $3^m\equiv 2^{m(m-1)}\pmod{F_n}$. Так как 3 - неквадрат (и первообразный корень) по модулю $F_n$, то $m$ - обязано быть чётным.

Если $\nu_2(m)\leq n$, то возводя последнее сравнение в степень $2^{n-\nu_2(m)}$ имеем $3^{m2^{n-\nu_2(m)}}\equiv -1\pmod{F_n}$, откуда $2^n-1 = \nu_2(m2^{n-\nu_2(m)}) = n$, что возможно только для тривиального случая $n=1$.

Если же $\nu_2(m)>n$, то сравнение приобретает вид $3^m\equiv 1\pmod{F_n}$, откуда $m=2^{2^n}$, ч.т.д.

[nnosipov]

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

Нас интересует, когда цикл замкнётся

А разве очевидно, что этого достаточно? Скажем, по модулю 13 последовательность $a_k$ ведет ведет себя периодически, но период имеет вид: 1, 3, 12, 12, 3, 1, 12, 10, 1, 1, 10, 12. Все-таки $a_k$ это не чистая экспонента.

[maxal]

nnosipov
Да, нужно предположить, что $a_k\equiv a_m\pmod{F_n}$ для $k<m$ и вывести, что $m-k=2^{2^n}$. Но аргументы те же, что и выше.

[nnosipov]

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

Но аргументы те же, что и выше.

Надеюсь, что да. У меня несколько другой подход, поэтому сразу неочевидно.

[maxal]

$a_k\equiv a_m\pmod{F_m}$ эквивалентно $3^{m-k} \equiv 2^{(m-k)(m+k-1)}\pmod{F_n}$ и далее аргументация дословно повторяет случай $k=0$ с заменой $m$ на $m-k$. Повторю здесь для полноты картины:

Так как 3 - неквадрат (и первообразный корень) по модулю $F_n$, то $m-k$ - обязано быть чётным.

Если $\nu_2(m-k)\leq n$, то возводя последнее сравнение в степень $2^{n-\nu_2(m-k)}$ имеем $3^{(m-k)2^{n-\nu_2(m-k)}}\equiv -1\pmod{F_n}$, откуда $2^n-1 = \nu_2((m-k)2^{n-\nu_2(m-k)}) = n$, что возможно только для тривиального случая $n=1$.

Если же $\nu_2(m-k)>n$, то сравнение приобретает вид $3^{m-k}\equiv 1\pmod{F_n}$, откуда $m-k=2^{2^n}$, ч.т.д.