1977 USAMO Problems/Problem 1
Contents
Problem
Determine all pairs of positive integers such that
is divisible by
.
Solution 1
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 (m+1)th 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 (m+1)th root of unity not equal to 1.
Note that if , the numbers
represent a complete set of residues minus 0 modulo
. However, if
not equal to 1, then
is congruent to
and thus a complete set is not formed. Therefore,
divides
if and only if
Solution 2
We could instead consider modulo
. Notice that
, and thus we can reduce the exponents of
to their equivalent modulo
. 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.