Cyclotomic Polynomial has Integer Coefficients

From ProofWiki
Jump to navigation Jump to search


Let $n \in \Z_{>0}$ be a positive integer.

Then the $n$th cyclotomic polynomial $\map {\Phi_n} x$ has integer coefficients.


The proof proceeds by strong induction on $n$.

For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:

$\map {\Phi_n} x$ has integer coefficients

Basis for the Induction

By First Cyclotomic Polynomial:

$\map {\Phi_1} x = x - 1$

Thus $\map P 1$ is seen to hold.

This is the basis for the induction.

Induction Hypothesis

Now it needs to be shown that if $\map P j$ is true, for all $j$ such that $0 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.

This is the induction hypothesis:

For all $j$ such that $0 \le j \le k$, $\map {\Phi_j} x$ has integer coefficients

from which it is to be shown that:

$\map {\Phi_{k + 1} } x$ has integer coefficients

Induction Step

This is the induction step:

Suppose $\map P j$ holds for all $j \le k$.

From Product of Cyclotomic Polynomials:

$\displaystyle \prod_{d \mathop \divides {k + 1} } \map {\Phi_d} x = x^k - 1$

By the induction hypothesis:

$\displaystyle \prod_{\substack {d \mathop \divides k \\ d \mathop \ne k}} \map {\Phi_d} x$

is a monic polynomial with integer coefficients, and thus primitive.

From Content of Polynomial is Multiplicative it follows that $\map {\Phi_{k + 1} } x$ has integer coefficients.