factors of and
Let be a positive integer. Then the binomial has as many prime factors (http://planetmath.org/PrimeFactorsOfXn1) with integer coefficients as the integer has positive divisors
, both numbers thus being (http://planetmath.org/TauFunction).
Proof. If generally means the th cyclotomic polynomial
where the s are the primitive th roots of unity, then the equation
is true, because each th root of unity is also a primitive (http://planetmath.org/RootOfUnity) th root of unity for one and only one positive divisor of . The cyclotomic factor polynomials have integer coefficients and are irreducible (http://planetmath.org/IrreduciblePolynomial2). Thus the number of them is same as the number of positive divisors of .
For illustrating the proof, let (divisors 1, 2, 3, 6); think the sixth roots of unity: , , , , , (where ). From them, is the primitive 1st root, the primitive 2nd root, and the primitive 3rd roots, and the primitive 6th roots of unity.