Maths Olympiad Prep

Library / /126 of 520

Number theory Difficulty 5.9 AIME, harder Find the answer

Find all positive integers x,y,zx, y, z such that

45x6y=2019z 45^{x}-6^{y}=2019^{z}

A number or a short expression. Spacing and $ signs are ignored.

Solution

We define v3(n)v_{3}(n) to be the non-negative integer kk such that 3kn3^{k} \mid n but 3k+1n3^{k+1} \nmid n. The equation is equivalent to

32x5x3y2y=3z673z 3^{2 x} \cdot 5^{x}-3^{y} \cdot 2^{y}=3^{z} \cdot 673^{z}

We will consider the cases y2xy \neq 2 x and y=2xy=2 x separately.

Case 1. Suppose y2xy \neq 2 x. Since 45x>45x6y=2019z>45z45^{x}>45^{x}-6^{y}=2019^{z}>45^{z}, then x>zx>z and so 2x>z2 x>z. We have

z=v3(3z673z)=v3(32x5x3y2y)=min{2x,y} z=v_{3}\left(3^{z} \cdot 673^{z}\right)=v_{3}\left(3^{2 x} \cdot 5^{x}-3^{y} \cdot 2^{y}\right)=\min \{2 x, y\}

as y2xy \neq 2 x. Since 2x>z2 x>z, we get z=yz=y. Hence the equation becomes 32x5x3y2y=3^{2 x} \cdot 5^{x}-3^{y} \cdot 2^{y}= 3y673y3^{y} \cdot 673^{y}, or equivalently,

32xy5x=2y+673y 3^{2 x-y} \cdot 5^{x}=2^{y}+673^{y}

Case 1.1. Suppose y=1y=1. Doing easy manipulations we have

32x15x=2+673=675=335245x2=1x=2 3^{2 x-1} \cdot 5^{x}=2+673=675=3^{3} \cdot 5^{2} \Longrightarrow 45^{x-2}=1 \Longrightarrow x=2

Hence one solution which satisfies the condition is (x,y,z)=(2,1,1)(x, y, z)=(2,1,1).

Case 1.2. Suppose y2y \geqslant 2. Using properties of congruences we have

12y+673y32xy5y(1)2xymod4 1 \equiv 2^{y}+673^{y} \equiv 3^{2 x-y} \cdot 5^{y} \equiv(-1)^{2 x-y} \bmod 4

Hence 2xy2 x-y is even, which implies that yy is even. Using this fact we have

032xy5y2y+673y1+12mod3 0 \equiv 3^{2 x-y} \cdot 5^{y} \equiv 2^{y}+673^{y} \equiv 1+1 \equiv 2 \bmod 3

which is a contradiction.

Case 2. Suppose y=2xy=2 x. The equation becomes 32x5x32x22x=3z673z3^{2 x} \cdot 5^{x}-3^{2 x} \cdot 2^{2 x}=3^{z} \cdot 673^{z}, or equivalently,

5x4x=3z2x673z 5^{x}-4^{x}=3^{z-2 x} \cdot 673^{z}

Working modulo 3 we have

(1)x15x4x3z2x673z0mod3 (-1)^{x}-1 \equiv 5^{x}-4^{x} \equiv 3^{z-2 x} \cdot 673^{z} \equiv 0 \bmod 3

hence xx is even, say x=2tx=2 t for some positive integer tt. The equation is now equivalent to

(5t4t)(5t+4t)=3z4t673z \left(5^{t}-4^{t}\right)\left(5^{t}+4^{t}\right)=3^{z-4 t} \cdot 673^{z}

It can be checked by hand that t=1t=1 is not possible. For t2t \geqslant 2, since 3 and 673 are the only prime factors of the right hand side, and since, as it is easily checked gcd(5t4t,5t+4t)=1\operatorname{gcd}\left(5^{t}-4^{t}, 5^{t}+4^{t}\right)=1 and 5t4t>15^{t}-4^{t}>1, the only way for this to happen is when 5t4t=3z4t5^{t}-4^{t}=3^{z-4 t} and 5t+4t=673z5^{t}+4^{t}=673^{z} or 5t4t=673z5^{t}-4^{t}=673^{z} and 5t+4t=3z4t5^{t}+4^{t}=3^{z-4 t}. Adding together we have

25t=3z4t+673z 2 \cdot 5^{t}=3^{z-4 t}+673^{z}

Working modulo 5 we have

025t3z4t+673z34t3z4t+3z23zmod5 0 \equiv 2 \cdot 5^{t} \equiv 3^{z-4 t}+673^{z} \equiv 3^{4 t} \cdot 3^{z-4 t}+3^{z} \equiv 2 \cdot 3^{z} \bmod 5

which is a contradiction. Hence the only solution which satisfies the equation is (x,y,z)=(x, y, z)= (2,1,1)(2,1,1).

Alternative Solution by PSC. Working modulo 5 we see that 14zmod5-1 \equiv 4^{z} \bmod 5 and therefore zz is odd. Now working modulo 4 and using the fact that zz is odd we get that 12y3z3mod41-2^{y} \equiv 3^{z} \equiv 3 \bmod 4. This gives y=1y=1. Now working modulo 9 we have 63zmod9-6 \equiv 3^{z} \bmod 9 which gives z=1z=1. Now since y=z=1y=z=1 we get x=2x=2 and so (2,1,1)(2,1,1) is the unique solution.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.