Maths Olympiad Prep

Library / /43 of 92

Number theory Difficulty 6.3 National olympiad Prove it Iran

Do there exist natural numbers aa, bb and cc such that a2+b2+c2a^2 + b^2 + c^2 is divisible by 2013(ab+bc+ca)2013(ab + bc + ca)?

Solution

Lemma 1. Let A2(mod3)A \equiv 2 \pmod{3} be a positive integer. Then there exists a prime number pp such that p2(mod3)p \equiv 2 \pmod{3} and pαAp^\alpha \mid A where α\alpha is an odd integer.

Proof of lemma. Assume to the contrary that there is not such a prime number pp. Therefore, if A=p1α1p2α2pkαkA = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} is the prime factorization of AA, we have two cases for pip_i's, 1ik1 \le i \le k, to consider:

Case 1. pi1(mod3)piαi1(mod3)p_i \equiv 1 \pmod{3} \Rightarrow p_i^{\alpha_i} \equiv 1 \pmod{3}.

Case 2. pi2(mod3)p_i \equiv 2 \pmod{3} and 2αipiαi(pi2)αi21(mod3)2|\alpha_i \Rightarrow p_i^{\alpha_i} \equiv (p_i^2)^{\frac{\alpha_i}{2}} \equiv 1 \pmod{3}.

As a result, we must have A1(mod3)A \equiv 1 \pmod{3} which is a contradiction. \square

Lemma 2. Let p2(mod3)p \equiv 2 \pmod{3} be a prime number. Show that {03,13,,(p1)3}\{0^3, 1^3, \dots, (p-1)^3\} is a complete residue system modulo pp.

Proof of lemma. Obviously i303(modp)i^3 \equiv 0^3 \pmod{p} iff i0(modp)i \equiv 0 \pmod{p}. Suppose that pi,jp \nmid i, j. Our goal is to show that i3j3(modp)i^3 \equiv j^3 \pmod{p} iff ij(modp)i \equiv j \pmod{p}. One part of the proof is obvious. To prove the other part, suppose that p=3t+2p = 3t + 2. Then by Fermat's Little Theorem, we have i3t+1j3t+11(modp)i^{3t+1} \equiv j^{3t+1} \equiv 1 \pmod{p}. Hence, we have
i3tii3t+1j3t+1(j3)tji3tj(modp). i^{3t} i \equiv i^{3t+1} \equiv j^{3t+1} \equiv (j^3)^t j \equiv i^{3t} j \pmod{p}.
Since (i,p)=1(i, p) = 1, we get ij(modp)i \equiv j \pmod{p}. \square

Now we are ready to solve the main problem. We claim that there is no such triple. Assume to the contrary that
a2+b2+c2=2013k(ab+bc+ca) a^2 + b^2 + c^2 = 2013k(ab + bc + ca)
for some positive integer kk.

First, without loss of generality we can suppose that aa, bb and cc have no common factor, because if (a,b,c)=d>1(a, b, c) = d > 1, we can divide them by dd to get a new triple with no common factor. We have (a+b+c)2=(2013k+2)(ab+bc+ca)(a+b+c)^2 = (2013k+2)(ab+bc+ca). 2013k+22(mod3)2013k+2 \equiv 2 \pmod{3}, so by lemma 1 there is some prime number p2(mod3)p \equiv 2 \pmod{3} such that p2n+12013k+2p^{2n+1} \nmid 2013k+2 (n0n \ge 0).
p2n+12013k+2p2n+1(a+b+c)2p2n+2(a+b+c)2p2n+2(2013k+2)(ab+bc+ca)pab+bc+ca. \begin{aligned} p^{2n+1} \nmid 2013k+2 & \Rightarrow p^{2n+1}|(a+b+c)^2 \Rightarrow p^{2n+2}|(a+b+c)^2 \\ & \Rightarrow p^{2n+2}|(2013k+2)(ab+bc+ca) \Rightarrow p|ab+bc+ca. \end{aligned}
As a result, pa+b+cp|a+b+c and pab+bc+cap|ab+bc+ca. Hence
0ab+bc+caab+c(a+b)ab+c(c)(modp)abc2(modp)c3abc(modp). \begin{aligned} 0 &\equiv ab + bc + ca \equiv ab + c(a+b) \equiv ab + c(-c) \pmod{p} \Rightarrow ab \equiv c^2 \pmod{p} \\ & \Rightarrow c^3 \equiv abc \pmod{p}. \end{aligned}
By a similar argument, a3b3abc(modp)a^3 \equiv b^3 \equiv abc \pmod{p}, so by lemma 2 we deduce abc(modp)a \equiv b \equiv c \pmod{p} and since pa+b+cp|a+b+c and 3p3 \nmid p, we find that pp divides aa, bb and cc, which contradicts our assumption that (a,b,c)=1(a, b, c) = 1. \square

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.