# Thread: primitive root modulo p

1. ## primitive root modulo p

Suppose p, q are primes with p = 2q + 1.

Under what conditions on q is 5 a primitive root modulo p?

2. Originally Posted by vinnie100
Suppose p, q are primes with p = 2q + 1.

Under what conditions on q is 5 a primitive root modulo p?
First observe $\displaystyle 5^{\frac{p-1}{2}}\equiv\pm1\mod{p}$.

In this case, $\displaystyle 5$ is a primitive root modulo $\displaystyle p \iff 5^{\frac{p-1}{2}}\equiv -1 \mod{p}$ (Ask if you'd like to see why.)

Note $\displaystyle \frac{p-1}{2} = q$

By Euler's Criterion, $\displaystyle 5^q\equiv -1\mod{p}\iff\left(\frac{5}{p}\right)=-1 \iff p\equiv 2 \text{ or } 3\mod{5}$

$\displaystyle p=5k+2=2q+1\iff 2q=5k+1\iff 2q\equiv1\mod{5}\iff q\equiv 3 \mod{5}$
$\displaystyle p=5k+3=2q+1\iff 2q=5k+2\iff 2q\equiv2\mod{5}\iff q\equiv 1 \mod{5}$

So $\displaystyle 5$ is a primitive root modulo $\displaystyle p \iff q\equiv 1\text{ or }3 \mod{5}$.

3. Thanks very much! It makes perfect sense. I could not progress before since I could not see the trick of using Euler's criterion.

Thanks again!