2005 IMO Shortlist Problems/N3
(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.
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.