BMO 2024 | Problem 3 | Solution - 30 April 2024

Problem 3.
Let a and b be distinct positive integers such that 3^a+2 is divisible by 3^b+2. Prove that a>b² .

Solution 1

Obviously $a>b$
Let $a=bx+y$ where $0\le y\le b-1$
Claim: $x\ge b$
Suppose by contradiction that $x\le b-1$
Then $3^b+2\mid (3^b)^x\cdot 3^y+2$ so $3^b+2\mid (-2)^x\cdot 3^y+2$ so $3^b+2\mid (-2)^x\cdot 3^y-3^b$ .Since $b>y$ and $(3,3^b+2)=1$ we have $3^b+2\mid (-2)^x-3^{b-y}$ .Divide into cases:(and also note $(-2)^x\neq 3^{b-y}$ )
Case 1: $x$ even
In this case we have $3^b+2\mid 2^x-3^{b-y}$ .
If $2^x>3^{b-y}$ then $3^b>2^b>2^{b-1}\ge 2^x\ge 3^{b-y}+3^b+2>3^b$ contradiction.
If $3^{b-y}>2^x$ then $3^b\ge 3^{b-y}\ge 2^x+3^b+2>3^b$ another contradiction
Case 2: $x$ odd then $2^x+3^{b-y}\ge 3^b+2$ .If $y>0$ then $2^{b-1}+3^{b-1}\ge 2^x+3^{b-y}\ge 3^b+2$ so $2^{b-1}>2\cdot 3^{b-1}>3^{b-1}\ge 2^{b-1}$ contradiction. Thus we must have $y=0$ i.e $3^b+2\mid 2^x+3^b$ or $3^b+2\mid 2^x-2$ .If $x=1$ we have $a=b$ ; is $x>1$ then $3^b<3^b+2\le 2^x-2<2^x<2^b<3^b$ false $\blacksquare$
By the claim we have $a\ge b^2$ so we must have $a=b^2$ meaning $3^b+2\mid (-2)^b-3^b$ or $3^b+2\mid (-2)^b+2$ which by the same boundings as above it fails. We are done !

Solution 2

Let's suppose, FTSOC, that $a\leq b^{2}$ . Let $a=mb+k$ , where $k$ is the remainder when $a$ is divided by $b$ . Suppose that $m \leq b$ .
We have $3^{b}+2|3^{mb+k}+2$ , and also $3^{b}+2|3^{mb+k}+2.3^{(m-1)b+k}$ . Subtracting these two, we get $3^{b}+2|3^{(m-1)b+k}-1$ (we can divide it by $2$ , because $3^{b}+2$ is odd. We can continue this process and we get:
$3^{b}+2|2.3^{(m-2)b+k}+1$
$3^{b}+2|4.3^{(m-3)b+k}-1$
$3^{b}+2|8.3^{(m-4)b+k}+1$
Well, observing this we can guess that $3^{b}+2|2^{l-1}.3^{(m-l)b+k}+(-1)^{l}$ for $l=1, 2, ..., m$ . This easily follows by induction.
Click to reveal hidden text

We have the base cases, so now let's suppose that for some $l$ we have $3^{b}+2|2^{l-1}.3^{(m-l)b+k}+(-1)^{l}$ ( $1$ )
We will prove this for $l+1$ . We have $3^{b}+2|3^{b}+2$ . Multiplying this by $2^{l-1}.3^{(m-l-1)b+k}$ , we get:
$3^{b}+2|2^{l-1}.3^{(m-l)b+k}+2^{l}.3^{(m-l-1)b+k}$ ( $2$ ). From ( $1$ ) and ( $2$ ), we have $3^{b}+2|2^{l}.3^{(m-l-1)b+k}+(-1)^{l+1}$ , as desired. $\square$

Now, when we proved this, take $l=m$ .
We have $3^{b}+2|2^{m-1}.3^{k}+(-1)^{m}$
Since $a$ and $b$ are distinct, at least one of the following two is not true: $m=1$ and $k=0$ , hence $2^{m-1}.3^{k}+(-1)^{m}$ cannot be $0$ . Also, $m$ cannot be $0$ , because obviously $a>b$ . We have 2 cases now:
Case 1: $m$ is even.
Then we have $3^{b}+2|2^{m-1}.3^{k}+1$ Clearly, $b\geq k$ , so we can multiply this by $3^{b-k}$ and we get $3^{b+2}|2^{m-1}.3^{b}+3^{b-k}$ . We also have $3^{b}+2|2^{m-1}.3^{b}+2^{m}$ . Subtracting these two, we get $3^{b}+2|3^{b-k}-2^{m}$ . This is clearly not $0$ , so we have two cases:
Case 1.1: $3^{b-k}-2^{m}>0$ . But obviously $3^b+2>3^{b-k}-2^{m}$ , which is a contradiction.
Case 1.2: $3^{b-k}-2^{m}<0$ . We have $2^{m}-3^{b-k} \leq 2^{b}-3^{b-k}<3^{b}-3^{b-k}<3^{b}+2$ , contradiction!
Case 2: $m$ is odd.
Then we have $3^{b}+2|2^{m-1}.3^{k}-1$ . Similarly to Case 1, we get $3^b+2|3^{b-k}+2^{m}$ . Well, this is obviously positive.
If $k=0$ , we get $3^{b}+2|2^{m-1}-1$ . $3^{b}+2>2^{m-1}-1$ , so the only option is $2^{m-1}=1$ , which implies $m=1$ and $a=b$ .
So $k \geq 1$ . We will prove that $3^{b}+2>3^{b-k}+2^{m} \iff 3^{b}-3^{b-k}>2^{m}-2$ , which will be a contradiction.
LHS $\geq 3^{b}-3^{b-1}=2.3^{b-1}>2.(2^{b-1}-1)\geq 2.(2^{m-1}-1)=$ RHS.
Hence we have contradiction with the assumption that $m\leq b$ . Hence, $m>b$ , and then $a>b^{2}$ , as desired. $\blacksquare$