Prove that the factorization of $x^n-1$ contains only 2 factors if and only if $n$ is prime

Question

I would like to prove the following statement.

If $n$ is a prime number, then the factorization of $x^n-1$ over $\Bbb{Z}$ contains only $2$ factors, and those factors are: $$x^n-1=(x-1)(x^{n-1}+x^{n-2}+\cdots+x+1).$$

I have already proved that the factorization above is valid for all $n\in\Bbb{N}$, what's left to prove is that if $n$ is a prime number, then $(x^{n-1}+x^{n-2}+\cdots+x+1)$ is irreducible. I know the Eisenstein's criterion could be used, but I have no clue how the proof can be developed. Help!

PS: If it helps with anything, I have also proved the inverse. That is, if $n$ is a compound number, then the factorization $x^n-1$ contains more than 2 factores (which I don't think it helps at all).

Answer 1

The $n$th roots of unity are any numbers $c$ such that $c^n=1$ (these include complex numbers). A primitive $n$th root of unity is any number $c$ such that $c^n=1$ and $n$ is the smallest integer $k$ such that $c^k=1$. Reading from here, there are exactly $ϕn$ primitive $n$th roots of unity for all $n$. This follows from the fact that if $d|n$, then $x^d-1 | x^n-1$ and any $d$th root of unity is also an $n$th root of unity, so then in order to be a primitive $n$th root of unity, $d$ must be relatively prime to $n$, therefore there are $ϕn$ roots of unity. If $n$ is prime, then $1$ is the only non primitive $n$th root of unity, and the rest are primitive root of unity. Since the number of $n$th primitive roots of unity is $ϕn$ and $n$ is prime, there are $n-1$ primitive $n$th roots of unity. There must be an irreducible polynomial, also known as the $n$th cyclotomic polynomial, which contains all primitive $n$th roots of unity. In turn from the information above, the $n$th cyclotomic polynomial has degree $ϕn$, but since $n$ is prime, the $n$th cyclotomic polynomial is of degree $n-1$, and $(x^n-1)/(x-1)$ is indeed the $n$th cyclotomic polynomial and $x^n-1$ will only have two polynomial factors. If $n$ is composite, then $ϕn$ < $n-1$ and the $n$th cyclotomic polynomial is not of degree $n-1$, therefore $(x^n-1)/(x-1)$ is not irreducible and $x^n-1$ contains at least $3$ polynomial factors.

Answer 2

We have $$ x^{n}-1= \prod _{d\mid n}\Phi _{d}(x) $$ where $\Phi _{d}(x)$ is the $d$-th cyclotomic polynomial. When $p$ is prime, we have $$ \Phi_p(x) = x^{p-1} + x^{p-2} + \cdots + x + 1 $$ whose irreducibility follows from Eisenstein's criterion applied to $\Phi_p(x+1)$.

Answer 3

The polynomial $x^n-1$ contains as many algebraic factors, as $n$ contains divisors. Each of these algebraic factors contain a first term $x^a$, where $a$ is the Euler totative of the divisor.

These equations can be demonstrated and evaluated from the decimal. This works at least for all values where the euler totative is less than 163 (that's as far as i went)

You start off with the numbers 9, 99, 999, &c.

a   b            c         d        e
1 9               9     555564    x-1
2 99             11     555566    x+1
3 999           111     555666    x2+x+1
4 9999          101     555656    x2+1
5 99999       11111     566666    x4+x3+x2+x+1
6 999999         91     555646    x2-x+1

b is simply $10^a-1$. c is the residue, when b is divided by previously evaluated c, if the index a divides the current a.

d is c, added by a number 555555. Normally the number of 5's is larger than the largest value. When 5 is subtracted from each digit, it gives the numerator for each power of x. This is the equation in e.

A program language like REXX is sufficient for this end.

To these one needs to note that the gaussian factorisation holds for particular multiples (odd number by some x), such as $x^4+x^3+x^2+x+1=x^2+3x+1\pm \sqrt{5x}(x+1)$.