Online Course Discussion Forum

MCIII Number Theory 5.20, 5.23, 5.27, and 5.28

 
 
Picture of Dr. Kevin Wang
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Dr. Kevin Wang - Monday, 29 January 2024, 11:35 PM
 

The first fraction is not correct.  The numerator should be $x^{n(m+1)}$ instead of $x^{nm+1}$.  There is a big difference.

This problem is question number 1 in USAMO 1977.  The solution:

Let \[ P(x) = \frac{1+x^n+x^{2n}+\cdots+ x^{mn}}{1+x+x^2 + \cdots + x^m} = \frac{(x^{(m+1)n}-1)(x-1)}{(x^n-1)(x^{m+1}-1)}. \] For all positive integers $m$ and $n$, $x^n-1$ and $x^{m+1}-1$ are both factors of $x^{(m+1)n}-1$. So as long as $x^n-1$ and $x^{m+1}-1$ do not have common factor (or common roots of unity) other than $x-1$, $P(x)$ is a polynomial with integer coefficients. On the other hand, if $x^n-1$ and $x^{m+1}-1$ have a common factor other than $x-1$, it means the equations $x^n-1=0$ and $x^{m+1}-1=0$ have common roots other than $x=1$, but the equation $x^{(m+1)n}-1=0$ has no repeated roots, so in this case $P(x)$ is not a polynomial.\\ Therefore the polynomials $x^n-1$ and $x^{m+1}-1$ do not have any common factor besides $x-1$, in other words, $\gcd(m+1, n)=1$.