# Proving that cyclotomic polynomials have integer coefficients

I don't understand why Gauss's lemma is invoked in the proof in Dummit and Foote that $\Phi_n(x)$ (the $n$th cyclotomic polynomial) belongs to $\mathbb{Z}[x]$. I'm an analyst and I wanted to remind myself about cyclotomic polynomials. The following is the proof as I've written it, and because it's been a while since I've done algebra I want to know if there is something I'm taking for granted.

It is a fact that if $R$ is a unital commutative ring, $f \in R[x]$ is a monic polynomial and $g \in R[x]$ is a polynomial, then there are $q,r \in R[x]$ with $g = qf+r$, $r=0$ or $\deg r < \deg f$.

First, $\Phi_1(x)=x-1 \in \mathbb{Z}[x]$. For $n>1$, assume that $\Phi_d(x) \in \mathbb{Z}[x]$ for $1 \leq d < n$. Then let $f = \prod_{d \mid n, d<n} \Phi_d$, which by hypothesis belongs to $\mathbb{Z}[x]$; and since each $\Phi_d$ is monic, so is $f$.

On the one hand, since $g(x)=x^n-1 \in \mathbb{Z}[x]$, there are $q,r \in \mathbb{Z}[x]$ with $g = q f + r$ and $r=0$ or $\deg r < \deg f$. On the other hand, using $x^n-1= \prod_{d \mid n} \Phi_d(x)$ we have $g = \Phi_n f \in \mathbb{C}[x]$.

Thus $\Phi_n f = qf+r \in \mathbb{C}[x]$, so $r = f \cdot (\Phi_n - q) \in \mathbb{C}[x]$. If $\Phi_n \neq q$ then $\deg r = \deg f + \deg (\Phi_n-q) \geq \deg f$, contradicting that $r=0$ or $\deg r < \deg f$. Therefore $\Phi_n = q \in \mathbb{C}[x]$, and because $q \in \mathbb{Z}[x]$ this means that $\Phi_n \in \mathbb{Z}[x]$.

I don't see any tacit assumptions, like for example degree meaning two different things in $\mathbb{C}[x]$ and $\mathbb{Z}[x]$, but if I'm not assuming anything then I don't see why Gauss's lemma is being used in the proofs I've come across.

