# primitive root modulo p

• Mar 22nd 2010, 03:00 PM
vinnie100
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?
• Mar 22nd 2010, 03:40 PM
chiph588@
Quote:

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}$.
• Mar 23rd 2010, 02:42 AM
vinnie100
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!