Азия-тынық мұхит математикалық олимпиадасы, 1998 жыл

Докажите, что для любых натуральных чисел $a$ и $b$, $(36a+b)(a+36b)$ не может быть степенью 2.

Комментарий/решение

$\textbf{Решение:} $ Предположим противное, то есть существует $k$ , такое что $(36а+b)(a+36b)=2^k$. Поскольку число $2^k $ можно представить в виде произведения двух целых чисел $2^l $ и $2^s $ (где $k=s+l $), то получаем систему:

$$ \begin{cases} 36a+b=2^l \\ a+36b=2^s\end{cases}$$

Решая систему получим

$$a=\frac{36\cdot 2^l-2^s}{35\cdot 37},\qquad b=\frac{36\cdot 2^s-2^l}{35\cdot 37}$$

Теперь докажем, что $a $ и $b $ не являются натуральными числами. Докажем это таким образом. Пусть для определенности считаем что,

$s\geq l $ . Тогда $a=\frac{2^l (36-2^{s-l})}{35\cdot 37}$. Из условий натуральности получим ограничение $s-l\leq 5$. Но в этом случаи числа $2^l (36-2^{s-l})$ и $37 \cdot 35$ являются взаимно простыми числами. Для случаи $s <l $ доказывается аналогично. Значит, наше предположение оказалось неверным.

Предположим обратное. Рассмотрим такую пару $a,b$ с наименьшей суммой. Предположим $a$ нечётное, тогда $a+36b$ - нечётное число, но таковое не может быть делителем степени 2. Поэтому $a=2a_1$, Аналогично $b=2b_1$. $(a+36b)(b+36a)=4(a_1+36b_1)(b_1+36a_1)$, т.е. $(a_1+36b_1)(b_1+36a_1)$ также является степенью 2. При этом $a_1+b_1<a+b$ - противоречие.

Допустим можно

Очевидно:

$36a+b=2^k$

$36b+a=2^l$

Б.О.О. $a \geq b$

$36a+b-(36b+a)=2^l(2^{k-l}-1)$

$a \ne b \rightarrow 2^l \mid a-b \rightarrow \varnothing \rightarrow a=b$

$(37a)^2 \ne 2^n$

Значит изначальное предположение не верно Ч.Т.Д.