Maths Olympiad Prep

Library / /8 of 38

Number theory Difficulty 6.4 National olympiad Prove it China

Find all non-negative integer solutions (x,y,z,w)(x, y, z, w) of the following equation
2x3y5z7w=1. 2^x \cdot 3^y - 5^z \cdot 7^w = 1.

Solution

Since 5z7w+15^z \cdot 7^w + 1 is even, we have x1x \ge 1.

Case 1: y=0y = 0. The equation to be solved becomes
2x5z7w=1. 2^x - 5^z \cdot 7^w = 1.
If z0z \neq 0, then 2x1(mod5)2^x \equiv 1 \pmod{5}. It follows that 4x4 \mid x. Thus 32x13 \mid 2^x - 1, which contradicts to 2x5z7w=12^x - 5^z \cdot 7^w = 1.
If z=0z = 0, then
2x7w=1. 2^x - 7^w = 1.
When x=1,2,3x = 1, 2, 3, a direct computation shows that (x,w)=(1,0),(3,1)(x, w) = (1, 0), (3, 1) are the solutions.
When x4x \ge 4, 7w1(mod16)7^w \equiv -1 \pmod{16}. By direct computation we know that this is impossible.
Consequently, when y=0y = 0 all non-negative integer solutions of the equation are
(x,y,z,w)=(1,0,0,0),(3,0,0,1). (x, y, z, w) = (1, 0, 0, 0), (3, 0, 0, 1).

Case 2: y>0y > 0 and x=1x = 1. Thus the equation to be solved becomes
23y5z7w=1. 2 \cdot 3^y - 5^z \cdot 7^w = 1.
Hence 5z7w1(mod3)-5^z \cdot 7^w \equiv 1 \pmod{3}, i.e., (1)z1(mod3)(-1)^z \equiv -1 \pmod{3}. It follows that zz is odd.
Thus
23y1(mod5). 2 \cdot 3^y \equiv 1 \pmod{5}.
y1(mod4). y \equiv 1 \pmod{4}.
When w0w \neq 0, we have 23y1(mod7)2 \cdot 3^y \equiv 1 \pmod{7}. Thus y4(mod6)y \equiv 4 \pmod{6}, which contradicts to the fact y1(mod4)y \equiv 1 \pmod{4}. Hence w=0w = 0 and
23y5z=1. 2 \cdot 3^y - 5^z = 1.
When y=1y = 1, we have z=1z = 1. If y2y \ge 2, then 5z1(mod9)5^z \equiv -1 \pmod{9}, which implies z3(mod6)z \equiv 3 \pmod{6}. Thus 53+1(mod5z+1)5^3 + 1 \pmod{5^z + 1}, so 7(mod5z+1)7 \pmod{5^z + 1}, which contradicts to 5z+1=23y5^z + 1 = 2 \cdot 3^y. Hence in this case we have only one solution
(x,y,z,w)=(1,1,1,0). (x, y, z, w) = (1, 1, 1, 0).

Case 3: y>0y > 0 and x2x \ge 2. Thus
5z7w1(mod4), and 5z7w1(mod3). 5^z \cdot 7^w \equiv -1 \pmod{4}, \text{ and } 5^z \cdot 7^w \equiv -1 \pmod{3}.
That is,
(1)w1(mod4), and (1)z1(mod3). (-1)^w \equiv -1 \pmod{4}, \text{ and } (-1)^z \equiv -1 \pmod{3}.
Thus zz and ww are odd. It follows that
2x3y=5z7w+135+14(mod8). 2^x \cdot 3^y = 5^z \cdot 7^w + 1 \equiv 35 + 1 \equiv 4 \pmod{8}.
Hence, x=2x = 2, and
43y5z7w=1 (where z and w are odd). 4 \cdot 3^y - 5^z \cdot 7^w = 1 \text{ (where $z$ and $w$ are odd).}
Thus,
43y1(mod5), and 43y1(mod7). 4 \cdot 3^y \equiv 1 \pmod{5}, \text{ and } 4 \cdot 3^y \equiv 1 \pmod{7}.
From the above two congruencies we have y2(mod12)y \equiv 2 \pmod{12}.
Set y=12m+2y = 12m + 2, m0m \ge 0, then
5z7w=43y1=(236m+11)(236m+1+1). 5^z \cdot 7^w = 4 \cdot 3^y - 1 = (2 \cdot 3^{6m+1} - 1)(2 \cdot 3^{6m+1} + 1).
Since
236m+1+1623m+16+10(mod7), 2 \cdot 3^{6m+1} + 1 \equiv 6 \cdot 2^{3m} + 1 \equiv 6 + 1 \equiv 0 \pmod{7},
and
(236m+11,236m+1+1)=1,(2 \cdot 3^{6m+1} - 1, 2 \cdot 3^{6m+1} + 1) = 1, so 5236m+115 \mid 2 \cdot 3^{6m+1} - 1.
Thus
236m+11=5z,2 \cdot 3^{6m+1} - 1 = 5^z,
236m+1+1=7w.2 \cdot 3^{6m+1} + 1 = 7^w.
If m1m \ge 1, by Equation (2) we have 5z1(mod9)5^z \equiv -1 \pmod{9}, and from Case 2 we know that this is impossible.
If m=0m=0, then y=2y=2, z=1z=1 and w=1w=1. Thus in this case, we have only one solution
(x,y,z,w)=(2,2,1,1). (x, y, z, w) = (2, 2, 1, 1).

Consequently, all non-negative integer solutions are
(x,y,z,w)=(1,0,0,0),(3,0,0,1),(1,1,1,0),(2,2,1,1). (x, y, z, w) = (1, 0, 0, 0), (3, 0, 0, 1), \\ (1, 1, 1, 0), (2, 2, 1, 1).

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.