PlanetMath: factors of $n$ and $x^n-1$

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

factors of $n$

and

(Theorem)

Let be a positive integer. Then the binomial $x^n\!-\!1$ has as many prime factors with integer coefficients as the integer has positive divisors, both numbers thus being $\tau(n)$ .

Proof. If $\Phi_d(x)$ generally means the th cyclotomic polynomial

$\displaystyle \Phi_d(x) := (x-\zeta_1)(x-\zeta_2)\ldots(x-\zeta_{\varphi(d)}),$

where the $\zeta_j$ s are the primitive

th roots of unity, then the equation

$\displaystyle \prod_{d\vert n,\,\,d>0}\!\Phi_d(x) = x^n\!-\!1$

is true, because each

th root of unity is also a primitive

th root of unity for one and only one positive divisor of

. The cyclotomic factor polynomials $\Phi_d(x)$ have integer coefficients and are irreducible. Thus the number of them is same as the number $\tau(n)$ of positive divisors of

For illustrating the proof, let (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.

"factors of $n$

and

" is owned by pahio.

(view preamble)

See Also: prime factors of $x^n-1$

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: roots, polynomials, factor, equation, roots of unity, primitive, cyclotomic polynomial, numbers, divisors, coefficients, binomial, integer, positive
There is 1 reference to this entry.

This is version 4 of factors of $n$

and

, born on 2007-01-16, modified 2007-08-19.
Object id is 8776, canonical name is FactorsOfNAndXn1.
Accessed 794 times total.

Classification:

AMS MSC:	11C08 (Number theory :: Polynomials and matrices :: Polynomials)
	11R18 (Number theory :: Algebraic number theory: global fields :: Cyclotomic extensions)
	11R60 (Number theory :: Algebraic number theory: global fields :: Cyclotomic function fields )

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact