# Thread: Primitive roots modulo p, cyclotomic polynomials - Challenge problem!

1. ## Primitive roots modulo p, cyclotomic polynomials - Challenge problem!

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

I suspect NonCommAlg will be the first to bite!

2. Originally Posted by Bruno J.
Let $\Phi_n(x)$ be the $n$th cyclotomic polynomial. Show that $r$ is a primitive root $\mod p$ if and only if $\Phi_{p-1}(r) \equiv 0 \mod p$.

I suspect NonCommAlg will be the first to bite!
haha ... it's not really a challenge, is it? anyway, if $r$ is a primitive root modulo p, then modulo $p: \ r^d - 1 \neq 0,$ for any 0 < d < p - 1. therefore modulo $p: \ \Phi_d(r) \neq 0$ because $\Phi_d(r) \mid r^d - 1.$

but $\Phi_{p-1}(r)\prod \Phi_d(r)=r^{p-1} - 1 \equiv 0 \mod p,$ where the product is over the set $\{d: \ \ d \mid p-1, \ d < p-1 \}.$ thus $\Phi_{p-1}(r) \equiv 0 \mod p.$

conversely, suppose $\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)[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)[x].$ then taking (formal) derivative we'll get $(p-1)r^{p-2} \equiv 0 \mod p,$ which is obviously impossible.

3. Originally Posted by NonCommAlg
haha ... it's not really a challenge, is it?
For you it isn't!