1977 USAMO Problems/Problem 1
Problem
Determine all pairs of positive integers such that
$(1\plus{}x^n\plus{}x^{2n}\plus{}\cdots\plus{}x^{mn})$ (Error compiling LaTeX. Unknown error_msg) is divisible by $(1\plus{}x\plus{}x^2\plus{}\cdots\plus{}x^{m})$ (Error compiling LaTeX. Unknown error_msg).
(Incorrect) Solution
Denote the first and larger polynomial to be and the second one to be
. In order for
to be divisible by
they must have the same roots. The roots of
are the mth roots of unity, except for 1. When plugging into
, the root of unity is a root of
if and only if the terms
all represent a different mth root of unity.
Note that if , the numbers
represent a complete set of residues modulo
. Therefore,
divides
only if
This solution is incorrect, but why??? (Answer below)
Correction to Solution
This is a common misconception: the roots of are the
th roots of unity, not
th roots of unity! Thus, replace all instances of
with
in the above solution to produce a final answer of
, and the solution should obtain full credit....
Actually, there is one more thing missing. We proved that if , then
is divisible by
But we have not proved that if
is not one, then
is not divisible by
. But this problem is easily remedied, for we can show that
because of the properties of gcd, and thus the terms do not all represent a different mth root of unity.
Solution 2
We could instead consider modulo
. Notice that
, and thus we can reduce the exponents of
in a similar way to the first solution. We want the resulting
with degree less than
to be equal to
(of degree
), which implies that the exponents of
must be all different modulo
. This can only occur if and only if
, and this is our answer, as shown in Solution 1.
See Also
1977 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.