Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We want to prove that $$ \Phi_n(x) = \prod_{d|n} \left( x^{\frac{n}{d}} - 1 \right)^{\mu(d)} $$ where $\Phi_n(x)$ in the n-th cyclotomic polynomial and $\mu(d)$ is the Möbius function defined on the natural numbers.

We were instructed to do it by the following stages:

Using induction we assume that the formula is true for $n$ and we want to prove it for $m = n p^k$ where $p$ is a prime number such that $p\not{|}n$.

a) Prove that $$\prod_{\xi \in C_{p^k}}\xi = (-1)^{\phi(p^k)} $$ where $C_{p^k}$ is the set of all primitive $p^k$-th roots of unity, and $\phi$ is the Euler function. I proved that.

b) Using the induction hypothesis show that $$ \Phi_m(x) = (-1)^{\phi(p^k)} \prod_{d|n} \left[ \prod_{\xi \in C_{p^k}} \left( (\xi^{-1}x)^{\frac{n}{d}} - 1 \right) \right]^{\mu(d)} $$

c) Show that $$ \prod_{\xi \in C_{p^k}} \left( (\xi^{-1}x)^{\frac{n}{d}} - 1 \right) = (-1)^{\phi(p^k)} \frac{x^{\frac{m}{d}}-1}{x^{\frac{m}{pd}} - 1} $$

d) Use these results to prove the formula by substituting c) into b).

I am stuck in b) and c).

In b) I tried to use the recursion formula $$ x^m - 1 = \prod_{d|m}\Phi_d(x) $$ and $$ \Phi_m(x) = \frac{x^m-1}{ \prod_{\stackrel{d|m}{d<m}} \Phi_d(x)} . $$

In c) I tried expanding the product by Newton's binom using $\phi(p^k) = p^k ( 1 - 1/p)$. I also tried replacing the product by $\xi \mapsto [ \exp(i2\pi / p^k) ]^j$ and let $j$ run on numbers that don't divide $p^k$. In both way I got stuck.

I would appreciate help here.

share|cite|improve this question
up vote 2 down vote accepted

For b), you have to prove this by saying that $\Phi_n(x) = \prod_{\xi \in C_n} (x - \xi)$, so you have to relate $C_m$ with $C_n$ and $C_{p^k}$. Can you find a relation between $\phi(m)$, $\phi(n)$, and $\phi(p^k)$ ? If so it should give you an idea for a way to describe $C_m$ in terms of $C_n$ and $C_{p^k}$.

For c), maybe you can compute $\Phi_{p^k}$, and use that result to show that both expressions are equal to $(-1)^{\phi(p^k)} \Phi_{p^k}(x^{n/d})$

share|cite|improve this answer
Thank you very much, your clues helped me and I think I've solved the problem. – Zachi Evenor Jun 17 '12 at 19:56

I found a solution that is easy to understand for those who want to know how to solve without following the steps given in the problem. Click to see the source.

First, we have a formula $$ {x^{n}-1=\Pi_{d|n}\Phi_{d}(x)} $$ Then, by taking the logarithm on the both sides, $$ \log(x^{n}-1)=\log(\Pi_{d|n}\Phi_{d}(x))=\Sigma_{d|n}(\log\Phi_{d}(x)) $$ Now, we use the Mobius Inversion Formula by taking $f_{n}=\log\Phi_{n}$ and $F_{n}=\Sigma_{d|n}(\log\Phi_{d})$. \begin{align*} \log(\Phi_{n}(x)) & = \Sigma_{d|n}\mu(\frac{n}{d})\log(x^{d}-1)\\ & = \Sigma_{d|n}\log(x^{d}-1)^{\mu(\frac{n}{d})}\\ & = \log\Pi_{d|n}(x^{d}-1)^{\mu(\frac{n}{d})} \end{align*} Hence, we have $$ \Phi_{n}(x)=\Pi_{d|n}(x^{d}-1)^{\mu(\frac{n}{d})} $$

share|cite|improve this answer

For (b) By definition, $$\Phi_m(x)=\prod_{\xi\in C_p^k}(x-\xi)=\prod_{\xi\in C_p^k}\xi\prod_{\xi\in C_p^k}\left(\xi^{-1}x-1\right)=(-1)^{\varphi(p^k)}\prod_{\xi\in C_p^k}\left(\xi^{-1}x-1\right)$$ and now use induction and the formula $$\Phi_m(x)=(x^m-1)\prod_{d\mid m,d<m}\Phi_d(x)^{-1}$$

Added I assume you know the (additive) Moebius Inversion formula for arithmetic functions:$$f(n)=\sum_{d\mid n}F(d)\Longrightarrow F(n)=\sum_{d\mid n} \mu(d)f\left(\frac{n}{d}\right)$$

Well, we also have a multiplicative version of the above: $$f(n)=\prod_{d\mid n}F(d)\Longrightarrow F(n)=\prod_{d\mid n}f\left(\frac{n}{d}\right)^{\mu(d)}$$and the proof goes, mutatis mutandis, as the one for the additive version:$$\prod_{d\mid n}f\left(\frac{n}{d}\right)^{\mu(d)}=\prod_{d\mid n}\left(\prod_{t\mid\frac{n}{d}}F(t)\right)^{\mu(d)}=\prod_{t\mid n}F(t)^{\sum_{d\mid n, t\mid\frac{n}{d}}\mu(d)}=$$$$=\prod_{t\mid n}F(t)^{\sum_{d\mid\frac{n}{t}}\mu(d)}=F(n)$$

== The second equality above is due to the fact that $\,\displaystyle{t\frac{n}{d}\,,\,\text{when}\,\,d\mid n\Longleftrightarrow t\mid n}\,$

== The third equality follows from a similar observation: $$t\mid\frac{n}{d}\Longleftrightarrow \frac{n}{d}=kt\Longleftrightarrow \frac{n}{t}=kd\Longleftrightarrow d\mid\frac{n}{t}\,\,,\,k\in\mathbb{N}\Longleftrightarrow d\mid n$$

== Finally, the last equality follows from the basic formula $$\sum_{d\mid n}\mu(d)=\left\{\begin{array}{} 1 &\,\text{if}\,n=1\\0&\,\text{if}\,n\geq 2\end{array}\right.$$

But now the formula follows at once, since putting $\,f(k):=x^k-1\,,\,F(k):=\Phi_k(x)\,$ , we get $$ f(n)=x^n-1=\prod_{d\mid n}\Phi_d(x)=\prod_{d\mid n}F(d)\Longrightarrow$$$$\Longrightarrow \Phi_n(x)=F(n)=\prod_{d\mid n}f\left(\frac{n}{d}\right)^{\mu(d)}=\prod_{d\mid n}\left(x^{\frac{n}{d}}-1\right)^{\mu(d)} $$

I think this way is much easier that the one you were instructed to follow.

share|cite|improve this answer
@Zachi The added part is due to the fact that the first part of my answer didn't give any new ideas to what you already had (most probably I didn't read carefully enough your whole question) – DonAntonio Jun 17 '12 at 17:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.