2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Остатки по кругу
Сообщение06.08.2024, 07:15 
Заслуженный участник


20/12/10
9000
Пусть $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).

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение10.08.2024, 20:20 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение01.09.2024, 15:18 


23/01/07
3469
Новосибирск
nnosipov в сообщении #1648604 писал(а):
$p \in \{17,251,257,433,641,\dots\}$ (эта последовательность простых чисел отсутствует в OEIS).

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

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение01.09.2024, 15:26 
Заслуженный участник


20/12/10
9000
Батороев в сообщении #1652664 писал(а):
Интересно, если продолжить последовательность, то не выйдет она на наименьший делитель $274177$ второго составного числа Ферма $F_{6}$?
Мне тоже интересно, что там с делителями чисел Ферма. Но я не знаю, как быстро считать члены той последовательности.

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение01.09.2024, 15:48 


23/01/07
3469
Новосибирск
nnosipov
Может, Dmitriy40 Вам сумеет помочь? Он человек отзывчивый... когда сам не сильно занят.

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение01.09.2024, 15:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение01.09.2024, 16:13 


23/01/07
3469
Новосибирск
nnosipov
Ну, так?- Так так!

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение01.09.2024, 22:07 
Заслуженный участник


20/08/14
11622
Россия, Москва
Батороев в сообщении #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$.

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение02.09.2024, 03:59 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение02.09.2024, 07:53 
Заслуженный участник


20/12/10
9000
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$.)

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение02.09.2024, 20:08 
Модератор
Аватара пользователя


11/01/06
5699
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}$, ч.т.д.

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение03.09.2024, 06:26 
Заслуженный участник


20/12/10
9000
maxal в сообщении #1652854 писал(а):
Нас интересует, когда цикл замкнётся
А разве очевидно, что этого достаточно? Скажем, по модулю 13 последовательность $a_k$ ведет ведет себя периодически, но период имеет вид: 1, 3, 12, 12, 3, 1, 12, 10, 1, 1, 10, 12. Все-таки $a_k$ это не чистая экспонента.

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение03.09.2024, 06:55 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение03.09.2024, 06:59 
Заслуженный участник


20/12/10
9000
maxal в сообщении #1652907 писал(а):
Но аргументы те же, что и выше.
Надеюсь, что да. У меня несколько другой подход, поэтому сразу неочевидно.

 Профиль  
                  
 
 Re: Остатки по кругу
Сообщение03.09.2024, 16:59 
Модератор
Аватара пользователя


11/01/06
5699
$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}$, ч.т.д.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group