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

[maxal]

Докажите, что 1489 не может быть делителем натурального числа $n,$ удовлетворяющего сравнению $2^n \equiv 3\pmod{n}.$

[Руст]

Проверил, что $p=1489$ простое число. По всей видимости $3$ не принадлежит мультипликативной группе остатков по модулю $p$, образованной $2$. Это можно проверить вычислив точные порядки чисел $T(2)$ и $T(3)$. Необходимо, чтобы $T(3)$ делил $T(2)$. Сразу по символам Лежандра не удалось проверить $2$ и $3$ оба квадратичные вычеты. Поэтому вычисления длинны $p-1=1488=16\cdot 3\cdot 31.$

[worm2]

$2^{637} \equiv 3\pmod{1489}$, так что не получается.

[Руст]

Тогда сложно. Знаем только, что надо показать, что при $n=1489m$ нет решения сравнений $2^{1489m}=3\pmod m \ \ m=637\pmod{744}$.
Для этого можно рассмотреть малые простые числа вида $p=2k\cdot 1489+1$ и рассмотреть остатки при делении $m$ на такие простые числа.

[maxal]

Задача простая. Первый шаг сделан.
Осталось сделать второй.

[Батороев]

Не уверен, что все учел правильно, но мне видится так:
Период повторения остатков по степеням двойки по основанию $1489$, в том числе и $3 \mod (1489)$ – $744$.
Первое появление остатка $3$, как здесь справедливо заметили, – $637$-я степень числа $2$.
Таким образом, можно составить равенство:
$637 + L\cdot 744 = 1489\cdot M$, где $L$ и $M$ – целые числа
Или $2\cdot 637 + L\cdot (1489-1) = 2M\cdot 1489.$
$2\cdot 637 + L\cdot 1489 - L = 2M\cdot 1489$
$2\cdot 637 - L = 1489\cdot (2M - L)$
Т.к. левая часть не делится на $1489$, то равенство в целых числах не возможно, следовательно, числу $1489$ - не судьба, участвовать в указанных сравнениях.

[maxal]

Батороев писал(а):

$2\cdot 637 - L = 1489\cdot (2M - L)$
Т.к. левая часть не делится на $1489$,

Почему это она не делится? Возьмите, например, $L=2\cdot 637$ или $L=2\cdot 637+1489$ и т.д. и будем вам делимость.

[Батороев]

"Ляпу" свою принимаю, но тогда, что мы имеем при $n=2056309$ и Вашем "т.д"?

[maxal]

Батороев писал(а):

"Ляпу" свою принимаю, но тогда, что мы имеем при $n=2056309$ и Вашем "т.д"?

Для $n=2056309$ число $1489$ является делителем, но данное $n$ не удовлетворяет сравнению $2^n \equiv 3\pmod{n}.$ Поэтому никаких выводов здесь сделать нельзя.

[Руст]

Будем считать, что worm нашёл минимальное решение сравнения. Тогда $T(2)>637$ и $T(2)\leq 744$ вследствие того, что $2$ квадратичный вычет, т.е. $m=637+744k$ даёт все возможные решения. Число $744$ делится на $24$, соответственно $m=13\pmod{24}$. Если бы символ Якоби $\left(\frac{2}{m}\right)=1$ а $\left(\frac{3}{m}\right)=-1$ то получилось бы доказательство не возможности деления $n$ на $1489$. Однако, дело обстоит наоборот $\left(\frac{2}{m}\right)=-1$, $\left(\frac{3}{m}\right)=1$. Поэтому, или задача решается привлечением законов взаимности более высшей степени (например кубической или биквадичной) или до чего то мы не можем додуматься или ошибся maxal.

[maxal]

Или ошибся Руст.
Ты на верном пути, но в твоих рассуждениях ошибка.

[Руст]

Да. Из $\left(\frac{2}{m}\right)=-1$,$\left(\frac{3}{m}\right)=1$ следует, что тройка должна быть чётной степенью $2$, а у нас $m=637\pmod {744}$ нечётная степень.

[maxal]

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

Итак, пусть $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$ несовместны.

[Руст]

maxal писал(а):

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

А разве, то что я писал, не решение. Правда раньше меня смущало, что $\left(\frac{2}{m}\right)=-1$,$\left(\frac{3}{m}\right)=1$. Но это противоречит нечётности n, о чём написал при последнем посте.

[maxal]

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

А разве, то что я писал, не решение. Правда раньше меня смущало, что $\left(\frac{2}{m}\right)=-1$,$\left(\frac{3}{m}\right)=1$. Но это противоречит нечётности n, о чём написал при последнем посте.

Да, решение, просто "последнего поста" не было, когда я писал свое решение. Я и сказал, что ты вплотную подошел к решению, потому как осталось исправить всего лишь одну маленькую ошибочку, что собственно и было сделано в "последнем посте".

Добавлено спустя 2 минуты 19 секунд:

Кстати, красивая задачка получилась? Я вообще совершенно случайно наткнулся на этот факт, вот и решил предложить в качестве задачки