Числа вида 3, 30, 300, ... как разность степеней двойки

[Ktina]

Сколько чисел вида 3, 30, 300, ... представимы в виде разности двух степеней двойки с ЦНП (Целым Неотрицательным Показателем)?

Иными словами, решить в ЦНЧ (Целых Неотрицательных Числах) уравнение

$$3\cdot 10^k=2^m-2^n$$

(реально было на одной из городских олимпиад)

[slavav]

Только два - 3 и 30. Для них предъявляется решение. Для остальных доказывается, что решения нет.

[Ktina]

slavav
Хотелось бы Ваше доказательство сравнить, скажем, с моим.

[slavav]

Приводим уравнение к такому виду:
$5^k2^k3 = (2^{m - n} - 1)2^n$.
Из соображений чётности: $n = k$. Тогда:
$5^k3 = 2^{m - n} - 1$.
Пусть $k\ge2$, тогда $2^{m - n} - 1 = 0 \mod 25$.
Остатки $2^t - 1$ по модулю $25$: $1, 3, 7, 15, 6, 13, (1, 3, 7, 15, 6, 13)$
Нулевых нет. Значит $k<2$.

[Ktina]

slavav в сообщении #1087672 писал(а):

Остатки $2^t - 1$ по модулю $25$: $1, 3, 7, 15, 6, 13, (1, 3, 7, 15, 6, 13)$
Нулевых нет. Значит $k<2$.

$2^{20}$ разве не даёт остаток 1 при делении на 25?

[slavav]

Вы правы. Я обсчитался при вычислении остатков: ряд такой:
$1, 3, 7, 15, 6, 13, 2, 5, 11, 23, 22, 20, 16, 8, 17, 10, 21, 18, 12, 0, 1, ....$
То есть, $2^{20s} - 1 = 0 \mod 25$. Моё доказательство провалилось.

[Ktina]

slavav
Не страшно, не торопитесь, попробуйте ещё раз. У этой задачи есть неожиданно простое решение.

[slavav]

Я буду продолжать моё (сложное) решение:
Пусть $k\ge2$, тогда $5^k3 = 2^{20s} - 1$
Введём $A = 2^{10s}$, тогда $5^k3 = A^2 - 1 = (A - 1)(A + 1)$.
Тогда $5^{k_1}3 = A - 1$ и $5^{k_2} = A + 1$
или $5^{k_1} = A - 1$ и $5^{k_2}3 = A + 1$.

В обоих случаях надо решить уравнение $\left\lvert 5^{r_1} - 5^{r_2}3 \right\rvert = 2$. Из делимости на 5 видно что $r_1 = 0 \vee r_2 = 0$. Тогда решения только два: $\left\lvert 5 - 3 \right\rvert = 2$ и $\left\lvert 1 - 3 \right\rvert = 2$.

Вспомним, что $r_1 + r_2 = k_1 + k_2 = k$. Тогда $k < 2$. Доказано отсутствие решений для $k \ge 2$.

[Ktina]

slavav
Всё гораздо, граздо проще, хотя у меня идея с делимостью на 25 тоже используется.

[slavav]

Я вам верю. Но сам пока не придумал.

[Shadow]

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

хотя у меня идея с делимостью на 25 тоже используется.

А у меня только делимость на 3

[Ktina]

Shadow
?

[Shadow]

$2^c-1=3\cdot 5^k$ По модулю 3 $c$ - четное

$(2^r-1)(2^r+1)=3\cdot 5^k$

Влево - произведение взаимнопростых чисел, откуда

$\begin{cases} 2^r-1=3\\2^r+1=5^k \end{cases}$

или

$\begin{cases} 2^r+1=3\\2^r-1=5^k \end{cases}$

[Ktina]

Shadow
У Вас очень красиво!

У меня так:
Начиная с числа 300, все числа указанного вида делятся на 25.
Это означает, что если такое число представимо в виде разности двух степеней двойки, то разность показателей этих степеней должна быть кратна 20.
Но если разность показателей кратна 20, то сама разность между степенями должна быть кратна 11.
А числа вида 3, 30, 300, ... не кратны 11 ни разу.

С Новым Годом!