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

[Ktina]

Мне почему-то упорно казалось, что эта задача уже была. Однако поиск по формулам ничего не дал. На всякий случай, публикую:

Решить в целых числах уравнение

$$5^n+3=2^m$$

[nnosipov]

Конкретно эта, возможно, и не была. Но подобные штуки мы обсуждали неоднократно. Вкратце: не решить такого вида уравнение очень трудно, поскольку всегда почему-то находится волшебный модуль (или ещё проще бывает, если повезёт). Если не полениться, можно даже программу написать, которая этот модуль предоставлять будет.

[Sonic86]

$m=0;1;2$ перебираем, далее $m\geqslant 3$
Берем по модулю $8$ - получаем $n=2k+1$. Подставляем.
Берем по модулю $3$ - получаем $m=2l$. Подставляем.
Берем по модулю $5$, получаем невозможное $3\equiv\pm 1\pmod 5$.

Наиболее веселый вариант этой задачи здесь есть в этом разделе за авторством СОКАКУ.
Еще:
topic44444.html
topic42767.html
и там по ссылкам. Там почти все есть, в т.ч. и на AOPS. Уря!

[nnosipov]

Sonic86, в этой задаче нужно немного поглубже покопать, поскольку есть решение $(m,n)=(7,3)$.

-- Пн авг 27, 2012 11:56:50 --

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

topic44444.html

Вот здесь мы это как раз и обсуждали (однако какой интересный номер у топика )

[nnosipov]

А вообще примерчик интересный. Этот волшебный модуль получается здесь очень нехилым. Возможно, я что-то просмотрел. В любом случае интересно было бы увидеть относительно короткое решение.

Ktina, Вы этот шедевр сами придумали или где-то нашли?

[Shadow]

По модулю 3 m и n одинаковой четности. С четными все понятно, для нечетных среди решений уравнения Пелля $2x^2-5y^2=3$ можно поискать степени двойки и пятерки.
$\\x_n=19x_{n-1}+30y_{n-1}\\ y_n=12x_{n-1}+19y_{n-1}$

Две начальные решения: $x_1=2,y_1=1;x_1=8,y_1=5$
В первом случае по модулю 12 годятся только решения с нечетными индексами.
$\\x_{2k+1}=2, y_{2k+1}=1 \pmod {12}\\ x_{2k}=8, y_{2k}=7 \pmod {12}$

Но $5^n \ne 7 \pmod {12}$
Но они не годятся по модулю 4: $x_{2k+1}=2 \pmod 4$
Аналогично второй случай: по модулю 56 годятся толко решения с индексами $8k+1$, которые не проходят по модулю 16.
Это все, конечно проверял на компютере.

[Sonic86]

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

Берем по модулю $3$ - получаем $m=2l$.

Тут ошибка: $m=2l+1$.

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

Этот волшебный модуль получается здесь очень нехилым.

Я вчера дошел до $125\cdot 5^{12s}+3=128\cdot 2^{12t}$ - модули брал - $2,3,5,7,13$.

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

Вкратце: не решить такого вида уравнение очень трудно, поскольку всегда почему-то находится волшебный модуль (или ещё проще бывает, если повезёт).

Вот где-то maxal явно писал, почему число решений конечно. А я не помню. Только если по ссылкам есть. По памяти боюсь какую-нибудь ерунду воспроизведу:
Если переменные две - $m,n$, то можно сделать подстановки $m=3m_1+r_m, n=3n_1+r_n, a^{m_1}=x, b^{n_1}=y$. Получим конечное число уравнений вида $Ax^3+By^3=C$. Эти уравнение по теореме Туэ-Зигеля-Рота имеют конечное число решений.
Но это - только для двух переменных.
Хотя это ничего не дает для понимания того, почему неразрешимо по модулю Уже столько этих уравнений было. Пора бы уже в общем виде алгоритм решения написать + теоремы.

[nnosipov]

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

Эти уравнение по теореме Туэ-Зигеля-Рота имеют конечное число решений.

Да, есть такое дело.

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

Хотя это ничего не дает для понимания того, почему неразрешимо по модулю Уже столько этих уравнений было. Пора бы уже в общем виде алгоритм решения написать + теоремы.

Очень хотелось, чтобы кто-нибудь это проделал. Думается, что это вполне тянет на публикацию в подходящем журнале (в зависимости от сложности получения результата).

Shadow, спасибо, что не поленились проверить, как здесь Пелль сработает. Меня вчера на это не хватило --- поиски волшебного модуля несколько затянулись Вот что получилось в сухом остатке.

Докажем, что равенство

$$ 5^3(5^a-1)=2^7(2^b-1) $$

невозможно в натуральных числах $a$ и $b$. Сначала запишем, что $a=32a_1$, $b=100b_1$ ($32$ --- порядок $5$ по модулю $2^7$, а $100$ --- порядок $2$ по модулю $5^3$). Теперь заметим, что $5^{32}-1$ делится на $2593$. Значит, $100b_1$ делится на $81$ --- порядок $2$ по модулю $2593$. Снова заметим, что $2^{81}-1$ делится на $262657$, а тогда $32a_1$ делится на порядок $5$ по модулю $262657$. А этот порядок (ура!) делится на $2^6$.

[Shadow]

Мда. Чтобы обобщить решения уравнения Пелля $x_n=38x_{n-1}-x_{n-2}$ по модулю 112 дают остатки
$2,68,6,48,26,44,78,8$, а степени двойки (больше 8), $16, 32,64$
Действительно, Ktina, откуда задача?

[Ktina]

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

Ktina, Вы этот шедевр сами придумали или где-то нашли?

Честно? Нашла: http://www.imocompendium.com/othercomp/Spa/SpaMO86.pdf (задача №3).

[nnosipov]

Ktina в сообщении #611761 писал(а):

Честно? Нашла: http://www.imocompendium.com/othercomp/Spa/SpaMO86.pdf (задача №3).

Тогда здесь мог подразумеваться только Пелль.

[Руст]

Годится проверка по модулю $p=641$.

[nnosipov]

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

Годится проверка по модулю $p=641$.

Что Вы имеете в виду? Равенство $5^3(5^a-1)=2^7(2^b-1) $ по модулю $641$ имеет место для многих пар $(a,b)$.

[Руст]

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

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

Годится проверка по модулю $p=641$.

Что Вы имеете в виду? Равенство $5^3(5^a-1)=2^7(2^b-1) $ по модулю $641$ имеет место для многих пар $(a,b)$.

Если $n>7$, то $n=35\mod 64$ для делимости на 256 числа $5^n+3$. Число $641|2^{32}+1$, $5=-2^7\mod 641$, значит $5^{35}=-125\mod 641\to 5^{35}+3=-122\mod 641$. Последнее не квадратичный вычет по модулю 641, в то время как 2 и его степени квадратичный вычет. Следовательно нет решений $n>7$.

[nnosipov]

А, квадратичные вычеты, ясно. Тоже интересно было бы понять, насколько это типично.