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.

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?

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Do you have any insight on the edit? –  Dexter Nov 6 '12 at 12:03
    
@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. –  joriki Nov 6 '12 at 12:21
add comment

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

share|improve this answer
    
Do you have any insight on the edit? –  Dexter Nov 6 '12 at 12:04
add comment

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.