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.

Page

Toolbox

Search

1998 APMO Problems/Problem 2

Problem

Solution 1

Solution 2