factors of n and xn-1


Let n be a positive integer.  Then the binomialxn-1  has as many prime factorsMathworldPlanetmathPlanetmath (http://planetmath.org/PrimeFactorsOfXn1) with integer coefficients as the integer n has positive divisorsMathworldPlanetmathPlanetmath, both numbers thus being τ(n) (http://planetmath.org/TauFunction).

Proof.  If  Φd(x) generally means the dth cyclotomic polynomialMathworldPlanetmath

Φd(x):=(x-ζ1)(x-ζ2)(x-ζφ(d)),

where the ζjs are the primitive dth roots of unityMathworldPlanetmath, then the equation

d|n,d>0Φd(x)=xn-1

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

For illustrating the proof, let  n=6 (divisors 1, 2, 3, 6); think the sixth roots of unity:  ζ0, ζ1, ζ2, ζ3, ζ4, ζ5 (where  ζ=eiπ/3=1+i32).  From them, ζ0=1  is the primitive 1st root, ζ3 the primitive 2nd root, ζ2 and ζ4 the primitive 3rd roots, ζ1 and ζ5 the primitive 6th roots of unity.

Title factors of n and xn-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