Maths Olympiad Prep

Library / /33 of 63

Number theory Difficulty 6.9 National olympiad Prove it Japan

Show that there are no positive integer solutions (a,b,c,d,n)(a, b, c, d, n) satisfying the equation a2+b2+c2+d24abcd=722n1a^2 + b^2 + c^2 + d^2 - 4\sqrt{abcd} = 7 \cdot 2^{2n-1}.

Solution

Assume the existence of a positive integer solution (a,b,c,d,n)(a, b, c, d, n) such that a2+b2+c2+d24abcd=722n1a^2 + b^2 + c^2 + d^2 - 4\sqrt{abcd} = 7 \cdot 2^{2n-1}, and take the one with the minimum value of nn. Since abcd\sqrt{abcd} is rational, abcdabcd must be a square number. First, we establish the following two lemmas. Note that a2+b2+c2+d24abcd=(ab)2+(cd)2+2(abcd)2a^2 + b^2 + c^2 + d^2 - 4\sqrt{abcd} = (a-b)^2 + (c-d)^2 + 2(\sqrt{ab} - \sqrt{cd})^2.

Lemma 1. a,b,c,da, b, c, d are all distinct from each other.
Proof. From the symmetry of a,b,c,da, b, c, d, it suffices to assume a=ba = b and derive a contradiction. Since abcd=a2cdabcd = a^2cd is a square number, cdcd must also be a square number. Therefore, both M=cdM = c - d and N=acdN = a - \sqrt{cd} are integers, and we have M2+2N2=722n1M^2 + 2N^2 = 7 \cdot 2^{2n-1}. Since the residues of square numbers divided by 77 are 0,1,2,0, 1, 2, or 44, the residues of M2M^2 and 2N22N^2 when divided by 77 must also be 0,1,2,0, 1, 2, or 44. Since their sum is a multiple of 77, both MM and NN must be multiples of 77. Therefore, M2+2N2M^2 + 2N^2 is a multiple of 4949. However, 722n17 \cdot 2^{2n-1} is not a multiple of 4949, which is a contradiction. ■

Lemma 2. The product of any two numbers among a,b,c,da, b, c, d is different from the product of the remaining two numbers.
Proof. From the symmetry of a,b,c,da, b, c, d, we only need to derive a contradiction by assuming ab=cdab = cd. Let M=abM = a - b and N=cdN = c - d, then MM and NN are integers, and M2+N2=722n1M^2 + N^2 = 7 \cdot 2^{2n-1} holds. Because the residues of square numbers divided by 77 can only be 0,1,2,0, 1, 2, or 44, as mentioned in Lemma 1, both MM and NN must be multiples of 77. Therefore, M2+N2M^2 + N^2 is a multiple of 4949, but 722n17 \cdot 2^{2n-1} is not, leading to a contradiction. ■

Consider cases based on the value of nn.

(1) n=1n = 1
By the symmetry of a,b,c,da, b, c, d and Lemma 1, we can assume that a<b<c<da < b < c < d. From (da)2+(cb)2+2(adbc)2=14(d-a)^2 + (c-b)^2 + 2(\sqrt{ad} - \sqrt{bc})^2 = 14, we have da14<4d-a \le \sqrt{14} < 4, implying a=b1=c2=d3a = b-1 = c-2 = d-3. We also get bc=a2+3a+2=ad+2bc = a^2 + 3a + 2 = ad + 2 and consequently ad+2ad=2\sqrt{ad} + 2 - \sqrt{ad} = \sqrt{2}, which leads to a contradiction since aa and dd are positive.

