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

Latest revision as of 14:58, 23 June 2022

Problem

Determine all pairs of positive integers $(m,n)$ such that $(1+x^n+x^{2n}+\cdots+x^{mn})$ is divisible by $(1+x+x^2+\cdots+x^{m})$ .

Solution 1

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 (m+1)th 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 (m+1)th root of unity not equal to 1.

Note that if $\\gcd(m+1,n)=1$ , the numbers $n, 2n, 3n, \cdots, mn$ represent a complete set of residues minus 0 modulo $m+1$ . However, if $gcd(m+1,n)=a$ not equal to 1, then $\frac{(m+1)(n)}{a}$ is congruent to $0 \pmod {m+1}$ and thus a complete set is not formed. Therefore, $f(x)$ divides $g(x)$ if and only if $\boxed{\\gcd(m+1,n)=1}.$ $\blacksquare$

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.

Solution 3

Notice that $1+x^n+x^{2n}+...+x^{mn}=\frac{x^{mn+n}-1}{x^n-1}$ and $1+x+x^2+...+x^m=\frac{x^{m+1}-1}{x-1}$ , so it remains to prove that $(x^n-1)(x^{m+1}-1) \mid (x^{mn+n}-1)(x-1)$ . It is clear that $(x^n-1) \mid (x^{mn+n}-1)$ and $(x^{m+1}-1) \mid (x^{mn+n}-1)$ . For any $k \in \mathbb{N}$ , we can use the fact that $x^k-1=\prod_{d \mid k} \Phi _d(x)$ , where $\Phi _d(x)$ is the dth cyclotomic polynomial. If $\gcd(m+1,n) = d > 1$ , then $x^{m+1}-1$ and $x^n-1$ share a common cyclotomic polynomial; namely, $\Phi _d(x)$ . But since all the factors of $x^{mn+n}-1$ are distinct, $(x^{mn+n}-1)(x-1)$ cannot be divisible by $(x^n-1)(x^{m+1}-1)$ . We find that $\gcd(m+1,n) = 1$ must be the solution, since the only shared polynomial is $\Phi _1(x)=x-1$ , and we are done.

@@ Line 1: / Line 1: @@
 == Problem ==
 Determine all pairs of positive integers <math> (m,n)</math> such that
-<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+x^n+x^{2n}+\cdots+x^{mn})</math> is divisible by <math> (1+x+x^2+\cdots+x^{m})</math>.
-== Solution ==
+== Solution 1 ==
-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 (m+1)th 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 (m+1)th root of unity not equal to 1.
-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+1,n)=1</math>, the numbers <math>n, 2n, 3n, \cdots, mn</math> represent a complete set of residues minus 0 modulo <math>m+1</math>. However, if <math>gcd(m+1,n)=a</math> not equal to 1, then <math>\frac{(m+1)(n)}{a}</math> is congruent to <math>0 \pmod {m+1}</math> and thus a complete set is not formed. Therefore, <math>f(x)</math> divides <math>g(x)</math> if and only if <math>\boxed{\\gcd(m+1,n)=1}.</math> <math>\blacksquare</math>
+==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> 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.
+==Solution 3==
+Notice that <math>1+x^n+x^{2n}+...+x^{mn}=\frac{x^{mn+n}-1}{x^n-1}</math> and <math>1+x+x^2+...+x^m=\frac{x^{m+1}-1}{x-1}</math>, so it remains to prove that <math>(x^n-1)(x^{m+1}-1) \mid (x^{mn+n}-1)(x-1)</math>. It is clear that <math>(x^n-1) \mid (x^{mn+n}-1)</math> and <math>(x^{m+1}-1) \mid (x^{mn+n}-1)</math>. For any <math>k \in \mathbb{N}</math>, we can use the fact that <math>x^k-1=\prod_{d \mid k} \Phi _d(x)</math>, where <math>\Phi _d(x)</math> is the dth cyclotomic polynomial. If <math>\gcd(m+1,n) = d > 1</math>, then <math>x^{m+1}-1</math> and <math>x^n-1</math> share a common cyclotomic polynomial; namely, <math>\Phi _d(x)</math>. But since all the factors of <math>x^{mn+n}-1</math> are distinct, <math>(x^{mn+n}-1)(x-1)</math> cannot be divisible by <math>(x^n-1)(x^{m+1}-1)</math>. We find that <math>\gcd(m+1,n) = 1</math> must be the solution, since the only shared polynomial is <math>\Phi _1(x)=x-1</math>, and we are done.
 == 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