1977 USAMO Problems/Problem 1

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).

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 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$

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

1977 USAMO Problems/Problem 1

Problem

Solution

See Also