Maths Olympiad Prep

Library / /35 of 50

Number theory Difficulty 5.7 AIME, harder Prove it Belarus

Find all integers aa and bb satisfying the equality
3a5b=2. 3^a - 5^b = 2.

Solution

(Solution of D. Babrou.) If a3a \le 3 or b2b \le 2, then we see that only the pairs (a;b)=(1;0)(a; b) = (1; 0), (a;b)=(3;2)(a; b) = (3; 2) satisfy the equation 3a5b=23^a - 5^b = 2.

Let now a4a \ge 4 and b3b \ge 3. We rewrite the equation in the form 33(3a31)=52(5b21)3^3(3^{a-3} - 1) = 5^2(5^{b-2} - 1). Setting x=a3x = a - 3, y=b2y = b - 2 (x,y>0x, y > 0) we obtain 33(3x1)=52(5y1)3^3(3^x - 1) = 5^2(5^y - 1).

It is easy to verify that the least possible nn with 3n1(mod25)3^n \equiv 1 \pmod{25} is n=20n = 20, hence we have x20x \equiv 20.

Similarly we conclude that y18(mod15)y \equiv 18 \pmod{15} because the least nn with 5n1(mod27)5^n \equiv 1 \pmod{27} is n=18n = 18. So, 5y119(mod19)5^y - 1 \equiv 19 \pmod{19}.

Further, the smallest positive xx such that 3x1(mod19)3^x \equiv 1 \pmod{19} is 18, so x180(mod100)x \equiv 180 \pmod{100}. Since x10(mod10)x \equiv 10 \pmod{10}, we have 3x111(mod11)3^x - 1 \equiv 11 \pmod{11}, then 5y111(mod11)5^y - 1 \equiv 11 \pmod{11}.

The smallest positive yy such that 5y111(mod5)5^y - 1 \equiv 11 \pmod{5}, hence
y90518y \equiv 90 \equiv 5 \cdot 18. Since x12(mod12)x \equiv 12 \pmod{12}, we have 3x113(mod13)3^x - 1 \equiv 13 \pmod{13}. Then 5y113(mod13)5^y - 1 \equiv 13 \pmod{13}.

The order of 5 modulo 13 is 4, hence y4(mod13)y \equiv 4 \pmod{13}, thus y180(mod12)y \equiv 180 \pmod{12}. Then y12(mod12)y \equiv 12 \pmod{12}.

Since 5121=(561)(56+1)5^{12} - 1 = (5^6 - 1)(5^6 + 1), 56+1601(mod601)=5452+15^6 + 1 \equiv 601 \pmod{601} = 5^4 - 5^2 + 1, where 601 is a prime number, we have 5y1601(mod601)5^y - 1 \equiv 601 \pmod{601} hence also 3y1601(mod601)3^y - 1 \equiv 601 \pmod{601}. Note that φ(601)=600=5224\varphi(601) = 600 = 5^2 \cdot 24.

Let α\alpha be the order 3 modulo 601. If α25\alpha \nmid 25, then α\alpha is a divisor of 120 (since 600α600 \nmid \alpha). So if 312016013^{120} - 1 \nmid 601, then α25(mod601)\alpha \equiv 25 \pmod{601}, and x25(mod601)x \equiv 25 \pmod{601}.

We have 3120172920112820121401(mod601)3^{120} - 1 \equiv 729^{20} - 1 \equiv 128^{20} - 1 \equiv 2^{140} - 1 \pmod{601}.

If 220≢12^{20} \not\equiv 1, then 2140≢1(mod601)2^{140} \not\equiv 1 \pmod{601} since 7 is not a divisor of 600. Next 220=10242=4232≢1(mod601)2^{20} = 1024^2 = 423^2 \not\equiv 1 \pmod{601}, indeed.

Therefore x25(mod601)x \equiv 25 \pmod{601}, so x100(mod601)x \equiv 100 \pmod{601}.

Further, since φ(125)=100\varphi(125) = 100, it follows that 3x1125(mod125)3^x - 1 \equiv 125 \pmod{125}, but if y>0y > 0, then 52(5y1)1255^2(5^y - 1) \nmid 125. Thus x=y=0x = y = 0 contrary to x,y>0x, y > 0. Therefore the only pairs mentioned above are the solutions of given equation.

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.