1998 APMO Problems/Problem 2

Problem

Show that for any positive integers $a$ and $b$, $(36a + b)(36b + a)$ cannot be a power of $2$.

Solution 1

First, assume that $(36a + b)(36b + a)$ is a power of $2$. Let $36a + b = 2^m = p$ and $36b + a = 2^n = q$. Then \[\frac{1}{36} < \frac{p}{q} = \frac{2^m}{2^n} = 2^{m-n} < 36\] \[-6 < m - n < 6\]

Consider $4^m - 4^n = p^2 - q^2$. Factoring out $4^n$ gives \[4^n(4^{m-n}-1) = p^2 - q^2 = 1295(a^2 - b^2)\]

Because $1295(a^2 - b^2)$ contains odd factors and $1295$ divides $37$, $4^{m-n}-1$ must also divide $37$, so $4^{m-n} \equiv  1\mod 37$.


Testing values shows that $m-n$ divides 18. It can be easily shown that $m-n \neq 0$, so the least possible value of $m-n$ is 18. But since $-6 < m - n < 6$, we reach a contradiction.


Solution 2

Assume that $(36a + b)(36b + a)$ is a power of $2$. Then $(m, n)$ must also be a solution to $(36a + b)(36b + a) = 2^x$ for some positive integer $x$. WLOG, assume $m < n$ and let $m$ be minimal. Then the least possible value of $(36m + n)(36n + m)$ is $(37)(37) > (2^5)(2^5)$. For all positive integers $x > 1$, $2^x \equiv 0\mod 4$. So both $(36m + n)(36n + m)$ must divide 4 as well. Then $(\frac{m}{2}, \frac{n}{2})$ must also be a solution. But $m$ is minimal and we find a smaller integer solution (because $m$ divides 4), so we reach a contradiction.