APMO Power!

In this proof the set of positive integers will be called $\mathbb N$ . This proof uses a popular method called Proof by Infinite Descent .

Proof by contradiction: Say it is possible that $\displaystyle (a+36b)(b+36a)=2^{x}$ , where $a,b,x\in\mathbb N$ .

Notice that $a+36b=2^n$ and $b+36a=2^m$ , where $n,m\in\mathbb N$ .

Hence $a,b$ are even. Let $a=2a', b=2b'$ , where $a',b'\in\mathbb N$ .

$\displaystyle (2a'+36(2b'))(2b'+36(2a'))=4(a'+36b')(b'+36a')=2^{x}$

$\displaystyle\implies (a'+36b')(b'+36a')=2^{x-2}$

Notice that $\displaystyle (a'+36b')(b'+36a')\in\mathbb N$ . Hence $x-2=x'\in\mathbb N$ .

Therefore, we have $\displaystyle (a'+36b')(b'+36a')=2^{x'}$ , where $a',b',x'\in\mathbb N$ .

But look at the beginning of the proof... this is the same problem we started with! Except the variables now carry smaller values. But they can't decrease forever, because the positive integers have a minimum value, namely $1$ , which will be reached at some point.

Therefore, we have a contradiction - there are no such variables $a,b,x\in\mathbb N$ satisfying $(a+36b)(b+36a)=2^x$ . $\square$

$a + 36b$ and $b + 36a$ are powers of $2 \Rightarrow 37(a + b) = 2^m(2^n + 1)$ for some $m, n$

therefore $2^n \equiv -1 \pmod{37} \Rightarrow n \geq 18$ , however $37(a+b) < 2^{17}$

I used the idea that, if $2^{m} = a + 36b$ and $2^{n} = b + 36a$ , and $m >= n$ , then, $2^{n} (2^{m-n} - 1) = 35 (b - a)$ Hence, we can say, $m - n = 12d$ , because the order of 2 mod 35 is 12. Continuing, $(b - a) = \frac{2^{n} (2^{12d} - 1)}{35}$ As, $a, b <= 999$ , we can say, $d = 1$ Now, $b - a = 2^{n} 117$ And, $b + 36a = 2^{n}$ Using these two equations, we find, $37a = 2^{n}(-116)$ Which is a contradiction(a is an integer). Hence, no solution.

We can see that $a + 36b$ and $b + 36a$ must both be powers of two. Hence $a + 36b = 2^n$ and $b + 36a = 2^m$ .

Adding yields $37(a+b) = 2^n + 2^m \rightarrow a + b = \frac{2^n + 2^m}{37}$ . The numerator will always be even and the denominator will always be odd, so there will be no integer solutions to a and b.

I will skip some obvious steps, since this is a level 4 question.

• $a+36b=2^x$ --1
• $b+36a=2^y$ --2
• 1&2: $a=\dfrac{36\times2^y-2^x}{36^2-1}$ --3
• 1&2: $b=\dfrac{36\times2^x-2^y}{36^2-1}$ --4

We will look for $x$ and $y$ such that $a$ and $b$ are (positive) integers.

• 3: $(36^2-1)|(36\times2^y-2^x)$
• $1295|(36\times2^y-2^x)$

Prime factors of $1295$ are $5$ , $7$ , $37$ .

• $\implies 5|(36\times2^y-2^x)$ --5
• $\implies 7|(36\times2^y-2^x)$ --6
• $\implies 37|(36\times2^y-2^x)$ --7

Then:

• 5: $\implies 5|(2^y-2^x)$ --8
• 6: $\implies 7|(2^y-2^x)$ --9

• 7: $\implies 37|(2^y+2^x)$ --10

• Observe (powers of 2) mod 5: $1,2,4,3,1,\cdots$

• Observe (powers of 2) mod 7: $1,2,4,1,\cdots$
• Observe (powers of 2) mod 37:
• $1,2,4,8,16,32,27,17,34,31,25,13,26,15,30,23,9,18,-1,-2,-4,-8,-16,-32,-27,-17,-34,-31,-25,-13,-26,-15,-30,-23,-9,-18,\cdots$

Therefore:

• 8: $y-x=4p$ --11
• 9: $y-x=3q$ --12
• 10: $y-x=18+36r$ --13

Thus:

• 11&12&13: $y-x=12m=18+36r$
• $\implies 2m=3+6r$
• $\implies \mbox{even}=\mbox{odd}+\mbox{even}$
• $\implies$ no solution

Let $a+36b=2^k, b+36a=2^l$ . Then, $37(a+b)=2^l+2^k=2^k(2^{l-k}+1)$ w.l.o.g.

For this to hold, we need $37$ to divide $2^{l-k}+1$ . But we also need $2^l < 37\cdot999$ , so $0 \le l-k \le l \le 16$ . Computing the first few powers of $2^{l-k}+1$ modulo 37, we can see that none give remainder 0, so there can't be any solutions.

JavaScript for(var i =1;i<1000;i++){ for(var j =1;j<1000;j++){ var val = (i+36 j) (j+36*i); var temp = val.toString(2); if( temp % 2 == 0){ var count = temp.match(/1/g); if(count == 1) console.log(temp); } } }