2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение15.09.2022, 15:53 
Аватара пользователя


05/06/08
470
Доказал некое утвердение и хотелось бы знать:
а) верно ли это доказательство (я никаких ошибок не вижу, тем не менее);
б) есть ли более элегантное и короткое.

Доказать утверждение:
Уравнение $\left| {{2^b} - {3^t}} \right| = 1$ верно только для трех пар $\left\{ {b,t} \right\}$ равных $\left\{ {\left\{ {1,1} \right\},\left\{ {2,1} \right\},\left\{ {3,2} \right\}} \right\}$.

Доказательство:
$$\left| {{2^b} - {3^t}} \right| = 1 \Rightarrow \left\{ \begin{array}{l}
{3^t} + 1 = {2^b}\\
{3^t} - 1 = {2^b}
\end{array} \right.$  $

Не нарушая общности доказательства, положим, что $t \ge 4$ (для $t<4$ доказательство очевидно и выполняется простой проверкой, включая и первое условие).

Если t нечетное $t = 2n + 1\left| {n \ge 1} \right.$, то:

(1) $ t \ge 3 \rightarrow {3^t} \pm 1 = \left( {3 \pm 1} \right)\left( {{3^{t - 1}} \pm {3^{t - 2}}... \pm 1} \right) = \left( {2or4} \right)\left( {2k + 1} \right) \ne {2^b} $

Для четных t необходимо доказать для каждого случая ${3^t} + 1 \ne {2^b}$ и ${3^t} - 1 \ne {2^b}$

Для этого произведем некоторые алгебраические преобразования:

$\begin{array}{l}
{3^{2\tau }} + 1 + 2 - 2 = 3\left( {{3^{2\tau  - 1}} + 1} \right) - 2 = \\
3\left( {{2^2}\left( {2k + 1} \right)} \right) - 2 = 2\left( {2 \cdot 3\left( {2k + 1} \right) - 1} \right) = \\
2\left( {2m - 1} \right) \ne {2^b}
\end{array}$


Для ${3^t} - 1 \ne {2^b}$ предложенная выше схема в общем виде не работает:

${3^{2\tau }} - 1 + 4 - 4 = 3\left( {{3^{2\tau  - 1}} + 1} \right) - 4 = 3\left( {4\left( {2k + 1} \right)} \right) - 4 = 4\left( {3\left( {2k + 1} \right) - 1} \right) $

Однако для этого случая есть даже более простое доказательство.
Действительно, если $t \ge 4$ то ${3^{2\tau }} - 1 = \left( {{3^\tau } - 1} \right)\left( {{3^\tau } + 1} \right) $ где $\tau  \ge 2$. Учитывая, что уже доказано (1)-(2) для любых $\tau  \ge 2$ ${3^\tau } + 1 \ne {2^b}$ имеем:

${3^{2\tau }} - 1 = \left( {{3^\tau } - 1} \right)\left( {{3^\tau } + 1} \right) \ne {2^b}$

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение15.09.2022, 16:57 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
MGM в сообщении #1564716 писал(а):
$$\left| {{2^b} - {3^t}} \right| = 1 \Rightarrow \left\{ \begin{array}{l}
{3^t} + 1 = {2^b}\\
{3^t} - 1 = {2^b}
\end{array} \right.$$
Скобка не та. Да и стрелка тоже.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение15.09.2022, 18:00 
Заслуженный участник


20/12/10
8858
MGM в сообщении #1564716 писал(а):
б) есть ли более элегантное и короткое
Сначала дайте определение элегантности :)

Тем не менее, вот другое решение: если $m \geqslant 3$, то сравнение $2^m-3^n \equiv 1 \pmod{8}$ невозможно, а при $m \geqslant 4$ невозможно сравнение $3^n-2^m \equiv 1 \pmod{80}$. Таким образом, остается проверить значения $m \in \{1,2,3\}$.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение15.09.2022, 23:36 
Аватара пользователя


05/06/08
470
nnosipov в сообщении #1564726 писал(а):
MGM в сообщении #1564716 писал(а):
б) есть ли более элегантмоего ное и короткое
Сначала дайте определение элегантности :)

Тем не менее, вот другое решение: если $m \geqslant 3$, то сравнение $2^m-3^n \equiv 1 \pmod{8}$ невозможно, а при $m \geqslant 4$ невозможно сравнение $3^n-2^m \equiv 1 \pmod{80}$. Таким образом, остается проверить значения $m \in \{1,2,3\}$.

