новое решение сравнения 2^n = 3 (mod n)

[maxal]

Отыскал новое решение сравнения $2^n\equiv 3\pmod{n}.$ А именно:

$$n = 3468371109448915$$

Таким образом, общее количество известных решений увеличивается до 4-х. Три других решения перечислены на MathWorld.

[Руст]

Я не понял, имеет ли решение такого сравнения хоть какое то применение.

[maxal]

Применения мне неизвестны (как впрочем и у многих других математических результатов).
Но это красивая и вычислительно-сложная математическая задача.

[Brukvalub]

Как я понял, Вы получили это решение в ходе тонко организованного численного поиска, и самым трудным в таком поиске является быстрое оперирование с очень большими числами на компъютере? Или Вы привлекали и какие-нибудь ранее не известные априорные факты о структуре решения?

[Руст]

Очевидно только, что n нечётное, не простое и не делится на 3. По видимому, искал в виде:
$n=mp, \ p|2^m-3, \ p=a(m)(mod \ per_2(m)), \ $2^{na(m)}=3$,
т.е. выбирая не очень большие m, вычисляем a(m) и проверяем нет ли делителя числа 2^m-3, дающего нужный остаток при делении на per2(m).
Но вряд ли стоит тратить время на такие вычисления без приложений.

[maxal]

Да, искал в виде $n=pm,$ где $p$ простое. При этом $m$ должно удовлетворять некоторому сравнению по модулю мультиприкативного порядка $ord_p(2).$ Поэтому, если $p$ является делителем решения $n,$ то $n$ удовлетворяет некоторому сравнению по модулю $p\cdot ord_p(2).$ Фиксируем $p$ и пробегаем по подходящим значениям $n$ (с шагом $p\cdot ord_p(2)$, я также учитывал неделимость на 2 и 3) вплоть до выбранного предела.
Моей исходной целью было доказать, что 4700063497 и 8365386194032363 - это единственные решения меньшие $10^{16}$ (почему-то была такая уверенность), но вдруг вылезло новое решение :)

А насчет тратить время или нет - каждый решает для себя. Я никого ни к чему не призывал.

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

Кстати, о том, как было найдено самое большое из известных решений, можно прочитать тут. Нашел его такой небезызвестный человек как Питер Монтгомери. Интерес к задаче со стороны именитых ученых чего-нибудь да значит?

[maxal]

А еще со мной связался Richard Guy, автор книги Unsolved Problems in Number theory, где эта задача значится под номером F10. В следующей редакции в ней будет упомянуто найденное решение.

[Brukvalub]

Судя по описанной Вами реакции специалистов в теори чисел, Вас можно поздравить с получением неплохого результата, что я с удовольствием и делаю (надеюсь, администрация форума не сочтет это за офф-топ).

[maxal]

Ага, спасибо! Весь день сегодня поздравления принимаю

Из специалистов заинтересованность также высказал Рон Грэхем, со-автор известной книги Конкретная Математика.

[PAV]

Присоединяюсь к поздравлениям.

[maxal]

Кстати, немножко не в тему, но тоже красивый и трудный вычислительный результат, найденный буквально на днях (но я к нему не имею никакого отношения):

$$3113^8+2012^8+1953^8+861^8=2823^8+2767^8+2557^8+1128^8.$$

Особенно впечатляет тот факт, что для 7-х степеней подобного равенства (из 7 слагаемых) пока не найдено. За деталями отправляю к http://euler.free.fr/

[Руст]

Мне лично кажется это более интересная задача. Только я подозреваю, что для 8-ых степеней существует некоторое общее решение, т.е. $a_i=f_i(x),b_i=\phi_i(x),i=1,2,3,4, \ \ a_1^8+a_2^8+a_3^8+a_4^8=b_1^8+b_2^8+b_3^8+b_4^8$. При этом думаю, что число параметров в многочленах $f_i(x),\phi_i(x)$ не меньше 4.

[maxal]

Руст
И на чем базируется твое подозрение? Найти параметрическое решение будет куда сложнее числового.

Добавлено спустя 10 минут 18 секунд:

Параметрические решения вплоть до 6-й степени приведены тут: http://euler.free.fr/identities.htm

[Руст]

maxal писал(а):

Руст
И на чем базируется твое подозрение? Найти параметрическое решение будет куда сложнее числового.

Добавлено спустя 10 минут 18 секунд:

Параметрические решения вплоть до 6-й степени приведены тут: http://euler.free.fr/identities.htm

Дело в том, что умножение в кватернионах не коммутативно. Поэтому можно выбрать произведение 4 кватернионов так, чтобы произведение с разными способами умножения задали 4 -е степени некоторых выражений, при этом получились разные числа. Когда я начал получать конкретную параметрическую формулу, удовлетворяющую этому уравнению, меня вызвали на пиво, и я пока оставил это. Идея искать решение в виде произведения четырёх кватернионов, взятых в разном порядке.
Что касается твоей задачи, я кажется могу доказать, что при любом (a,b)=1, a>1 сравнекние $ n|a^n-b$ имеет бесконечно много решений. Соответственно смогу предложить более эффективные решеия для получения конкретных решений.

[maxal]

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

Что касается твоей задачи, я кажется могу доказать, что при любом (a,b)=1, a>1 сравнекние $ n|a^n-b$ имеет бесконечно много решений.

Я думаю, это серьезный результат, вполне заслуживающий отдельной статьи. Кстати, в своем письме Рон Грэхем упоминал подобное утверждение как гипотезу.

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

Соответственно смогу предложить более эффективные решеия для получения конкретных решений.

Чтобы не ходить далеко, можешь найти еще одно (пятое) решение $2^n \equiv 3\pmod{n}$ ?