5^n+3=2^m в целых числах (надеюсь, что не повторяюсь)

[Профессор Снэйп]

$5^n - 1 = 2^m - 4$
$(5 - 1)(5^{n-1} + 5^{n-2} + \ldots + 5 + 1) = 2^m - 4$
$5^{n-1} + \ldots + 5 + 1 = 2^{m-2} - 1$
$5(5^{n-2} + \ldots + 1) = 2(2^{m-3} - 1)$

Интересно, отсюда что-нибудь можно выжать?

[nnosipov]

Профессор Снэйп в сообщении #612132 писал(а):

Интересно, отсюда что-нибудь можно выжать?

Не знаю, надо пробовать. Вообще, вопрос о каноническом решении этой задачи (том, которое подразумевалось составителями этой испанской олимпиады), не такой уж простой. Сейчас мне уже кажется, что это решение, предложенное Рустом. Что-то не получается у меня убедиться в корректности решения Shadow: с одной серией понятно, а с другой --- нет.

[Shadow]

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

Что-то не получается у меня убедиться в корректности решения Shadow: с одной серией понятно, а с другой --- нет.

Вы имеете в виду ту, которая начинается с (8,5)
$\\8,5\\ 302,191\\ 11468,7253\\ 435482,275423\\ 16536848,10458821\\ ... $
Достаточно проверить только для иксов, там рекурентная формула $x_n=38x_{n-1}-x_{n-2}$
И остатки по модулю 112 соответно:
$8,78,44,26,48,6,68,2$
А у степеней двойки по модулю 112: $16,32,64$
Я в Excel проверял.Но такой способ решения на олимпиаде, естественно, не подразумевается.

-- 29.08.2012, 12:57 --

А в другой серии остатки те же, только в обратном порядке...

[nnosipov]

Shadow, всё в порядке, это я забыл на двойку поделить. Т.е. фактически решено уравнение $5y^2+3=2^n$.

[maxal]

Sonic86 в сообщении #611748 писал(а):

Пора бы уже в общем виде алгоритм решения написать + теоремы.

Алгоритм у меня есть реализованный в PARI/GP, а кое-какие теоремы написаны тут: http://projecteuclid.org/euclid.pjm/1102724775

[nnosipov]

maxal, а что Ваш алгоритм выдаёт в этом случае? Поменьше, чем в post611754.html#p611754?

[maxal]

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

maxal, а что Ваш алгоритм выдаёт в этом случае? Поменьше, чем в post611754.html#p611754?

В данном случае выдает 3355392. Но у него нет цели минимизировать модуль - возможно, существует и что-то меньшее.

[nnosipov]

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

В данном случае выдает 3355392

Так это даже лучше, поскольку простые делители здесь маленькие.

[Руст]

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

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

В данном случае выдает 3355392

Так это даже лучше, поскольку простые делители здесь маленькие.

Только вряд ли здесь можно решить с этим модулем в одну строчку (без компьютера). Я модуль $p=641$ взял как делитель числа Ферма $F_5$, когда все вычисляется удобно для уравнения содержащего $2^n$. Раньще я решал такие задачи сведением к Пелля (в том числе здесь). Решать через подходящий модуль несколько нестандартно (нахождение такого модуля), однако в нем больший потенциал. Такой метод позволяет решить уравнения $\sum_{i=1}^k a_i c_i^n=m$ при заданных $a_i,c_i\in Z$ при любом k, не только при $k=2$ как сведение к Пелля.

[nnosipov]

Руст в сообщении #616691 писал(а):

однако в нем больший потенциал

Видимо, да.