# Prove $S$ is composite

HINTS ONLY

Let $a, b, c, d, e, f$ be positive integers. Suppose that $S = a + b + c + d + e + f$ divides both $abc + def$ and $ab + bc + ca − de − ef − fd$. Prove that $S$ is composite.

Must be solved using polynomials in some way

HINTS ONLY

I was thinking of defining $P(x) = (x + a)(x + b)(x+c) + (x + d)(x + e)(x + f)$ such that $P(0) = abc + def$. And $S | P(0)$.

But besides that, I dont see anything obvious.

• This looks familiar; do you know the (original) source of the problem? – bakula Nov 5 '15 at 14:57
• @bakula IMO shortlist 2005, problem N3, see here. – Wojowu Nov 5 '15 at 14:59
• @Wojowu thanks :) – bakula Nov 5 '15 at 15:01
• Why is the hint unclear? Another hint (to add to the answer): Euclid's lemma. – user236182 Nov 5 '15 at 20:53

Hint: $S$ divides all coefficients of $f(x)=(x+a)(x+b)(x+c)-(x-d)(x-e)(x-f)$, so it divides $f(d)$. What would happen if $S$ was prime?
• (+1), mmm. $S | f(d) = (a + d)(d + b)(d + c)$. If $S$ is prime then it is not divisible by any other numbers. $f(d) = kS + 0 = kS$ for some integer $k$. Then $S = f(d)/k$. No other number divides $S$, so $\pmod{f(d)}$ it gives: $S \equiv t \pmod{f(d)} \implies S \equiv t \pmod{kS} \implies S = t + nkS.$ For an integer $n$. And $t > 0$. Is this headed the right direction? – Amad27 Nov 6 '15 at 16:55
• Okay. So $f(d) = (d +a)(d+b)(d+c)$, and so $S$ must divide at least a pair or another factor. So, suppose $S| (d + a)$ at least. Then what could I do? I don't see a possible end to this, if I go about this way. Is there something else I am missing? – Amad27 Nov 7 '15 at 16:41
• Remember that $S=a+b+c+d+e+f>d+a$. – Wojowu Nov 7 '15 at 16:44
• Yeah I thought of this, and thought this was a contradiction. But then realized that this isn't the only case. Consider: $S| (a + d)(d + b)$ then, $S|(ad + ab + d^2 + db)$ which doesn't lead anywhere – Amad27 Nov 7 '15 at 17:46