primitive root modulo p

**vinnie100** · March 22nd 2010, 03:00 PM

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

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

**chiph588@** · March 22nd 2010, 03:40 PM

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 $5^{\frac{p-1}{2}}\equiv\pm1\mod{p}$ .

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

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

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

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

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

**vinnie100** · March 23rd 2010, 02:42 AM

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!

Thread: primitive root modulo p

LinkBack

Thread Tools

Display

primitive root modulo p

Similar Math Help Forum Discussions

Prove if a is a primitive root mod p^2, then it is a primitive root mod p

p=2^k+1 and (a/p)=-1 imply a is primitive modulo p

Prove that 2 is a primitive root modulo p.

powers modulo p and primitive root question

Primitive root modulo 121

Search Tags