## Primitive roots & cyclotomic polynomials

Posted: December 17, 2009 in Elementary Algebra; Problems & Solutions, Rings and Modules
Tags: ,

Problem. Let $\Phi_n(x)$ be the $n$th cyclotomic polynomial and $p$ a prime number. Show that $r$ is a primitive root $\mod p$ if and only if $\Phi_{p-1}(r) \equiv 0 \mod p$.

Solution. If $r$ is a primitive root modulo $p,$ then modulo $p: \ r^d - 1 \neq 0,$ for any $0 < d < p - 1.$ So modulo $p: \ \Phi_d(r) \neq 0$ because $\Phi_d(r) \mid r^d - 1.$ But we also have

$\Phi_{p-1}(r)\prod \Phi_d(r)=r^{p-1} - 1 \equiv 0 \mod p,$

where the product is over $\{d: \ \ d \mid p-1, \ d < p-1 \}.$ Therefore $\Phi_{p-1}(r) \equiv 0 \mod p.$ Conversely, suppose that $\Phi_{p-1}(r) \equiv 0 \mod p$ and $r^d - 1 \equiv 0 \mod p,$ for some $d < p-1, \ d \mid p-1.$ Then in $(\mathbb{Z}/p\mathbb{Z})[x]$ we’ll have $x-r \mid \Phi_d(x), \ x-r \mid \Phi_{p-1}(x).$ Thus $x^{p-1} - 1=(x-r)^2f(x),$ for some $f(x) \in (\mathbb{Z}/p \mathbb{Z})[x].$ Then taking (formal) derivative will give us $(p-1)r^{p-2} \equiv 0 \mod p,$ which is obviously impossible. $\Box$