1489 как делитель решения 2^n = 3 (mod n)

[Руст]

Согласен, что задача красивая.
Что касается использования кубических и биквадратных законов взаимности, то это в принципе возможно для малых чисел 2 и 3. Но там всё гораздо сложнее и я не встречал задач типа этого, решаемых с привлечением таких законов взаимности.

[maxal]

Руст писал(а):

Что касается использования кубических и биквадратных законов взаимности, то это в принципе возможно для малых чисел 2 и 3. Но там всё гораздо сложнее и я не встречал задач типа этого, решаемых с привлечением таких законов взаимности.

На всякий случай ссылки на законы взаимности высших степеней:
cubic reciprocity law
On the theory of cubic residues and nonresidues

Rational quartic reciprocity I и Rational quartic reciprocity II

И вот книжка еще: http://books.google.com/books?vid=ISBN3540669574 (в свободном доступе не нашел к сожалению)

[dmd]

1489 - это не уникальное исключение и дальше имеются подобные? Если да, то правильно ли нашел следующие 3793 и 5857?

[maxal]

dmd писал(а):

1489 - это не уникальное исключение и дальше имеются подобные? Если да, то правильно ли нашел следующие 3793 и 5857?

Такие числа имеются и дальше. Ваши расчеты верны.

[dmd]

Следующий код все такие числа отфильтрует?

if((h%24)==0,
 x=lift(Mod(k,24));
 if(x%2,
  y=kronecker(6,x);
  if(y==-1, print(p))
 )
)

здесь под $k$ понимается наименьшее решение $mod(2^k,p)=3$, $h$ - период двойки, $p$ - подходящее простое.

[maxal]

Да. Кстати, проверку if(x%2 можно выкинуть. Дело в том, что если 6 и x не будут взаимно-просты, то их символ Кронекрера будет равен 0.

[dmd]

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

Рустем вплотную подошел к решению, поэтому можно выкладывать карты на стол ;)

Итак, пусть $n=1489\cdot m$ удовлетворяет сравнению $2^n \equiv 3\pmod{n}.$
Тогда:

во-первых, (как справедливо заметили Руст и worm2), m должно удовлетворять сравнению $m\equiv 637\pmod{744}$, которое в свою очередь влечет $m\equiv 13\pmod{24}$;

во-вторых, $n$ обязано быть нечетным, а поэтому $\left(2^{(n+1)/2}\right)^2 \equiv 6\pmod{m}$ и, значит, символ Якоби $\left(\frac6m\right)=1.$

Осталось только проверить, что требования $m\equiv 13\pmod{24}$ и $\left(\frac6m\right)=1$ несовместны.

Пусть $p$ - подходящее простое, делящее решение $2^n \equiv 3\pmod{n}$, $h$ - порядок двойки по модулю $p$, $k$ - наименьшее решение $2^k \equiv 3\pmod{p}$.

Совместные условия $24\mid h$ и $\left(\frac{6}{k\%24}\right)=-1$ исключают $p$ из списка подходящих.

Обобщаемо ли это на другие делители $h$? Т.е. если $d\mid h$ и $\left(\frac{6}{k\%d}\right)=-1$, то $p$ неподходяще?

[maxal]

dmd в сообщении #588135 писал(а):

Совместные условия $24\mid h$ и $\left(\frac{6}{k\%24}\right)=-1$ исключают $p$ из списка подходящих.
Обобщаемо ли это на другие делители $h$? Т.е. если $d\mid h$ и $\left(\frac{6}{k\%d}\right)=-1$, то $p$ неподходяще?

Вряд ли. 24 здесь не просто так - дело в том, что значение символа Якоби $\left(\frac{6}{m}\right)$ имеет период 24 (то есть, $\left(\frac{6}{m}\right) = \left(\frac{6}{m\bmod 24}\right)$).

Если уж обобщать, то надо смотреть в сторону кубических и выше законов взаимности.

[maxal]

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

Если уж обобщать, то надо смотреть в сторону кубических и выше законов взаимности.

Хотя и это сомнительно - степенные символы высших порядков не обладают свойством периодичности.

[megamix62]

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

Рустем вплотную подошел к решению, поэтому можно выкладывать карты на стол ;)

Итак, пусть $n=1489\cdot m$ удовлетворяет сравнению $2^n \equiv 3\pmod{n}.$
Тогда:

во-первых, (как справедливо заметили Руст и worm2), m должно удовлетворять сравнению $m\equiv 637\pmod{744}$, которое в свою очередь влечет $m\equiv 13\pmod{24}$;

во-вторых, $n$ обязано быть нечетным, а поэтому $\left(2^{(n+1)/2}\right)^2 \equiv 6\pmod{m}$ и, значит, символ Якоби $\left(\frac6m\right)=1.$

Осталось только проверить, что требования $m\equiv 13\pmod{24}$ и $\left(\frac6m\right)=1$ несовместны.

Ответ в книге Richard Guy, автор книги Unsolved Problems in Number theory, где эта задача значится под номером F10.

[maxal]

megamix62 в сообщении #657719 писал(а):

Ответ в книге Richard Guy, автор книги Unsolved Problems in Number theory, где эта задача значится под номером F10.

Этой задачи там нет. Там задача о (бес)конечности решений рассматриваемого сравнения без каких-либо ограничений.

[megamix62]

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

megamix62 в сообщении #657719 писал(а):

Ответ в книге Richard Guy, автор книги Unsolved Problems in Number theory, где эта задача значится под номером F10.

Этой задачи там нет. Там задача о (бес)конечности решений рассматриваемого сравнения без каких-либо ограничений.

Вы правы , этой конкретной задачи нет, но для $2^n = 3 (mod n)$ Richard Guy (стр.250) дает указание на работу Маковского и что простые числа вида $ p=24\pm7 $ или $\pm11 $ на которые не дожно делится $n$

[maxal]

megamix62 в сообщении #657825 писал(а):

Richard Guy (стр.250) дает указание на работу Маковского и что простые числа вида $ p=24\pm7 $ или $\pm11 $ на которые не дожно делится $n$

1489 не является простым такого вида

[dmd]

Правильно ли понимаю, что на составные подходящие числа условие этой задачи тоже распространяется?

ckr()=
{

Z= matrix(0, 3):vec;
Z= read("pkh6.dbt"):vec;
L= (#Z~):int;

for(i=1, L,
 q= Z[i,1];
 if(!isprime(q),
  h= Z[i,3];
  if(!(h%24),
   k= Z[i,2];
   if(kronecker(6, lift(Mod(k, 24)))==-1,
    print(q,"    ",factorint(q))
   )
  )
 )
)

};

До $10^6$ таких четыре числа обнаружилось:

? ckr()
296419    [19, 1; 15601, 1]
316483    [19, 1; 16657, 1]
497059    [19, 1; 26161, 1]
724147    [19, 1; 38113, 1]

[megamix62]

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

megamix62 в сообщении #657825 писал(а):

Richard Guy (стр.250) дает указание на работу Маковского и что простые числа вида $ p=24\pm7 $ или $\pm11 $ на которые не дожно делится $n$

1489 не является простым такого вида

Вы правы , но 1489 является простым такого вида $ p=24k\pm7 $ или $\pm11 $