# Prove that $x^4+x^3+x^2+x+1 \mid x^{4n}+x^{3n}+x^{2n}+x^n+1$

Problem: Prove that $x^4+x^3+x^2+x+1$ divides $x^{4n}+x^{3n}+x^{2n}+x^n+1$ for all positive $n$ that are not multiples of $5$.

I’d like to get some pointers about how to solve this. No full solutions, just a nudge in the right direction. I’ve been working on this for a bit now and I’m not getting anywhere. Thanks.

#### Solutions Collecting From Web of "Prove that $x^4+x^3+x^2+x+1 \mid x^{4n}+x^{3n}+x^{2n}+x^n+1$"

$$X^4+X^3+X^2+X+1=\frac{X^5-1}{X-1}$$
$$X^{4n}+X^{3n}+X^{2n}+X^n+1=\frac{X^{5n}-1}{X^n-1}$$

Now, use the fact that $X^5-1|X^{5n}-1$ and that for $n$ not divisible by $5$ we have

$$gcd(X^5-1,X^n-1)=X^{gcd(5,n)}-1=X-1$$

Alternately

If $1,\omega_1, \omega_2, \omega_3, \omega_4$ are the fifth roots of unity, prove that

$$P(\omega_1)=P(\omega_2)=P(\omega_3)=P(\omega_4)=0$$
where $P(X)=X^{4n}+X^{3n}+X^{2n}+X^n+1$. Then, $P(X)$ must be divisible by $(X-\omega_1)(X-\omega_2)(X-\omega_3)(X-\omega_4)$.