Maths Olympiad Prep

Library / /13 of 18

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:

Decide whether there exist positive integers a,b,ca, b, c such that 3(ab+bc+ca)3(a b + b c + c a) divides a2+b2+c2a^{2} + b^{2} + c^{2}.

Solution

Solution:

The answer is no: such integers do not exist. In what follows, νp(n)\nu_{p}(n) will denote the exponent of pp in the prime factorization of nn.

Assume without loss of generality that a,b,ca, b, c do not have some common divisor, and a2+b2+c2=3k(ab+bc+ca)a^{2} + b^{2} + c^{2} = 3k(a b + b c + c a). Write
(3k+2)(a2+b2+c2)=3k(a+b+c)2. (3k + 2)\left(a^{2} + b^{2} + c^{2}\right) = 3k \cdot (a + b + c)^{2}.

Since 3k+22(mod3)3k + 2 \equiv 2 \pmod{3}, there is a prime p2(mod3)p \equiv 2 \pmod{3} with νp(3k+2)\nu_{p}(3k + 2) odd (in particular, p3k+2p \mid 3k + 2).
We first show that p2p \neq 2. Let us assume on the contrary that ν2(3k+2)\nu_{2}(3k + 2) is odd (in particular, kk is even). Remark that since a,b,ca, b, c are not all even, ν2(a2+b2+c2)1\nu_{2}\left(a^{2} + b^{2} + c^{2}\right) \leq 1. Furthermore,
ν2(a+b+c)=0ν2(a2+b2+c2)=0. \nu_{2}(a + b + c) = 0 \Longleftrightarrow \nu_{2}\left(a^{2} + b^{2} + c^{2}\right) = 0.

Now we consider two cases.
- Assume ν2(k)2\nu_{2}(k) \geq 2. Then ν2(3k+2)=1\nu_{2}(3k + 2) = 1, ν2(a2+b2+c2)1\nu_{2}\left(a^{2} + b^{2} + c^{2}\right) \leq 1. Therefore
ν2(k)+2ν2(a+b+c)2ν2(3k+2)+ν2(a2+b2+c2) \nu_{2}(k) + 2\nu_{2}(a + b + c) \geq 2 \geq \nu_{2}(3k + 2) + \nu_{2}\left(a^{2} + b^{2} + c^{2}\right)
but equality cannot occur since the relations
ν2(a+b+c)=0andν2(a2+b2+c2)=1 \nu_{2}(a + b + c) = 0 \quad \text{and} \quad \nu_{2}\left(a^{2} + b^{2} + c^{2}\right) = 1
cannot hold simultaneously.

- Assume ν2(k)=1\nu_{2}(k) = 1. Then ν2(3k+2)>1\nu_{2}(3k + 2) > 1 and is odd. Now
ν2(3k+2)+ν2(a2+b2+c2)=1+2ν2(a+b+c). \nu_{2}(3k + 2) + \nu_{2}\left(a^{2} + b^{2} + c^{2}\right) = 1 + 2\nu_{2}(a + b + c).
Thus ν2(a2+b2+c2)\nu_{2}\left(a^{2} + b^{2} + c^{2}\right) must be even, so it is zero; consequently ν2(a+b+c)=0\nu_{2}(a + b + c) = 0 as well and we obtain 1<v2(3k+2)=11 < v_{2}(3k + 2) = 1.

Now for the interesting part. Remark pa+b+cp \mid a + b + c and pa2+b2+c2p \mid a^{2} + b^{2} + c^{2}. Without loss of generality b≢0(modp)b \not\equiv 0 \pmod{p}, so that
a2+b2+(a+b)20(modp)a2+ab+b20(modp) a^{2} + b^{2} + (a + b)^{2} \equiv 0 \pmod{p} \Longrightarrow a^{2} + a b + b^{2} \equiv 0 \pmod{p}
Then if x=ab1x = a b^{-1}, we get that x2+x+10(modp)x^{2} + x + 1 \equiv 0 \pmod{p}. But the left-hand side is the third cyclotomic polynomial, so either p=3p = 3 or 3p13 \mid p - 1, but neither is the case.

Therefore, such a triple (a,b,c)(a, b, c) does not exist.

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.