2
$\begingroup$

Here $\phi(n)$ is the Euler totient function and the degree of $\Phi_{n}(x)$.

What I've done so far: Let $\phi(n) = p$ so the following products each have p components. $$\Phi_{n}(x) = \prod_{k=1, k|n}^n(x - \omega_{k}) = (x - \omega_{1})(x - \omega_{2})...(x - \omega_{p})$$ where $\omega_{k}$ is a primitive $n^{th}$ root of unity.

Then

$$\Phi_{n}(x^{-1}) = \prod_{k=1, k|n}^n(x^{-1} - \omega_{k}) = (x^{-1} - \omega_{1})(x^{-1} - \omega_{2})...(x^{-1} - \omega_{p})$$

and $x^{p} \Phi_{n}(x^{-1}) = x^p(x^{-1} - \omega_{1})(x^{-1} - \omega_{2})...(x^{-1} - \omega_{p})$.

$= x(x^{-1} - \omega_{1})x(x^{-1} - \omega_{2})...x(x^{-1} - \omega_{p})$

(Splitting the $x^p$ amongst the components of the product.)

$= (1 - x\omega_{1})(1 - x\omega_{2})...(1 - x\omega_{p})$.

So now I need to show that

$(x - \omega_{1})(x - \omega_{2})...(x - \omega_{p})= (1 - x\omega_{1})(1 - x\omega_{2})...(1 - x\omega_{p})$.

The LHS has zeros $\omega_{1}, \omega_{1}, ..., \omega_{p}$ and the RHS has zeros $\frac{1}{\omega_{1}}, \frac{1}{\omega_{2}}, ..., \frac{1}{\omega_{p}}$.

If $\omega_{i}$ is an $n^{th}$ root of unity, so is $\omega_{i}^{-1}$, so the zeros of both sides are primitive $n^{th}$ roots of unity. Moreover they have the same number of roots and hence both sides have degree p.

And then... I draw a blank. Suggestions or hints would be much appreciated!

$\endgroup$

3 Answers 3

2
$\begingroup$

Note that $$x^n-1=\prod_{d|n}\Phi_d(x),$$ hence by Möbius inversion $$\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(d)}. $$ Then the result follows because each $x^d-1$ is reciprocal and products/quotients of reciprocals are reciprocal.

$\endgroup$
3
  • $\begingroup$ I like this proof, thank you. Showing that products/quotients of reciprocals are reciprocal was actually pretty straightforward. $\endgroup$
    – Lewy
    Apr 4, 2013 at 15:40
  • 1
    $\begingroup$ @Lewy, wait, you call a polynomial $f(x)$ of degree $k$ reciprocal if $f(x)= x^k f(x^{-1})$, right? But for $f(x) = x^d - 1$ you have $x^d f(x^{-1}) = x^d (x^{-d} - 1) = 1 - x^d = - (x^d - 1) = - f(x)$. $\endgroup$ Apr 4, 2013 at 15:52
  • $\begingroup$ You are correct - that'll teach me not to pay proper attention to the simple bit! $\endgroup$
    – Lewy
    Apr 4, 2013 at 16:27
1
$\begingroup$

So you know that you are done if you can show $$ (x - \omega_{1})(x - \omega_{2})...(x - \omega_{p})= (1 - x\omega_{1})(1 - x\omega_{2})...(1 - x\omega_{p})$$

which is true if they have the same roots. The LHS has zeros $\omega_i$ and the RHS has zeros $1/\omega_i$ so to finish you have to show that that the second list is a permutation of the first list (in particular, you must show the second list consists of primitive $n$-th roots only, not any $n$-th root as you wrote above). To show this, note that the primitive $n$-th roots of unity are $\exp(2\pi i k/n)$ where $(k,n)=1$ so the inverse is $\exp(- 2\pi i k/n)= \exp(2\pi i (n-k)/n).$ Since $(k,n)=1 \implies (n-k,n)=1$ the inverse is also a primitive $n$-th root of unity.

$\endgroup$
3
  • $\begingroup$ Yes, that would be a nice finish to my proof... which now seems very longwinded compared to the answers above! $\endgroup$
    – Lewy
    Apr 4, 2013 at 15:33
  • 1
    $\begingroup$ @Lewy I've given more details to finish the proof. I actually don't think it's very long winded. $\endgroup$ Apr 4, 2013 at 15:54
  • $\begingroup$ Thank you - I've edited in primitive $n^{th}$ roots. $\endgroup$
    – Lewy
    Apr 4, 2013 at 16:33
1
$\begingroup$

If $n = 2$, then we are talking of the polynomial $x+1$.

If $n > 2$, we have that $1, -1$ are not roots of $\Phi_{n}(x)$, so every root $r$ can be paired with its inverse $r^{-1} \ne r$ to show that the constant coefficient of $\Phi_{n}(x)$, which is the leading coefficient of $x^{\phi(n)}\Phi(n)(x^{-1})$, is $1$.

Also, $x^{\phi(n)}\Phi(n)(x^{-1})$ has the same degree as $\Phi_{n}(x)$, and has the same roots, which are distinct.

It follows that $x^{\phi(n)}\Phi(n)(x^{-1}) = \Phi_{n}(x)$, as the two polynomials are monic, and have the same distinct roots.

$\endgroup$
1
  • $\begingroup$ Thank you. I knew I needed this fact (monic polynomials with identical roots are identical), but wasn't sure that it was true. $\endgroup$
    – Lewy
    Apr 4, 2013 at 17: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.