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

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

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

I suspect NonCommAlg will be the first to bite!

2. Originally Posted by Bruno J.
Let $\displaystyle \Phi_n(x)$ be the $\displaystyle n$th cyclotomic polynomial. Show that $\displaystyle r$ is a primitive root $\displaystyle \mod p$ if and only if $\displaystyle \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 $\displaystyle r$ is a primitive root modulo p, then modulo $\displaystyle p: \ r^d - 1 \neq 0,$ for any 0 < d < p - 1. therefore modulo $\displaystyle p: \ \Phi_d(r) \neq 0$ because $\displaystyle \Phi_d(r) \mid r^d - 1.$

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

conversely, suppose $\displaystyle \Phi_{p-1}(r) \equiv 0 \mod p$ and $\displaystyle r^d - 1 \equiv 0 \mod p,$ for some $\displaystyle d < p-1, \ d \mid p-1.$ then in $\displaystyle (\mathbb{Z}/p)[x]$ we'll have $\displaystyle x-r \mid \Phi_d(x), \ x-r \mid \Phi_{p-1}(x).$ thus $\displaystyle x^{p-1} - 1=(x-r)^2f(x),$

for some $\displaystyle f(x) \in (\mathbb{Z}/p)[x].$ then taking (formal) derivative we'll get $\displaystyle (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!