2015 IMO Problems/Problem 2

Problem

Determine all triples of positive integers $(a,b,c)$ such that each of the numbers $ab-c,\; bc-a,\; ca-b$ is a power of 2.

(A power of 2 is an integer of the form $2^n$ where $n$ is a non-negative integer ).

Solution

The solutions for $(a,b,c)$ are $(2,2,2)$ , $(2,2,3)$ , $(2,6,11)$ , $(3,5,7)$ , and permutations of these triples.

Assume $a \leq b \leq c$ , so that $ab-c = 2^m$ , $ca-b = 2^n$ , $bc-a=2^p$ , with $m \leq n \leq p$ . We have $a>1$ since otherwise $c-b$ and $b-c$ should both be positive, which is impossible. We exhaust the various cases as follows:

Case 1: $a=b$ .

Hence $n=p$ , $a^2=2^m+c$ and $a(c-1)=2^n$ . From the second equation, $a=2^r$ and $c=2^{n-r}+1$ , where $r>0$ . From the first, $2^{2r}=2^{m}+2^{n-r}+1$ . Thus either $n=r$ or $m=0$ (otherwise the LHS is even and RHS is odd). Hence either $2^{2n}=2^{m}+2$ or $2^{2r}=2^{n-r}+2;$ $(m,n,r)$ equals $(1,1,1)$ or $(0,2,1).$ This gives $(a,b,c) = (2,2,2)$ or $(2,2,3)$ .

Case 2: $2=a<b \leq c$ (so $m\leq n<p$ ).

Hence $2b-c=2^m$ , $2c-b=2^n$ , $bc-2=2^p$ . From the second equation, $2^n \geq c>2$ , so $2^n$ is even. Hence $b$ is even. Further, $2^p\geq 2^{n+1}>4.$ From the third equation, $bc=2^p+2$ is not divisible by 4, so $c$ is odd and $b=2b_0$ where $b_0$ is odd. From the first equation, $2^m$ is odd and must equal 1. Hence $4b_0-c=1$ , $c-b_0=2^{n-1}$ , $b_0c=2^{p-1}+1$ . Hence $b_0(b_0+2^{n-1})=2^{p-1}+1$ . From the first two equations, $3b_0=1+2^{n-1}$ . Hence $n \geq 4$ (note that $n=2$ would imply $b_0=1$ which contradicts $b>a$ ). Substituting for $b_0$ , we get $(1+2^{n-1})(1+2^{n+1})=9(2^{p-1}+1)$ . Modulo $2^{n-1}$ , the LHS $\equiv 1$ and the RHS $\equiv 9$ (note $p>n$ ). Hence $9\equiv 1 \mod 2^{n-1}$ , so $n=4$ , $p=6$ , $b=6$ , and $c=11$ . We conclude that $(a,b,c)=(2,6,11)$ is the only solution.

Case 3: $3\leq a<b \leq c$ .

The following simple lemma is used in the proof below: If $i$ and $j$ are odd integers, then exactly one of the two (even) integers $i+j$ and $i-j$ is divisible by $4$ .

For, if $i+j\equiv k \mod 4$ and $i-j\equiv k \mod 4$ , we would have $k=0$ or $k=2$ (since $i+j$ and $i-j$ are even). But then $2i \equiv 0 \mod 4$ which contradicts the hypothesis that $i$ is odd.

From $ac-b=2^n$ , we get $2^n\geq 2c > 6$ , so $n\geq 3$ and $2^n$ is even. Write the last two equations as $(c-1)(b+a) = 2^p+2^n,$ $(c+1)(b-a) = 2^p-2^n.$ If $c$ is even, $2^n$ should divide $b-a<b\leq c \leq 2^{n-1}$ , which is impossible. Hence $c$ is odd, and one of $c+1$ and $c-1$ is not divisible by 4 (from the lemma above). Hence one of $b+a$ and $b-a$ is an odd multiple of $2^{n-1};$ since $b-a < 2^{n-1}$ , this must be $b+a$ . But $b+a<2b \leq 2.2^{n-1}$ , so in fact $b+a=2^{n-1}$ . Hence $c-1=2^{p-n+1}+2$ , and $(2^{p-n+1}+4)(2^{n-1}-2a)=2^p-2^n$ .

If $a$ and $b$ were even, we would have $m=1$ and $c+1=2^{p-n+1}+4=ab \geq 3(4)=12$ . Hence $2^{p-n+1} \geq 8$ and $ab=2^{p-n+1}+4$ is not divisible by $8$ . Hence $a=2a_0$ where $a_0$ is odd, and $(2^{p-n-1}+1)(2^{n-3}-a_0)=2^{p-4}-2^{n-4}$ . The LHS is odd and so must be the RHS, i.e., $n=4$ . We get $(2^{p-5}+1)(2-a_0)=2^{p-4}-1$ . For the LHS to be positive, we need $a_0=1,$ i.e., $a=2$ which is contrary to the hypothesis that $a\geq 3$ .

Thus $a$ and $b$ are odd. We have $(2^{p-n-1}+1)(2^{n-2}-a)=2^{p-3}-2^{n-3}$ . If $2^{p-n-1}$ were even, the LHS would be odd, so $n=3$ and $a<2^{n-2}=2.$ This is impossible. Hence $p-n-1=0$ , and $c=2^{p-n+1}+3=7$ . Also $(2^{n-2}-a)=2^{p-4}-2^{n-4}$ , so $n=4$ , $p=5$ , $a=3$ , $b=ac-2^{n}=5$ . Hence the only solution in this case is $(a,b,c)=(3,5,7)$ .

2015 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search

2015 IMO Problems/Problem 2

Problem

Solution

See Also