Difference between revisions of "1977 USAMO Problems/Problem 1"

Revision as of 15:19, 14 August 2014

Problem

Determine all pairs of positive integers $(m,n)$ 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 $f(x)$ and the second one to be $g(x)$ . In order for $f(x)$ to be divisible by $g(x)$ they must have the same roots. The roots of $g(x)$ are the mth roots of unity, except for 1. When plugging into $f(x)$ , the root of unity is a root of $f(x)$ if and only if the terms $x^n, x^{2n}, x^{3n}, \cdots x^{mn}$ all represent a different mth root of unity.

Note that if $\\gcd(m,n)=1$ , the numbers $n, 2n, 3n, \cdots, mn$ represent a complete set of residues modulo $m$ . Therefore, $f(x)$ divides $g(x)$ only if $\boxed{\\gcd(m,n)=1}$ $\blacksquare$

This solution is incorrect, but why??? (Answer below)

Correction to Solution

This is a common misconception: the roots of $1 + x + x^2 + ... + x^m$ are the $(m+1)$ th roots of unity, not $m$ th roots of unity! Thus, replace all instances of $m$ with $m+1$ in the above solution to produce a final answer of $\boxed{\\gcd(m+1,n)=1}$ , and the solution should obtain full credit....

Actually, there is one more thing missing. We proved that if $gcd(m+1,n)=1$ , then $f(x)$ is divisible by $g(x).$ But we have not proved that if $gcd(m+1,n) = a$ is not one, then $f(x)$ is not divisible by $g(x)$ . But this problem is easily remedied, for we can show that $x^{\frac{m+1}{a} \cdot n} = 1$ 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 $f(x)$ modulo $g(x)$ . Notice that $x^{m+1} = 1 \pmod {g(x)}$ , and thus we can reduce the exponents of $f(x)$ to their equivalent modulo $m+1$ . We want the resulting $h(x)$ with degree less than $m+1$ to be equal to $g(x)$ (of degree $m$ ), which implies that the exponents of $f(x)$ must be all different modulo $m+1$ . This can only occur if and only if $gcd(m+1, n) = 1$ , and this is our answer, as shown in Solution 1.

@@ Line 17: / Line 17: @@
 ==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.
+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 ==

1977 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search