6th USAMO 1977

For which positive integers a, b does (x^a + ... + x + 1) divide (x^ab + x^ab-b + ... + x^2b + x^b + 1)?

Solution

Answer: a+1 and b relatively prime.

The question is when (x^a+1 - 1)/(x - 1) divides (x^b(a+1) - 1)/(x^b - 1) or when (x^a+1 - 1)(x^b - 1) divides (x^b(a+1) - 1)(x - 1). Now both (x^a+1 - 1) and (x^b - 1) divide (x^b(a+1) - 1). They both have a factor (x - 1), so if that is their only common factor, then their product divides (x^b(a+1) - 1)(x - 1). That is true if a+1 and b are relatively prime, for the roots of x^k - 1 are the kth roots of 1. Thus if a+1 and b are relatively prime, then the only (complex) number which is an (a+1)th root of 1 and a bth root of 1 is 1.

But suppose d is a common factor of a+1 and b, then exp(2πi/d) is a root of both x^a+1 - 1 and x^b - 1. It is a root of x^b(a+1) - 1, but only with multiplicity 1, so (x^a+1 - 1)(x^b - 1) does not divide (x^b(a+1) - 1)(x - 1).

6th USAMO 1977

© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002