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

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

Printable View

- Mar 22nd 2010, 03:00 PMvinnie100primitive 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 PMchiph588@
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 AMvinnie100
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!