1
$\begingroup$

Claim: $$\prod_{d \mid n} \Phi_{d}(x) = x^n - 1 $$ Where $\Phi_{m}(x)$ is the $m^{th}$ cyclotomic polynomial of $x$.

I think it has to do with Euler's Totient Function $\phi$ and the result $$\sum_{d \mid n} \phi(d) = n$$ but am not sure how to show the intermediate step(s).

Edit:

Ok, I would now like to take this a little further and show, by induction on $m$ and use of the above result, that $$\Phi_m (x)\in \mathbb{Z}[x]$$ By basic computation I know it's true for $m<4$. I've considered dividing the products from the initial claim for $n=k$ and $n=k+1$. Do you have any advice?

$\endgroup$
3
$\begingroup$

The roots of $x^n-1$ are the $n$-th roots of unity, $\omega_n^k$ for $k=0,\dotsc,n-1$ with $\omega_n=\mathrm e^{2\pi\mathrm i/n}$. The roots of the cyclotomic polynomial $\Phi_d(x)$ are the primitive $d$-th roots of unity. Every $n$-th root of unity is a primitive $d$-th root of unity for exactly one divisor $d$ of $n$. The result follows.

$\endgroup$
2
  • $\begingroup$ Do you have any insight on the edit? $\endgroup$
    – Dexter
    Nov 6 '12 at 12:03
  • $\begingroup$ @Dexter: I'd divide not according to $n=k$ and $n=k+1$, but write $$ \Phi_n(x)\prod_{d|n,d\ne n}\Phi_d(x)=x^n-1 $$ and then prove by complete induction that the cyclotomic polynomials are monic (i.e. have highest coefficient $1$) and that the coefficients are integers (since the highest non-integer coefficient in $\Phi_n(x)$ would lead to a non-integer coefficient in the product, whereas the right-hand side has integer coefficients). Of course it all depends on how you define the cyclotomic polynomials. $\endgroup$
    – joriki
    Nov 6 '12 at 12:21
0
$\begingroup$

You can do this by looking at the roots of $f(x)=x^n-1$, which come out as $e^{\frac {2\pi i}{n}}$, and which (multiplicatively) form a cyclic group of order n.

The cyclotomic polynomials pick out the roots having exact order $d$ for each $d|n$ (the primitive roots mod $d$).

Each element of the group has an order which is a divisor of $n$ and is therefore captured by the relevant cyclotomic polynomial.

There are $\phi(d)$ primitive roots mod $d$, so the order of each $\Phi(d)$ is $\phi(d)$.

$\endgroup$
1
  • $\begingroup$ Do you have any insight on the edit? $\endgroup$
    – Dexter
    Nov 6 '12 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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