Maths Olympiad Prep

Library / /2 of 3

Number theory Difficulty 5.9 AIME, harder Prove it North Macedonia

Find all positive integers xx, yy, zz and tt such that
2x3y+5z=7t. 2^x \cdot 3^y + 5^z = 7^t.

Solution

Reducing modulo 33 we get 5z15^z \equiv 1, therefore zz is even, z=2cz = 2c, cNc \in \mathbb{N}.
Next we prove that tt is even.
Obviously, t2t \ge 2. Let us suppose that tt is odd, say t=2d+1t = 2d+1, dNd \in \mathbb{N}. The equation becomes 2x3y+25c=749d2^x \cdot 3^y + 25^c = 7 \cdot 49^d. If x2x \ge 2, reducing modulo 44 we get 131 \equiv 3, a contradiction. And if x=1x=1, we have 23y+25c=749d2 \cdot 3^y + 25^c = 7 \cdot 49^d and reducing modulo 2424 we obtain
23y+17242(3y3), i.e. 43y11 2 \cdot 3^y + 1 \equiv 7 \Rightarrow 24 \mid 2(3^y - 3), \text{ i.e. } 4 \mid 3^{y-1} - 1
which means that y1y-1 is even. Then y=2b+1y = 2b+1, bNb \in \mathbb{N}. We obtain 69b+25c=749d6 \cdot 9^b + 25^c = 7 \cdot 49^d, and reducing modulo 55 we get (1)b=2(1)d(-1)^b = 2(-1)^d which is false for all b,dNb, d \in \mathbb{N}. Hence tt is even, t=2d,dNt=2d, d \in \mathbb{N}, as claimed.

Now the equation can be written as
2x3y+25d=49d2x3y=(7d5c)(7d+5c). 2^x \cdot 3^y + 25^d = 49^d \Leftrightarrow 2^x \cdot 3^y = (7^d - 5^c)(7^d + 5^c).
As gcd(7d5c,7d+5c)=2\gcd(7^d - 5^c, 7^d + 5^c) = 2 and 7d+5c>27^d + 5^c > 2, there exist exactly three possibilities:
(1){7d5d=2x17d+5d=23y (1) \begin{cases} 7^d - 5^d = 2^{x-1} \\ 7^d + 5^d = 2 \cdot 3^y \end{cases}
(2){7d5d=23y7d+5d=2x1 (2) \begin{cases} 7^d - 5^d = 2 \cdot 3^y \\ 7^d + 5^d = 2^{x-1} \end{cases}
(3){7d5d=27d+5d=2x13y. (3) \begin{cases} 7^d - 5^d = 2 \\ 7^d + 5^d = 2^{x-1} \cdot 3^y \end{cases}.

### Case 1.
We have 7d=2x2+3y7^d = 2^{x-2} + 3^y and reducing modulo 33, we get 2x21(mod3)2^{x-2} \equiv 1 \pmod{3}, hence x2x-2 is even, i.e. x=2a+2x=2a+2, aNa \in \mathbb{N}, where a>0a>0, since a=0a=0 would mean 3y+1=7d3^y+1=7^d which is impossible (even=odd).
We obtain
7d5d24a(mod4)7d1(mod4)d=2e,eN. 7^d - 5^d \equiv 2 \cdot 4^a \pmod{4} \Rightarrow 7^d \equiv 1 \pmod{4} \Rightarrow d=2e, e \in \mathbb{N}.
Then we have
49c5d24a(mod8)5c1(mod8)c=2f,fN. 49^c - 5^d \equiv 2 \cdot 4^a \pmod{8} \Rightarrow 5^c \equiv 1 \pmod{8} \Rightarrow c=2f, f \in \mathbb{N}.
We obtain 49c25f=24a02(mod3)49^c - 25^f = 2 \cdot 4^a \Rightarrow 0 \equiv 2 \pmod 3, false. In conclusion, in this case there are no solutions to the equation.

### Case 2.
From 2x1=7d+5c122^{x-1} = 7^d + 5^c \ge 12 we obtain x5x \ge 5. Then 7d+5c0(mod4)7^d + 5^c \equiv 0 \pmod 4, i.e. 3d+10(mod4)3^d + 1 \equiv 0 \pmod 4, hence dd is odd. As 7d=5c+23y117^d = 5^c + 2 \cdot 3^y \ge 11, we get d2d \ge 2, hence d=2e+1d=2e+1, eNe \in \mathbb{N}.
As in the previous case, from 7d=22+3y7^d = 2^2 + 3^y reducing modulo 33 we obtain x=2a+2x=2a+2 (because x5x \ge 5). We get 7d=4a+3y7^d = 4^a + 3^y i.e. 749c=4a+3y7 \cdot 49^c = 4^a + 3^y, hence, reducing modulo 88 we obtain 73y7 \equiv 3^y which is false, because 3y3^y is congruent either to 11 (if yy is even) or to 33 (if yy is odd). In conclusion, in this case there are no solutions to the equation.

### Case 3.
From 7d=5c+27^d = 5^c + 2 it follows that the last digit of 7d7^d is 77, hence d=4k+1d=4k+1, kNk \in \mathbb{N}.
If c2c \ge 2, from 74k+1=5c+27^{4k+1} = 5^c + 2 reducing modulo 2525 we obtain 72(mod2)7 \equiv 2 \pmod 2 which is false.
For c=1c=1 we get d=1d=1 and the solution x=3,y=1,z=t=2x=3, y=1, z=t=2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.