2005 IMO Shortlist Problems/N3

Problem

(Mongolia) Let $\displaystyle a,\, b,\, c,\, d,\, e,$ , and $\displaystyle f$ be positive integers. Suppose that the sum $\displaystyle S = a+b+c+d+e+f$ divides both $\displaystyle abc + def$ and $\displaystyle ab+bc+ca - de-ef-fd$ . Prove that $\displaystyle S$ is composite.

This was also Problem 1 of the 2nd 2006 German TST, and a problem at the 2006 Indian IMO Training Camp.

Solution

For all integers $\displaystyle x$ we have

$(x+a)(x+b)(x+c) \equiv x^3 + (a+b+c)x^2 + (ab+bc+ca)x + abc \equiv x^3 - (d+e+f)x^2 + (de+ef+fd)x - def$ $\equiv (x-d)(x-e)(x-f) \pmod{S}$ ,

since each coefficient of the first two polynomials is congruent to the corresponding coefficient of the second two polynomials, mod $\displaystyle S$ . Now, suppose $\displaystyle S$ is prime. Since

$(d+a)(d+b)(d+c) \equiv (d-d)(d-e)(d-f) \equiv 0 \pmod{S}$ ,

one of $\displaystyle d+a, d+b, d+c$ is divisible by $\displaystyle S$ , say $\displaystyle d+a$ . Since $\displaystyle d,a > 0$ , this means $d+a \ge S$ . But since $a, \ldots, f$ are positive integers, we then have