Show that $x^{n-1}+\cdots +x+1$ is irreducible over $\mathbb Z$ if and only if $n$ is a prime.

Solution 1:

The key is the repeated application of the geometric summation formula $$ \sum_{i=0}^{z-1} q^i = \frac{q^z - 1}{q-1}. $$

Plugging in $z=n, q=x$ and assuming $n = kl$, we get $$p(x) = x^{n-1} + x^{n-2} + \ldots + 1 = \frac{x^n - 1}{x-1} = \frac{x^{kl} - 1}{x-1}.$$

Geometric summation with $z=l$ and $q = x^k$ yields $$ \ldots = \frac{x^k - 1}{x-1} (x^{(l-1)k} + x^{(l-2)k} + \ldots + 1).$$

And finally by geometric summation with $z=k, q=x$ $$ \ldots = (x^{k-1} + x^{k-2} + \ldots + 1)(x^{(l-1)k} + x^{(l-2)k} + \ldots + 1).$$

If $k \geq 2$ and $l \geq 2$, this is a proper factorization of the polynomial $p$.

Solution 2:

If $n$ is not a prime, say $n=ab$ with $a,b>1$, then $q_a(x)=\frac{x^a-1}{x-1}$ is a divisor of $p(x)=\frac{x^n-1}{x-1}$, since every root of $q_a$ is a root of $p$, and there are no repeated roots.