Maths Olympiad Prep

Library / /11 of 61

Number theory Difficulty 5.6 AIME, harder Prove it Belarus

Find all triples (x,y,z)(x, y, z) of nonnegative integers xx, yy, zz such that 7x=3z2y7^x = 3^z - 2^y.

Solutions — 2

Solution 1

{(x,y,z)}={(0,1,1),(1,1,2),(0,3,2),(2,5,4)}\{(x, y, z)\} = \{(0, 1, 1), (1, 1, 2), (0, 3, 2), (2, 5, 4)\}.
We rewrite the equation in the form 7x+2y=3z7^x + 2^y = 3^z. Note that for y=0y = 0 the left-hand side of the equation is an even integer while the right-hand side is an odd integer. So, y>0y > 0.
Consider three cases: y=1y = 1, y=2y = 2 and y3y \ge 3.
1) y=1y = 1. In this case we have
7x+2=3z.(1) 7^x + 2 = 3^z. \quad (1)
If x=0x = 0, then z=1z = 1; if x=1x = 1, then z=2z = 2. Thus, it remains to consider the case x>2x > 2, z>2z > 2. In this case (7x+2)33(7^x + 2) \ge 3^3. Consider the residues of 7n7^n modulo 27:
758213101141. 7 \rightarrow -5 \rightarrow -8 \rightarrow -2 \rightarrow 13 \rightarrow 10 \rightarrow -11 \rightarrow 4 \rightarrow 1.
It follows that x4(mod9)x \equiv 4 \pmod 9. Note that 76+73+1=117993=33710637^6 + 7^3 + 1 = 117993 = 3 \cdot 37 \cdot 1063, so (791)(76+73+1)37(7^9 - 1) \equiv (7^6 + 7^3 + 1) \equiv 37. Thus, 791(mod37)7^9 \equiv 1 \pmod{37} and then
7x7449212214433(mod37). 7^x \equiv 7^4 \equiv 49^2 \equiv 12^2 \equiv 144 \equiv 33 \pmod{37}.
Hence 7x+235(mod37)7^x + 2 \equiv 35 \pmod{37}.
On the other hand, considering the residues of 3n3^n modulo 37, we have
3927721264123634281030161133251. 3 \rightarrow 9 \rightarrow 27 \rightarrow 7 \rightarrow 21 \rightarrow 26 \rightarrow 4 \rightarrow 12 \rightarrow 36 \rightarrow 34 \rightarrow 28 \rightarrow 10 \rightarrow 30 \rightarrow 16 \rightarrow 11 \rightarrow 33 \rightarrow 25 \rightarrow 1.
We see that 3z≢35(mod35)3^z \not\equiv 35 \pmod{35} for all zz. Therefore, there are no solutions of (1) for x>2x > 2, z>2z > 2.
2) y=2y = 2. We have 3z=7x+42(mod3)3^z = 7^x + 4 \equiv 2 \pmod 3, a contradiction.
3) y3y \ge 3. Then 7x3z(mod8)7^x \equiv 3^z \pmod 8, whence x2(mod2)x \equiv 2 \pmod 2 and z2(mod2)z \equiv 2 \pmod 2. Let x=2x1x = 2x_1, z=2z1z = 2z_1. Now the initial equation can be rewritten in the form
(3z17x1)(3z1+7x1)=2y. (3^{z_1} - 7^{x_1})(3^{z_1} + 7^{x_1}) = 2^y.
So, it follows that
3z17x1=2a,(2) 3^{z_1} - 7^{x_1} = 2^a, \quad (2)
3z1+7x1=2b,(3) 3^{z_1} + 7^{x_1} = 2^b, \quad (3)
and, since (3z17x1)2(3^{z_1} - 7^{x_1}) \equiv 2, we have b>a1b > a \ge 1. Summing (2) and (3), we obtain 2a+2b=23z12^a + 2^b = 2 \cdot 3^{z_1}. Hence a=1a = 1. Then (2) can be rewritten as 3z17x1=23^{z_1} - 7^{x_1} = 2, or 3z1=7x1+23^{z_1} = 7^{x_1} + 2, which coincides with (1). Therefore, we have {(x1,z1)}={(0,1),(1,2)}\{(x_1, z_1)\} = \{(0, 1), (1, 2)\}, and bb is equal to 2 and 4 respectively.
Finally, in this case we have {(x,y,z)}={(0,3,2),(2,5,4)}\{(x, y, z)\} = \{(0, 3, 2), (2, 5, 4)\}.