This proof seems to be more elementary. We begin by contending that if $$(x^n -1) =({\sum}^p_{i=1}{a_i{x^i}})({\sum}^q_{j=1}{b_j{x^i}}),$$ where $${\sum}^p_{i=1}{a_i{x^i}}\in{\bf{Z}[x]},$$ then every coefficient $$b_j$$, must be an integer. To prove this, we argue by backward induction. Since $$a_p{b_q} = 1,$$ and since $$a_p\in{\bf Z},$$ we conclude that $$a_p=b_q = \pm{1}$$ and $$b_q$$ is therefore an integer. Now, assume as our induction hypothesis, that $$b_q,b_{q-1},\cdots b_{r+1}$$ are all integers. Then, the coefficient of $$x^{p+r}$$ is $${a_p}{b_r}+{a_{p-1}}{b_{r+1}}+\cdots +{a_{(p+r)-q}}{b_q}=0.$$ Since $${a_p}=\pm1$$, the above identity shows that $${b_r} = \pm({a_{p-1}}{b_{r+1}}+\cdots +{a_{(p+r)-q}}{b_q})\in{\bf{Z}}.$$ Thus, we conclude that every coefficient $$b_j$$, must be an integer by mathematical induction. Now, we use the identity $$(x^n - 1) = {\prod}_{d|n}{\Phi}_d(x).$$ We claim that $$\Phi_n(x)\in{\bf{Z}}[x]$$ by induction on $$n$$. The assertion is clear for $$n=1$$ since $$\Phi_1(x)=(x-1).$$ Assume now, as our induction hypothesis, that $$\Phi_d(x)\in{\bf{Z}}[x]$$ for all positive integers $$d. Then, writing $$(x^n - 1) = {{\prod}_{d|n,d since $${{\prod}_{d|n,d, it follows by our argument above that $${\Phi_n(x)}\in {\bf{Z}}[x].$$

Here are some remarks :

• For those who haven't Dummit and Foote (lemma 40, Sec. 13.6 in the third edition), let me recall that they define $\Phi_n(X)$ as the product of the $X-\zeta$ with $\zeta \in \mu_n$ going through the primitive $n$-th roots of unity.

• In their proof, they say : $f$ divides $X^n-1$ in $\Bbb Q(\zeta_n)[X]$ and also in $\Bbb Q[X]$ by the division algorithm. Then, $X^n-1=f(X)\Phi_n(X)$ in $\Bbb Q[X]$ and thanks to Gauss' lemma ($f$ being monic in $\Bbb Z[X]$), one has $f \in \Bbb Z[X]$ and $\Phi_n \in \Bbb Z[X]$. In this version, they need to use Gauss' lemma.

• But I think your version is also right. Actually, since $f$ is assumed to be a monic polynomial in $\Bbb Z[X]$, the division algorithm allows us to write $X^n-1 = q(X)f(X)+r(X)$ in $\Bbb Z[X]$ as you did. In particular, you don't need to use Gauss' lemma here. Then the conclusion follows by your argument, which seems correct to me.

• Sometimes, the $n$-th cyclotomic polynomial is defined as the minimal polynomial of $\zeta_n$ over $\mathbb Q$. Then $\Phi_n$ divides $X^n-1$ in $\mathbb Q[X]$, since it is a minimal polynomial. By Gauss' lemma, we get : $\Phi_n$ divides $X^n-1$ in $\mathbb Z[X]$, in particular $\Phi_n \in \Bbb Z[X]$.

• Proofs, especially somewhat simple ones like this, can become traditional and possibly the appeal to Gauss's lemma is like inactivated DNA in humans. Thanks for looking at my argument. I'd be glad to hear if there is anything I'm sweeping under the carpet. For example, when Dummit and Foote talk about factoring in $\mathbb{Q}(\zeta_n)[x]$ rather than in $\mathbb{C}[x]$ I imagined there was a structural reason, but it seems like they were just using the smallest field that a priori works. Feb 4, 2016 at 18:33
• @Jordan : I think that, as you mentionned, they talk about $\Bbb Q(\zeta_n)[X]$ because it is the smallest polynomial ring that works. More precisely $\Phi_d(X) \in \Bbb Q(\zeta_n)[X]$ if $d \mid n$, so it is somehow also "natural" to choose $\Bbb Q(\zeta_n)$ rather that $\Bbb C$. Feb 4, 2016 at 18:42

I am adding this because it is a proof using induction.

Induction Hypothesis:

Let $$\Phi_{k}(x)$$ be monic and have integral co-efficients for $$1 \leq k \leq n$$.

This is true for n = 1.

Proving that it is true for $$n+1$$,

$$x^{n+1}-1 = \Pi_{d|n+1}^{n+1}\Phi_d(x)$$

$$\frac{x^{n+1}-1}{\Pi_{d|n+1,d \neq n+1}\Phi_d(x)} = \Phi_{n+1}(x)$$

We are done.

All $$\Phi_d(x)$$ are integral and monic and they will divide $$x^{n+1}-1$$ (factors) and monic divided by another monic polynomial will give another monic polynomial. (as monics are primitve polynomials.)

• This is not a proof. At best you've proved $\Phi_{n+1}(x)$ is monic in $\mathbb{Q}[x]$. You need Gauss's Lemma to get that it lies in $\mathbb{Z}[x]$ (or one of the other arguments discussed in the solutions above. Feb 10 at 9:48
• But wouldn't it be correct if both are integral and monic Feb 10 at 9:57
• It needs proof! That's what Gauss's Lemma is for. Bare assertion is not enough. Feb 10 at 10:00
• thanks I will edit this in short time Feb 10 at 10:03