Difference between revisions of "1977 USAMO Problems/Problem 1"
(→Solution) |
|||
| Line 3: | Line 3: | ||
<math> (1\plus{}x^n\plus{}x^{2n}\plus{}\cdots\plus{}x^{mn})</math> is divisible by <math> (1\plus{}x\plus{}x^2\plus{}\cdots\plus{}x^{m})</math>. | <math> (1\plus{}x^n\plus{}x^{2n}\plus{}\cdots\plus{}x^{mn})</math> is divisible by <math> (1\plus{}x\plus{}x^2\plus{}\cdots\plus{}x^{m})</math>. | ||
| − | == Solution == | + | == (Incorrect) Solution == |
| − | Denote the first and larger polynomial to be <math>f(x)</math> and the second one to be <math>g(x)</math>. In order for <math>f(x)</math> to be divisible by <math>g(x)</math> they must have the same roots. The roots of <math>g(x)</math> are the mth roots of unity, except for 1. When plugging into <math>f(x)</math>, the root of unity is a root of <math>f(x)</math> if the terms <math>x^n, x^{2n}, x^{3n}, \cdots x^{mn}</math> all represent a different mth root of unity. | + | Denote the first and larger polynomial to be <math>f(x)</math> and the second one to be <math>g(x)</math>. In order for <math>f(x)</math> to be divisible by <math>g(x)</math> they must have the same roots. The roots of <math>g(x)</math> are the mth roots of unity, except for 1. When plugging into <math>f(x)</math>, the root of unity is a root of <math>f(x)</math> if and only if the terms <math>x^n, x^{2n}, x^{3n}, \cdots x^{mn}</math> all represent a different mth root of unity. |
Note that if <math>\\gcd(m,n)=1</math>, the numbers <math>n, 2n, 3n, \cdots, mn</math> represent a complete set of residues modulo <math>m</math>. Therefore, <math>f(x)</math> divides <math>g(x)</math> only if <math>\boxed{\\gcd(m,n)=1}</math> <math>\blacksquare</math> | Note that if <math>\\gcd(m,n)=1</math>, the numbers <math>n, 2n, 3n, \cdots, mn</math> represent a complete set of residues modulo <math>m</math>. Therefore, <math>f(x)</math> divides <math>g(x)</math> only if <math>\boxed{\\gcd(m,n)=1}</math> <math>\blacksquare</math> | ||
| + | |||
| + | '''This solution is incorrect, but why??? (Answer below)''' | ||
| + | |||
| + | == Correction to Solution == | ||
| + | This is a common misconception: the roots of <math>1 + x + x^2 + ... + x^m</math> are the <math>(m+1)</math>th roots of unity, not <math>m</math>th roots of unity! Thus, replace all instances of <math>m</math> with <math>m+1</math> in the above solution to produce a final answer of <math>\boxed{\\gcd(m+1,n)=1}</math>, and the solution should obtain full credit.... | ||
| + | |||
| + | Actually, there is one more thing missing. We proved that if <math>gcd(m+1,n)=1</math>, then <math>f(x)</math> is divisible by <math>g(x).</math> But we have not proved that if <math>gcd(m+1,n) = a</math> is not one, then <math>f(x)</math> is not divisible by <math>g(x)</math>. But this problem is easily remedied, for we can show that <math>x^{\frac{m+1}{a} \cdot n} = 1</math> 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 <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> in a similar way to the first solution. 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:17, 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 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. 