Solution 2

Answer: {(x,y,z)}={(0,1,1),(1,1,2),(0,3,2),(2,5,4)}\{(x, y, z)\} = \{(0, 1, 1), (1, 1, 2), (0, 3, 2), (2, 5, 4)\}.

We rewrite the equation in the form 7x+2y=3z7^x + 2^y = 3^z. Note that for y=0y = 0 the left-hand side of the equation is an even integer while the right-hand side is an odd integer. So, y>0y > 0.

Consider three cases: y=1y = 1, y=2y = 2 and y3y \ge 3.

1)
y=1y = 1. In this case we have
7x+2=3z.(1) 7^x + 2 = 3^z. \tag{1}
If x=0x = 0, then z=1z = 1; if x=1x = 1, then z=2z = 2. Thus, it remains to consider the case x>2x > 2, z>2z > 2. In this case (7x+2)÷33(7^x + 2) \div 3^3. Consider the residues of 7n7^n modulo 2727:
758213101141. 7 \rightarrow -5 \rightarrow -8 \rightarrow -2 \rightarrow 13 \rightarrow 10 \rightarrow -11 \rightarrow 4 \rightarrow 1.
It follows that x4(mod9)x \equiv 4 \pmod{9}. Note that 76+73+1=117993=33710637^6 + 7^3 + 1 = 117993 = 3 \cdot 37 \cdot 1063, so (791)÷(76+73+1)÷37(7^9 - 1) \div (7^6 + 7^3 + 1) \div 37. Thus, 791(mod37)7^9 \equiv 1 \pmod{37} and then
7x7449212214433(mod37). 7^x \equiv 7^4 \equiv 49^2 \equiv 12^2 \equiv 144 \equiv 33 \pmod{37}.
Hence 7x+235(mod37)7^x + 2 \equiv 35 \pmod{37}.

On the other hand, considering the residues of 3n3^n modulo 3737, we have
3927721264123634281030161133251. 3 \rightarrow 9 \rightarrow 27 \rightarrow 7 \rightarrow 21 \rightarrow 26 \rightarrow 4 \rightarrow 12 \rightarrow 36 \rightarrow 34 \rightarrow 28 \rightarrow 10 \rightarrow 30 \rightarrow \\ \rightarrow 16 \rightarrow 11 \rightarrow 33 \rightarrow 25 \rightarrow 1.
We see that 3z≢35(mod37)3^z \not\equiv 35 \pmod{37} for all zz. Therefore, there are no solutions of (1) for x>2x > 2, z>2z > 2.

2) y=2y = 2. We have 3z=7x+42(mod3)3^z = 7^x + 4 \equiv 2 \pmod{3}, a contradiction.

3) y3y \ge 3. Then 7x3z(mod8)7^x \equiv 3^z \pmod{8}, whence x÷2x \div 2 and z÷2z \div 2. Let x=2x1x = 2x_1, z=2z1z = 2z_1. Now the initial equation can be rewritten in the form
(3z17x1)(3z1+7x1)=2y. (3^{z_1} - 7^{x_1})(3^{z_1} + 7^{x_1}) = 2^y.
So, it follows that
3z17x1=2a,(2) 3^{z_1} - 7^{x_1} = 2^a, \qquad (2)
3z1+7x1=2b,(3) 3^{z_1} + 7^{x_1} = 2^b, \qquad (3)
and, since (3z17x1)÷2(3^{z_1} - 7^{x_1}) \div 2, we have b>a1b > a \ge 1. Summing (2) and (3), we obtain 2a+2b=23z12^a + 2^b = 2 \cdot 3^{z_1}. Hence a=1a = 1. Then (2) can be rewritten as 3z17x1=23^{z_1} - 7^{x_1} = 2, or 3z1=7x1+23^{z_1} = 7^{x_1} + 2, which coincides with (1). Therefore, we have {(x1,z1)}={(0,1),(1,2)}\{(x_1, z_1)\} = \{(0, 1), (1, 2)\}, and bb is equal to 22 and 44 respectively.

Finally, in this case we have {(x,y,z)}={(0,3,2),(2,5,4)}\{(x, y, z)\} = \{(0, 3, 2), (2, 5, 4)\}.

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.