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


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.

Hints please?

  • $\begingroup$ This looks familiar; do you know the (original) source of the problem? $\endgroup$ – bakula Nov 5 '15 at 14:57
  • $\begingroup$ @bakula IMO shortlist 2005, problem N3, see here. $\endgroup$ – Wojowu Nov 5 '15 at 14:59
  • $\begingroup$ @Wojowu thanks :) $\endgroup$ – bakula Nov 5 '15 at 15:01
  • $\begingroup$ Why is the hint unclear? Another hint (to add to the answer): Euclid's lemma. $\endgroup$ – 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?

| cite | improve this answer | |
  • $\begingroup$ (+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? $\endgroup$ – Amad27 Nov 6 '15 at 16:55
  • $\begingroup$ This isn't exactly how I would go about doing it. I would go and use the further hint which user236182 has given in a comment to the question. $\endgroup$ – Wojowu Nov 6 '15 at 17:04
  • $\begingroup$ 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? $\endgroup$ – Amad27 Nov 7 '15 at 16:41
  • $\begingroup$ Remember that $S=a+b+c+d+e+f>d+a$. $\endgroup$ – Wojowu Nov 7 '15 at 16:44
  • $\begingroup$ 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 $\endgroup$ – Amad27 Nov 7 '15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.