Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1998 APMO Problems/Problem 2"

(→‎Problem)
(→‎Problem)
 
(No difference)

Latest revision as of 12:50, 22 July 2021

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_APMO_Problems/Problem_2&oldid=158892"