(2) n>1n > 1
When a,b,c,da, b, c, d are all even, (a2,b2,c2,d2,n1)(\frac{a}{2}, \frac{b}{2}, \frac{c}{2}, \frac{d}{2}, n-1) satisfies the given equation, contradicting the minimality of nn. Therefore, at least one of a,b,c,da, b, c, d is odd. Since the residues of square numbers divided by 44 are 00 or 11, and a2+b2+c2+d2=722n1+4abcda^2 + b^2 + c^2 + d^2 = 7 \cdot 2^{2n-1} + 4\sqrt{abcd} is divisible by 44, all of a,b,c,da, b, c, d are odd. Since abcdabcd is an odd square number, abcd1(mod4)abcd \equiv 1 \pmod{4}, implying that there are an even number of elements among a,b,c,da, b, c, d that leave a remainder of 33 when divided by 44. Thus, without loss of generality, we can assume ab(mod4)a \equiv b \pmod{4} and cd(mod4)c \equiv d \pmod{4}. Let gg denote the greatest common divisor of abab and cdcd. Then, abg\frac{ab}{g} and cdg\frac{cd}{g} are coprime, and abgcdg=abcdg2\frac{ab}{g} \cdot \frac{cd}{g} = \frac{abcd}{g^2} is a square number. Hence, there exist positive integers xx and yy such that ab=gx2ab = gx^2 and cd=gy2cd = gy^2, and (abcd)2=g(xy)2(\sqrt{ab} - \sqrt{cd})^2 = g(x - y)^2 holds. Since ab(mod4)a \equiv b \pmod{4}, we have ab1(mod4)ab \equiv 1 \pmod{4}, and combined with x21(mod4)x^2 \equiv 1 \pmod{4}, this yields g1(mod4)g \equiv 1 \pmod{4}. By Lemma 1 and Lemma 2, we can find positive odd integers p,q,rp, q, r and non-negative integers α,β,γ\alpha, \beta, \gamma satisfying ab=p2α,cd=q2β|a-b| = p \cdot 2^\alpha, |c-d| = q \cdot 2^\beta, and xy=r2γ|x-y| = r \cdot 2^\gamma. Remark that
722n1=a2+b2+c2+d24abcd=(ab)2+(cd)2+2(abcd)2=p222α+q222β+gr222γ+1 \begin{aligned} 7 \cdot 2^{2n-1} &= a^2 + b^2 + c^2 + d^2 - 4\sqrt{abcd} \\ &= (a-b)^2 + (c-d)^2 + 2(\sqrt{ab} - \sqrt{cd})^2 \\ &= p^2 \cdot 2^{2\alpha} + q^2 \cdot 2^{2\beta} + gr^2 \cdot 2^{2\gamma+1} \end{aligned}
holds. p2q21(mod8)p^2 \equiv q^2 \equiv 1 \pmod{8}, gr21(mod4)gr^2 \equiv 1 \pmod{4} imply a contradiction by the following lemma.

Lemma 3. There exist no non-negative integers α,β,γ\alpha, \beta, \gamma, positive integers n,s,t,un, s, t, u such that st1(mod8)s \equiv t \equiv 1 \pmod{8}, u1(mod4)u \equiv 1 \pmod{4}, and
s22α+t22β+u22γ+1=722n1. s \cdot 2^{2\alpha} + t \cdot 2^{2\beta} + u \cdot 2^{2\gamma+1} = 7 \cdot 2^{2n-1}.
Proof. By the symmetry of (α,s)(\alpha, s) and (β,t)(\beta, t), we can assume αβ\alpha \le \beta.

* case when αγ\alpha \le \gamma
Since s+t22(βα)+u22(γα)+1=722(nα)1s+t \cdot 2^{2(\beta-\alpha)} + u \cdot 2^{2(\gamma-\alpha)+1} = 7 \cdot 2^{2(n-\alpha)-1} is a positive integer, we must have nα1n-\alpha \ge 1. Therefore, both u22(γα)+1u \cdot 2^{2(\gamma-\alpha)+1} and 722(nα)17 \cdot 2^{2(n-\alpha)-1} are even, implying that s+t22(βα)s+t \cdot 2^{2(\beta-\alpha)} is even as well, and consequently, α=β\alpha = \beta. Since s+t20s+t \cdot 2^0 cannot be divisible by 44, we obtain either γα=0\gamma-\alpha = 0 or nα=1n-\alpha = 1. In the former case, 722(nα)1=s+t+2u4(mod8)7 \cdot 2^{2(n-\alpha)-1} = s+t+2u \equiv 4 \pmod{8}, leading to a contradiction. In the latter case, u22(γα)+1=14st4(mod8)u \cdot 2^{2(\gamma-\alpha)+1} = 14-s-t \equiv 4 \pmod{8}, which also contradicts the conditions.

* case when γ<α\gamma < \alpha
Since s22(αγ)+t22(βγ)+2u=722(nγ)1s \cdot 2^{2(\alpha-\gamma)} + t \cdot 2^{2(\beta-\gamma)} + 2u = 7 \cdot 2^{2(n-\gamma)-1} has a remainder of 22 when divided by 44, we must have nγ=1n-\gamma = 1. In this case, 22(βγ)<142^{2(\beta-\gamma)} < 14, implying αγβγ1\alpha-\gamma \le \beta-\gamma \le 1, which leads to αγ=βγ=1\alpha-\gamma = \beta-\gamma = 1. Therefore, we have 2s+2t+u=72s+2t+u = 7, but 2s+2t+u1(mod4)2s+2t+u \equiv 1 \pmod{4}, which is a contradiction.

Therefore we have proved the lemma.

Therefore, there are no solutions (a,b,c,d,n)(a, b, c, d, n).

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.