Take the 2-minute tour ×
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.

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|improve this question

3 Answers 3

up vote 1 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|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

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

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|improve this answer

Your Answer

 
discard

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.