# For what $(m, n)$, does $1+x+x^2 +\dots+x^m | 1 + x^n + x^{2n}+\dots+x^{mn}$?

For what $(m, n)$, does $1+x+x^2 +\dots+x^m | 1 + x^n + x^{2n}+\dots+x^{mn}$?

Well,

$$\sum_{i = 0}^{m} x^i = \frac{x^{m+1} - 1}{x - 1}$$

and,

$$\sum_{i = 0}^m x^{in} = \frac{x^{n(m+1)} - 1}{x-1}$$

Notice that $x^{m+1} - 1|(x^{m+1})^n - 1$, therefore,

$$x^{n(m+1)} - 1 = q(x^{m+1} - 1)$$

Let

$$\frac{x^{m+1} - 1}{x - 1} = \alpha$$

Therefore,

$$\sum_{i = 0}^{m} x^i = \frac{x^{m+1} - 1}{x - 1} = \alpha$$

and,

$$\sum_{i = 0}^m x^{in} = \frac{x^{n(m+1)} - 1}{x-1} = \frac{q(x^{m+1} - 1)}{x-1} = \alpha q$$

Clearly, $\alpha|\alpha q$. Therefore, all $(m, n)$ such that $m, n \in \mathbb{N}$ should work. But the correct answer, according to the text is that $(m+1)$ and $n$ have to be relatively prime. Where did I go wrong?

• In your second formula you need $x^n$ in denominator. – Maesumi Nov 5 '13 at 8:12
• @Maesumi This should be the answer. – Carsten S Nov 5 '13 at 8:29

The number $x^{m}-1$ has a unique factor for every number $b \mid m$, say $A_b$.
The number $x^{mn}-1$ has a unique factor for every $b \mid mn$.
The proposed divisor is then the product of $A_b$, where $b\mid m$, except b=1 The proposed quotient is the product of $A_b$, where $b \mid mn$, but not $b \mid n$
So we seek values of $m$, where none of its divisors belong to $n$, and find the two to be co-prime.
In your second formula you need $x^n$ in denominator.