Intereting Posts

On how to solve the ODE $v'-\frac{1}{v}=x$…
Finite abelian groups – direct sum of cyclic subgroup
If a function is measurable with respect to the completion then it is equal to some measurable (with respect to the measure space) function a.e.
Numbers as sum of distinct squares
Difference between the formula of Roger Cotes and Euler
Prove that matrix is symmetric and positive definite given the fact that $A+iB$ is.
Inverse of a block matrix
Number of non zero integer values of $k$ for which the points ($k,k^2)$ lies inside the triangle formed by the given three lines
Sheaf of germs of regular functions on an affine variety
Is $\int_a^b f(x) dx = \int_{f(a)}^{f(b)} f^{-1}(x) dx$?
Representation of Cyclic Group over Finite Field
Is $(\mathbb{Q},+)$ the direct product of two non-trivial subgroups?
importance of implication vs its tautology
An obvious pattern to $i\uparrow\uparrow n$ that is eluding us all?
How to move from a right semigroup action to a left semigroup action?

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

- How to show that a prime degree separable field extension containing a nontrivial conjugate of a primitive element is Galois and cyclic
- Why isn't the inverse of the function $x\mapsto x+\sin(x)$ expressible in terms of “the functions one finds on a calculator”?
- Galois representations and normal bases
- Prove that $\operatorname{Gal}(\mathbb{Q}(\sqrt{2}, i)/\mathbb{Q}(\sqrt{-2})) \cong Q_8$
- Galois field extension and number of intermediate fields
- Inverse function of $y=\frac{\ln(x+1)}{\ln x}$

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

- Congruent Polynomials
- Congruence properties of $x_1^6+x_2^6+x_3^6+x_4^6+x_5^6 = z^6$?
- The number of grid points near a circle.
- Proving a palindromic integer with an even number of digits is divisible by 11
- Is this reflexive?
- Limit for entropy of prime powers defined by multiplicative arithmetic function
- Which $p$-adic fields contain these numbers?
- If $n = a^2 + b^2 + c^2$ for positive integers $a$, $b$,$c$, show that there exist positive integers $x$, $y$, $z$ such that $n^2 = x^2 + y^2 + z^2$.
- Algorithm to find solutions $(p,x,y)$ for the equation $p=x^2 + ny^2$.
- Valuations, Isomorphism, Local ring

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.

- You are standing at the origin of an “infinite forest” holding an “infinite bb-gun”
- Differential equation of all non horizontal lines?
- A derivation of the Euler-Maclaurin formula?
- Prove that a set of nine consecutive integers cannot be partitioned into two subsets with same product
- Is the $\sum\sin(n)/n$ convergent or divergent?
- Free idempotent semigroup with 3 generators
- Find the form of a second linear independent solution when the two roots of indicial equation are different by a integer
- Is Serge Lang's Algebra still worth reading?
- Independence of increments of some processes
- Every path has a simple “subpath”
- A convex function that is bounded on a neighborhood is Lipschitz
- Prove: $\int_0^\infty \sin (x^2) \, dx$ converges.
- Importance of the zero free region of Riemann zeta function
- Meaning of commutative diagram
- Do factorials really grow faster than exponential functions?