# Proving the Möbius formula for cyclotomic polynomials

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.

#### Solutions Collecting From Web of "Proving the Möbius formula for cyclotomic polynomials"

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})$

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})}$$

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.