Спасибо. Первая часть доказательства действительно элегантна. А главное, утверждение если $m \geqslant 3$, то сравнение $2^m-3^n \equiv 1 \pmod{8}$ невозможно - утверждение очевидное даже мне, не шибко знакомому с модулярной арифметикой.
Однако, в силу слабого знакомства с методами модулярной алгебры, мне сложно понять с лету часть вторую.
Так как считать в лоб модуль 80ти от двух слагаемых не делящихся нацело на 80 у меня не получается.
Хотя допускаю, что и $3^n-2^m \equiv 1 \pmod{80}$ очевидно для спецов, а значит и все доказательство элегантно.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение16.09.2022, 00:46 
Заслуженный участник
Аватара пользователя


16/07/14
8346
Цюрих
Какие остатки бывают у $3^n$ по модулю $80$? А т.к. $2^m$ и $80$ делятся на $16$, то и $2^m$ по модулю $80$ делится на $16$; но т.к. $2$ не делится на $5$, а $80$ делится, то $2^m$ по модулю $80$ не будет нулем.

Я бы правда второй случай рассмотрел аналогично тому что у вас: если $3^n - 2^m \equiv 1 \pmod 8$, то $n$ четное, а тогде $2^m = (3^t - 1)(3^t + 1)$, но тогда оба сомножителя справа - степени двойки, причем отличающиеся на $2$, а таких кроме как $2$ и $4$ не бывает.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение16.09.2022, 03:57 
Заслуженный участник


20/12/10
8858
MGM в сообщении #1564751 писал(а):
Хотя допускаю, что и $3^n-2^m \equiv 1 \pmod{80}$ очевидно для спецов
Нет, это не очевидно, но легко проверяется в уме: $3^n \bmod{80} \in \{1,3,9,27\}$ (очевидно, так как $3^4=81 \equiv 1 \pmod{80}$), $2^m \bmod{80} \in \{16,32,48,64\}$ (нужно чуть-чуть посчитать) и видно, что всевозможные разности не дают единицу по модулю $80$.

Вообще, это хорошо известная задача, она есть в книжке В. Серпинского "250 задач по элементарной теории чисел" (см. задачи 154 и 155).

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение16.09.2022, 10:24 
Аватара пользователя


05/06/08
470
nnosipov в сообщении #1564765 писал(а):
Вообще, это хорошо известная задача, она есть в книжке В. Серпинского "250 задач по элементарной теории чисел" (см. задачи 154 и 155).

Спасибо за ссылку. К своему стыду книгу не читал.

-- Пт сен 16, 2022 11:43:42 --

mihaild в сообщении #1564757 писал(а):
Какие остатки бывают у $3^n$ по модулю $80$? А т.к. $2^m$ и $80$ делятся на $16$, то и $2^m$ по модулю $80$ делится на $16$; но т.к. $2$ не делится на $5$, а $80$ делится, то $2^m$ по модулю $80$ не будет нулем.

Я бы правда второй случай рассмотрел аналогично тому что у вас: если $3^n - 2^m \equiv 1 \pmod 8$, то $n$ четное, а тогде $2^m = (3^t - 1)(3^t + 1)$, но тогда оба сомножителя справа - степени двойки, причем отличающиеся на $2$, а таких кроме как $2$ и $4$ не бывает.

Посмотрел доказательсво из книжки для второго случая. Не могу сказать что оно проще моего. Разве что для четной степени я лоханулся и не заметил, что в скобках два поледовательных четных.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение17.09.2022, 08:10 
Заблокирован


16/04/18

1129
Похоже на известную задачу, которая недавно была решена, что только 9-8=1.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение17.09.2022, 09:36 
Заслуженный участник


20/12/10
8858
Эта задача, известная как Catalan's conjecture, гораздо сложнее. А здесь мы имеем дело с простым частным случаем.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение18.09.2022, 09:52 


23/02/12
3109
MGM в сообщении #1564716 писал(а):
б) есть ли более элегантное и короткое.
Расстояние 1 между $3^2$ и $2^3$ очевидно. Меньшего - 0 быть не может, так в уравнение $3^x=2^y$ не имеет натуральных решений (слева стоит нечетное, а справа четное число).

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение18.09.2022, 10:17 
Заслуженный участник


20/12/10
8858
vicvolf
Вы, как всегда, о чем-то своем. У ТС речь идет о том, чтобы найти ВСЕ ситуации, когда степень двойки от степени тройки отстоит на расстояние 1.

 Профиль  
                  
 
 Re: Кратчайшее расстояние 1 между степенью двойки и тройки
Сообщение18.09.2022, 18:07 


23/02/12
3109
nnosipov в сообщении #1564891 писал(а):
когда степень двойки от степени тройки отстоит на расстояние 1.
Я дополнительно показал, что данное расстояние кратчайшее, как в названии темы.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group