2005 IMO Shortlist Problems/N3
Problem
(Mongolia) Let , , , , , and be positive integers. Suppose that the sum divides both and . Prove that 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 we have
,
since each coefficient of the first two polynomials is congruent to the corresponding coefficient of the second two polynomials, mod . Now, suppose is prime. Since
,
one of is divisible by , say . Since , this means . But since are positive integers, we then have
,
a contradiction. ∎
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.