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"

(Created page with "== Problem == Show that for any positive integers <math>a</math> and <math>b</math>, <math>(36a + b)(36b + a)</math> cannot be a power of 2.")
 
(→‎Problem)
 
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Show that for any positive integers <math>a</math> and <math>b</math>, <math>(36a + b)(36b + a)</math> cannot be a power of 2.
+
Show that for any positive integers <math>a</math> and <math>b</math>, <math>(36a + b)(36b + a)</math> cannot be a power of <math>2</math>.
 +
 
 +
== Solution 1 ==
 +
 
 +
First, assume that <math>(36a + b)(36b + a)</math> is a power of <math>2</math>.
 +
Let <math>36a + b = 2^m = p</math> and <math>36b + a = 2^n = q</math>.
 +
Then <cmath>\frac{1}{36} < \frac{p}{q} = \frac{2^m}{2^n} = 2^{m-n} < 36</cmath>
 +
<cmath>-6 < m - n < 6</cmath>
 +
 
 +
Consider <math>4^m - 4^n = p^2 - q^2</math>. Factoring out <math>4^n</math> gives
 +
<cmath>4^n(4^{m-n}-1) = p^2 - q^2 = 1295(a^2 - b^2)</cmath>
 +
 
 +
Because <math>1295(a^2 - b^2)</math> contains odd factors and <math>1295</math> divides <math>37</math>, <math>4^{m-n}-1</math> must also divide <math>37</math>, so
 +
<math>4^{m-n} \equiv  1\mod 37</math>.
 +
 
 +
 
 +
Testing values shows that <math>m-n</math> divides 18. It can be easily shown that <math>m-n \neq 0</math>, so the least possible value of <math>m-n</math> is 18. But since <math>-6 < m - n < 6</math>, we reach a contradiction.
 +
 
 +
 
 +
== Solution 2 ==
 +
 
 +
Assume that <math>(36a + b)(36b + a)</math> is a power of <math>2</math>. Then <math>(m, n)</math> must also be a solution to <math>(36a + b)(36b + a) = 2^x</math> for some positive integer <math>x</math>. WLOG, assume <math>m < n</math> and let <math>m</math> be minimal. Then the least possible value of <math>(36m + n)(36n + m)</math> is <math>(37)(37) > (2^5)(2^5)</math>. For all positive integers <math>x > 1</math>, <math>2^x \equiv 0\mod 4</math>. So both <math>(36m + n)(36n + m)</math> must divide 4 as well. Then <math>(\frac{m}{2}, \frac{n}{2})</math> must also be a solution. But <math>m</math> is minimal and we find a smaller integer solution (because <math>m</math> divides 4), so we reach a contradiction.

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"