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  ${\mathrm{\Phi }}_d(x)$ generally means the $d$th cyclotomic polynomial

$${\mathrm{\Phi }}_d(x):=(x-{\zeta }_1)(x-{\zeta }_2)\mathrm{\dots }(x-{\zeta }_{\phi (d)}),$$

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

$$\prod _{d|n,d>0}{\mathrm{\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 ${\mathrm{\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$
Canonical name	FactorsOfNAndXn1
Date of creation	2013-03-22 16:35:05
Last modified on	2013-03-22 16:35:05
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	7
Author	pahio (2872)
Entry type	Theorem
Classification	msc 11R60
Classification	msc 11C08
Classification	msc 11R18
Related topic	PrimeFactorsOfXn1