# 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.

-

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

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

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.

-
@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