Maths Olympiad Prep

Library / /1 of 3

Number theory Difficulty 5.8 AIME, harder Prove it Hong Kong

Find all positive integer(s) nn such that (2n1)(5n1)(2^n - 1)(5^n - 1) is a perfect square.

Solution

n=1n = 1.
When n=1n = 1, (211)(511)=4(2^1 - 1)(5^1 - 1) = 4 is a perfect square. Suppose n>1n > 1.

* If n3(mod4)n \equiv 3 \pmod{4}, we have (2n1)(5n1)(2)(1)3(mod5)(2^n - 1)(5^n - 1) \equiv (2)(-1) \equiv 3 \pmod{5}, which is not true for a square.

* If n1(mod4)n \equiv 1 \pmod{4}, we rewrite
(2n1)(5n1)=(2n1)4(5n1+5n2++1). (2^n - 1)(5^n - 1) = (2^n - 1) \cdot 4(5^{n-1} + 5^{n-2} + \dots + 1).
If this is a square, so is (2n1)(5n1+5n2++1)(2^n - 1)(5^{n-1} + 5^{n-2} + \dots + 1). However,
(2n1)(5n1+5n2++1)(1)(1+1++1)=n3(mod4), (2^n - 1)(5^{n-1} + 5^{n-2} + \dots + 1) \equiv (-1)(1 + 1 + \dots + 1) = -n \equiv 3 \pmod{4},
which is not true for a square.

* If n=2mn = 2m is even, suppose (2n1)(5n1)(2^n - 1)(5^n - 1) is a perfect square. Let 2n1=ds22^n - 1 = ds^2 and 5n1=dt25^n - 1 = dt^2 where dd is squarefree. We first show that d>1d > 1. Indeed, if d=1d = 1, then 52mt2=15^{2m} - t^2 = 1. This gives (5mt)(5m+t)=1(5^m - t)(5^m + t) = 1, which is impossible as t>0t > 0. Now, it is known that the solutions to Pell's equation x2dy2=1x^2 - dy^2 = 1 are generated by (x1+y1d)n=xn+ynd(x_1 + y_1\sqrt{d})^n = x_n + y_n\sqrt{d}, where (x1,y1)(x_1, y_1) is the fundamental solution.
Claim. Let (xk,yk)(x_k, y_k) be a solution to x2dy2=1x^2 - dy^2 = 1.
(i) If k0(mod2)k \equiv 0 \pmod{2}, then xk1(mod2)x_k \equiv 1 \pmod{2} and yk0(mod2)y_k \equiv 0 \pmod{2}.
(ii) If k1(mod2)k \equiv 1 \pmod{2}, then xkx1(mod2)x_k \equiv x_1 \pmod{2} and yky1(mod2)y_k \equiv y_1 \pmod{2}.

Proof.
(i) Let k=2lk = 2l. Then we have
xk+ykd=(x1+y1d)2l=(xl+yld)2=xl2+dyl2+2xlyld=2xl21+2xlyld. \begin{aligned} x_k + y_k \sqrt{d} &= (x_1 + y_1 \sqrt{d})^{2l} \\ &= (x_l + y_l \sqrt{d})^2 \\ &= x_l^2 + dy_l^2 + 2x_l y_l \sqrt{d} \\ &= 2x_l^2 - 1 + 2x_l y_l \sqrt{d}. \end{aligned}
So xk=2xl211(mod2)x_k = 2x_l^2 - 1 \equiv 1 \pmod{2} and yk=2xlyl0(mod2)y_k = 2x_l y_l \equiv 0 \pmod{2}.

x2l+1=x2lx1+y2ly1dx1(mod2), x_{2l+1} = x_{2l}x_1 + y_{2l}y_1 d \equiv x_1 \pmod{2},
y2l+1=x2ly1+x1y2ly1(mod2). y_{2l+1} = x_{2l}y_1 + x_1 y_{2l} \equiv y_1 \pmod{2}.
\Box
Now, since 22m1=ds22^{2m} - 1 = ds^2, (x,y)=(2m,s)(x, y) = (2^m, s) is a solution to x2dy2=1x^2 - dy^2 = 1. By the claim, we must have x10(mod2)x_1 \equiv 0 \pmod{2}. Similarly, since 52m1=dt25^{2m} - 1 = dt^2, (xk,yk)=(5m,t)(x_k, y_k) = (5^m, t) is another solution. By the claim, as 5m≢x1(mod2)5^m \not\equiv x_1 \pmod{2}, we must have k0(mod2)k \equiv 0 \pmod{2}. Let k=2lk = 2l. Then we have 5m=x2l=2xl215^m = x_{2l} = 2x_l^2 - 1. This implies 2xl210(mod5)2x_l^2 - 1 \equiv 0 \pmod{5}, and hence xl23(mod5)x_l^2 \equiv 3 \pmod{5}. This is impossible.
Therefore, the only solution is n=1n = 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 reproduced verbatim; metadata (topic, difficulty) added by this project.