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})$.
Problem
Source: 1977 USAMO Problem 1
Tags: algebra, polynomial, modular arithmetic
04.04.2010 07:12
Might be some error because it's late.
04.04.2010 21:44
The required condition is $ \gcd(m + 1,n) = 1$ The roots of the second polynomial are the $ (m + 1)^{th}$ roots of unity. If $ (m + 1,n) = 1$, then they are clearly roots of the first polynomial as well. This is because $ x^{in}$ cycles through all the $ (m + 1)^{th}$ roots of unity $ (0 \le i \le m) \implies$ we get zero when we plug in one of the $ (m + 1)^{th}$ roots of unity in the first polynomial. If $ \gcd(m + 1,n) \ne 1$, then $ (m + 1)|in$ for some $ i \le m$. This means that when we plug in an $ (m + 1)^{th}$ root of unity $ \alpha$ in the first polynomial, we get $ 1 + \alpha^n + \alpha^{2n} + \cdots + 1 + \alpha^n + \cdots$, which is not zero.
14.11.2023 06:47
Second equation is equivalent to $x^{m+1}=1,x\ne 1$ And first is $(x^n)^{m+1}=1,x^n\ne 1$ Now every root of second must be a root of first. For this to happen necessary and sufficient condition is $x^{m+1}=1\text{ and }x^n\ne 1\iff \gcd(m+1,n)=1$