Sloane's OEIS A000005 gives the number of divisors of the integer n. A comment (by a very reputable contributor) in this sequence claims that this is also the number of factors in the factorization of the polynomial $x^n-1$ over the integers. For example a(6) = 4 because there are 4 divisors of the integer 6 and (apparently) because there are 4 factors in the factorization of $x^6 - 1= (-1 + x) (1 + x) (1 - x + x^2) (1 + x + x^2)$.
Is there an easy explanation for this? How can I count the number of factors in the factorization of $x^n - 1$? Is there an algorithm to produce these factors? I read an article on-line that gave a method to produce all the factors of x^n - 1 with no rational roots ( that is 1 and -1 are not roots) but this is not the same as the irreducible factors that are being counted in this sequence.
The idea is to construct a bijection between divisors $d$ of $n$ and irreducible factors $F$ of $X^n-1$.
Given a divisor $d$, let $F$ be the $d$-th cyclotomic polynomial (the minimal polynomial of a primitive $d$-th root of unity). Then $F$ is irreducible, and $F \mid X^d - 1 \mid X^n - 1$.
Given an irreducible factor $F$ of $X^n-1$, let $d$ be minimal such that $F \mid X^d - 1$. Then $F \mid \gcd(X^d-1,X^n-1)=X^{\gcd(d,n)}-1$, which implies $d \leq \gcd(d,n)$ hence $d \mid n$.
It now remains to show that these two maps (of which we have shown that they are well-defined) are inverses of each other.