# Problems on Cyclotomic Polynomials

A complex number $z=\cos(\alpha)+i\sin(\alpha)=e^{i\alpha}$ is called an $n$th root of unity if $z^n-1=0$, and is a primitive $n$th root of unity if in addition $z^k-1\neq0$ for $1\leq k<n$. The $n$th cyclotomic polynomial, $\Phi_n(x)$, is the monic polynomial of which the zeros are the distinct primitive $n$th roots of unity. Take $n>1$.

(a) Show that $\zeta=e^{2\pi i/n}$ is a primitive $n$th root of unity.

(b) Show that $$\Phi_n(x)=\prod_{\substack{1\leq j\leq n\\ (j,n)=1}}(x-\zeta^j),$$ and that $x^n-1=\prod_{d\mid n}\Phi_d(x)$.

(c) By applying the inversion formula to $\log \Phi_n(x)$, or otherwise, show that $$\Phi_n(x)=\prod_{d\mid n}(x^{n/d}-1)^{\mu(d)}.$$ In particular, conclude that $\Phi_n\in\mathbb{Z}[x]$.

(d) Suppose that $p$ is prime, $p\nmid n$, and $\Phi_n(a)\equiv 0\pmod p$. Show that
$\qquad$ (i) $\hskip0.11in p\nmid a$;
$\qquad$ (ii) $\hskip0.07in t\mid n$, where $t=\operatorname{ord}_p a$;
$\qquad$ (iii) $\hskip0.03in$if $a^{n/d}\equiv 1\pmod p$, then $d\mid\frac{n}{t}$;
$\qquad$ (iv) $\hskip0.03in$if $p^s\| (a^t-1)$, then $p^s\|(a^{mt}-1)$ when $p\nmid m$;
$\qquad$ (v) $\hskip0.07in$if $n/t>1$, then $p\nmid \Phi_n(a)$ [use (c)];
$\qquad$ (vi) $\hskip0.03in$the congruence $\Phi_n(x)\equiv0\pmod p$ is solvable if and only if $p\equiv 1\pmod n$.

(e) Show that there are infinitely many primes $p\equiv 1\pmod n$. [Hint: Consider $\Phi_n(np_1\cdots p_ry)$, where the $p_i$ are $\equiv1\bmod n$.]

These are a bunch of exercises on cyclotomic polynomial from Fundamentals of Number theory, p. 131, William J. Leveque. I have thought really hard, but still cannot prove most of them. Could anyone talk something about them or give me some reference books on that? I am really curious about their proofs. Thanks in advance.

-
(a) Should be straight forward (they are clearly roots of unity, just check they are primitive). The first part of (b) follows by noting that if $\zeta$ is a primative $n$th root of unity, then $\zeta^m$ is a primitive $nth$ root of unity if and only if $(m,n)=1$, the second part of (b) by looking at the roots of $x^n-1$, (c) follows from (b) and the mobius inversion formula. (di) follows from (c). For (dii), note that one of the factors in (c) must be 0. (diii) follows from thinking about the cyclic group $(Z/p)^*$. Hopefully this is enough to get you started. – Aaron Nov 20 '11 at 18:47
"still cannot prove most of them" isn't really a basis for a good question here. Let's be more specific: can you do (a)? – Gerry Myerson Nov 20 '11 at 22:59
@GerryMyerson I could do everything now except (d). – Kou Nov 21 '11 at 3:29
You can't do any part of (d)? Even the parts Aaron wrote about in a comment? – Gerry Myerson Nov 21 '11 at 4:51
@GerryMyerson Yes! – Kou Nov 21 '11 at 14:24

We've established in the comments that the difficulties start with (d)(i). So: $$\Phi_n(a)=\prod_{d\mid n}(a^{n/d}-1)^{\mu(d)}$$ from (c). Since $p$ is, by hypothesis, a prime, $$\Phi_n(a)\equiv0\pmod p$$ implies at least one of the factors $a^{n/d}-1$ is zero mod $p$. But if $p$ divides $a$, then each of these factors is $-1$ mod $p$, contradiction, hence, $p$ doesn't divide $a$.
EDIT: For (d)(ii), as noted above, at least one of the factors $a^{n/d}-1$ is zero mod $p$, so, if $t$ is the order of $a$ mod $p$, then $t$ divides $n/d$ for that $d$; a fortiori, $t$ divides $n$.