# factors of $n$ and $x^{n}-1$

Let $n$ be a positive integer.  Then the binomial$x^{n}\!-\!1$  has as many prime factors (http://planetmath.org/PrimeFactorsOfXn1) with integer coefficients as the integer $n$ has positive divisors, both numbers thus being $\tau(n)$ (http://planetmath.org/TauFunction).

Proof.  If  $\Phi_{d}(x)$ generally means the $d$th cyclotomic polynomial

 $\Phi_{d}(x):=(x-\zeta_{1})(x-\zeta_{2})\ldots(x-\zeta_{\varphi(d)}),$

where the $\zeta_{j}$s are the primitive $d$th roots of unity, then the equation

 $\prod_{d|n,\,\,d>0}\!\Phi_{d}(x)=x^{n}\!-\!1$

is true, because each $n$th root of unity is also a primitive (http://planetmath.org/RootOfUnity) $d$th root of unity for one and only one positive divisor of $n$.  The cyclotomic factor polynomials $\Phi_{d}(x)$ have integer coefficients and are irreducible (http://planetmath.org/IrreduciblePolynomial2).  Thus the number of them is same as the number $\tau(n)$ of positive divisors of $n$.

For illustrating the proof, let  $n=6$ (divisors 1, 2, 3, 6); think the sixth roots of unity:  $\zeta^{0}$, $\zeta^{1}$, $\zeta^{2}$, $\zeta^{3}$, $\zeta^{4}$, $\zeta^{5}$ (where  $\zeta=e^{i\pi/3}=\frac{1+i\sqrt{3}}{2}$).  From them, $\zeta^{0}=1$  is the primitive 1st root, $\zeta^{3}$ the primitive 2nd root, $\zeta^{2}$ and $\zeta^{4}$ the primitive 3rd roots, $\zeta^{1}$ and $\zeta^{5}$ the primitive 6th roots of unity.

Title factors of $n$ and $x^{n}-1$ FactorsOfNAndXn1 2013-03-22 16:35:05 2013-03-22 16:35:05 pahio (2872) pahio (2872) 7 pahio (2872) Theorem msc 11R60 msc 11C08 msc 11R18 PrimeFactorsOfXn1