Maths Olympiad Prep

Library / /26 of 30

Number theory Difficulty 6.9 National olympiad Prove it Ireland

Find with proof all solutions in nonnegative integers a,b,c,da, b, c, d of the equation
11a5b3c2d=1. 11^a 5^b - 3^c 2^d = 1.

Solution

We consider four cases: d=0d=0, d=1d=1, d=2d=2 and d>2d > 2.

Case 1: d=0d=0. In this case 3c2d3^c 2^d is odd, so there are no solutions.

Case 2: d=1d=1. We have 11a5b23c=111^{a} 5^{b} - 2 \cdot 3^{c} = 1, so c>0c > 0, and, reading mod 4, we see that aa is odd. Next reading mod 3, we get that a+ba+b is even. Hence a=2α+1a = 2\alpha + 1, b=2β+1b = 2\beta + 1, for some nonnegative integers α,β\alpha, \beta. Then 55112α52β23c=155 \cdot 11^{2\alpha} 5^{2\beta} - 2 \cdot 3^c = 1 and c3c \ge 3. Suppose that c>3c > 3. Then we have 55(112α52β1)=54(3c31)55(11^{2\alpha} 5^{2\beta} - 1) = 54(3^{c-3} - 1). Hence 3c313^{c-3} - 1 is divisible by 1111. Since 5 is the order of 3 mod 11, c3=5γc-3 = 5\gamma, for some nonnegative integer γ\gamma, and 3c313^{c-3} - 1 is divisible by 351=21123^5 - 1 = 2 \cdot 11^2. This contradicts the fact that 11211^2 does not divide 55(112α52β1)=54(3c31)55(11^{2\alpha} 5^{2\beta} - 1) = 54(3^{c-3} - 1). So, in this case a=1a=1, b=1b=1, c=3c=3, d=1d=1 is the only solution.

Case 3: d=2d=2. Here 11a5b43c=111^{a} 5^{b} - 4 \cdot 3^{c} = 1, so reading mod 4, we see that aa is even. If c=0c=0, then we have the solution a=0a=0, b=1b=1, c=0c=0, d=2d=2. Suppose that c>0c > 0. Reading mod 3, we see that a+ba+b is even, so aa is even and bb is even. Write a=2αa=2\alpha, b=2βb=2\beta. Now we have (11a5b1)(11a5b+1)=43c(11^{a} 5^{b} - 1)(11^{a} 5^{b} + 1) = 4 \cdot 3^c and this is impossible since the left-hand side is divisible by 8.

Case 4: d>2d > 2. Reading 11a5b3c2d=111^{a} 5^{b} - 3^{c} 2^{d} = 1 mod 4, we see that aa is even. Reading mod 8, we find that bb is even and thus, a=2αa=2\alpha and b=2βb=2\beta for some nonnegative integers α,β\alpha, \beta. Hence (11a5b1)(11a5b+1)=3c2d(11^{a} 5^{b} - 1)(11^{a} 5^{b} + 1) = 3^{c} \cdot 2^{d}. If c=0c=0, then (11a5b1)(11a5b+1)=2d(11^{a} 5^{b} - 1)(11^{a} 5^{b} + 1) = 2^{d}. Since gcd(11a5b1,11a5b+1)=2\gcd(11^{a} 5^{b} - 1, 11^{a} 5^{b} + 1) = 2, and 11a5b1>211^{a} 5^{b} - 1 > 2, this is impossible. Hence c>0c > 0 and we have two possibilities: (i) 11a5b1=3c211^{a} 5^{b} - 1 = 3^{c} \cdot 2 and 11a5b+1=2d111^{a} 5^{b} + 1 = 2^{d-1}, and (ii) 11a5b1=2d111^{a} 5^{b} - 1 = 2^{d-1} and 11a5b+1=3c211^{a} 5^{b} + 1 = 3^{c} \cdot 2, where we again used gcd(11a5b1,11a5b+1)=2\gcd(11^{a} 5^{b} - 1, 11^{a} 5^{b} + 1) = 2. In case (i), we obtain, by subtraction, 2d1=3c2+22^{d-1} = 3^{c} \cdot 2 + 2 and thus 2d2=3c+12^{d-2} = 3^{c} + 1. So 2d21=3c2^{d-2} - 1 = 3^c and d2d-2 is even, say d2=2δd-2 = 2\delta and then (2d1)(2d+1)=3c(2^d - 1)(2^d + 1) = 3^c and thus δ=1\delta = 1 and c=1c=1, since gcd(2d1,2d+1)=1\gcd(2^d - 1, 2^d + 1) = 1. But 11a5b1=611^{a} 5^{b} - 1 = 6 has no solutions.
In case (ii), we have by subtraction 2=3c22d12 = 3^c \cdot 2 - 2^{d-1} and thus 2d2=3c12^{d-2} = 3^c - 1. Then either d=3d=3 and c=1c=1 or, reading mod 4, c=2γc=2\gamma is even. For c>1c > 1, we have 2d2=(3γ1)(3γ+1)2^{d-2} = (3^\gamma - 1)(3^\gamma + 1) and from gcd(3γ1,3γ+1)=2\gcd(3^\gamma - 1, 3^\gamma + 1) = 2 we get γ=1\gamma = 1 and d=5d=5. The case c=1c=1 gives the solution a=0a=0, b=2b=2, c=1c=1, d=3d=3. The case c=2c=2, d=5d=5 does not yield solutions.

Combining all cases, we see that the solutions are 111513321=111^1 \cdot 5^1 - 3^3 \cdot 2^1 = 1, 110513022=111^0 \cdot 5^1 - 3^0 \cdot 2^2 = 1 and 110523123=111^0 \cdot 5^2 - 3^1 \cdot 2^3 = 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.