Difference between revisions of "1977 USAMO Problems/Problem 1"
(→Solution) |
(→Solution 2) |
||
Line 17: | Line 17: | ||
==Solution 2== | ==Solution 2== | ||
− | We could instead consider <math>f(x)</math> modulo <math>g(x)</math>. Notice that <math>x^{m+1} = 1 \pmod g(x)</math>, and thus we can reduce the exponents of <math>f(x)</math> | + | We could instead consider <math>f(x)</math> modulo <math>g(x)</math>. Notice that <math>x^{m+1} = 1 \pmod {g(x)}</math>, and thus we can reduce the exponents of <math>f(x)</math> to their equivalent modulo <math>m+1</math>. We want the resulting <math>h(x)</math> with degree less than <math>m+1</math> to be equal to <math>g(x)</math> (of degree <math>m</math>), which implies that the exponents of <math>f(x)</math> must be all different modulo <math>m+1</math>. This can only occur if and only if <math>gcd(m+1, n) = 1</math>, and this is our answer, as shown in Solution 1. |
== See Also == | == See Also == |
Revision as of 15:19, 14 August 2014
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
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.