Factoring $x^n - 1$ systematically? The polynomial $x^n-1$ is interesting in for example many signal processing applications.
It is easy to find special cases for factorizations, for example the famous conjugate rule:$$x^2-1 = (x+1)(x-1)$$
We can extend this to find another factorization for general n:
$$x^n-1 = (x^{n-1}+\cdots+x+1)(x-1)$$
Except for these quite trivial special cases, can we somehow systematically find more factorizations?
 A: What you probably want are the cyclotomic polynomials. This is basically a list of the possible factors of $x^n-1$, organized in a nice fashion.
For each $n\in \Bbb N$, there is a cyclotomic polynomial $\varphi_n(x)$. It is defined as the single factor of $x^n-1$ (over the integers) which isn't a factor of $x^k-1$ for $k<n$. The start of the list of cyclotomic polynomials is
$$
\begin{array}{|c|c|}
\hline
n & \varphi_n(x)\\
\hline
1& x-1\\
2&x+1\\
3&x^2+x+1\\
4 & x^2+1\\
5&x^4+x^3+x^2+1\\
6&x^2-x+1\\
\vdots&\vdots
\end{array}
$$
Now, the neat thing is that
$$
x^n-1 = \prod_{d\mid n} \varphi_d(x)
$$
For instance, we have
$$
x^6-1 = \varphi_1(x)\cdot \varphi_2(x)\cdot\varphi_3(x)\cdot \varphi_6(x)
$$
as $1, 2, 3$ and $6$ are the divisors of $6$. This can actually be used to build the list one element at a time: for any given $n$, assuming you know all cyclotomic polynomials above it, there is only one unknown here, and it can be found through polynomial division. If you don't want to get into complex numbers, this is probably the most straight-forward way of calculating them (might not be the fastest way, though).
For prime $n$, we always have
$$
\varphi_n(x) = x^{n-1} + x^{n-2} + \cdots + x + 1
$$
as $x^n-1$ cannot be factored further than what you show in your example, but in other cases, interesting things can happen. For instance, for any $n$, $\varphi_{n^2}(x) = \varphi_n(x^n)$, and if $n>1$ is odd we have $\varphi_{2n}(x) = \varphi_n(-x)$ and $\varphi_{4n} = \varphi_n(-x^2)$.
The degree of $\varphi_n(x)$ is $\phi(n)$, where $\phi$ is Euler's Totient function. There are a lot of other properties too, but I won't copy all of the Wikipedia article in here.
Finally, they illustrate nicely the so-called strong law of small numbers (this is example 27 in that article). If you continue this list by hand, it might be tempting after a while to believe that the coefficients are always $\pm 1$. However, $\varphi_{105}(x)$ has two $2$'s in it, and in fact, the coefficients of $\varphi_{n}(x)$ can be arbitrarily large, although that requires $n$ to have many distinct odd prime factors ($105 = 3\cdot 5\cdot 7$).
