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

Question

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 05 '13 at 08:12 — Maesumi, Nov 05 '13 at 08:12
@Maesumi This should be the answer. – Carsten S Nov 05 '13 at 08:29 — Carsten S, Nov 05 '13 at 08:29

score 1 · Answer 1 · answered Nov 05 '13 at 08:14

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.

score 1 · Answer 2 · answered Nov 05 '13 at 12:49

1

In your second formula you need $x^n$ in denominator.

answered Nov 05 '13 at 12:49

Maesumi

3,702

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

2 Answers2