Factorization of $x^6 - 1$ I started by intuition since I'm familiar with the formula $a^2-b^2 = (a-b)(a+b)$. So in our case $$x^6 - 1 = ({x^3} - 1)({x^3}+1)$$
How should I proceed? I assume there's some sort of algorithm to keep the process till you reach a form of irreducible linear polynomials. 

In general, we have:
$$x^n - 1 = (x-1)(x^{n-1}+x^{n-2}+\ldots+ 1).$$
It is a particular instance of: $$a^n-b^n = (a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1}).$$

Think of the geometric progression $(a_1, \ldots, a_n,\ldots)$, with common ratio $q$. Then: $$a_1+\ldots +a_n = a_1 \frac{q^n-1}{q-1}.$$
This gives: $$1+x+\ldots+x^{n-1} = \frac{x^n-1}{x-1}.$$
