2005 IMO Shortlist Problems/N3

Problem

(Mongolia) Let $a$, $b$, $c$, $d$, $e$, and $f$ be positive integers. Suppose that the sum $S = a+b+c+d+e+f$ divides both $abc + def$ and $ab+bc+ca - de-ef-fd$. Prove that $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

$S > d+a \ge S$,

a contradiction.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources