Show that ifpis a prime andp=2q+1, whereqis an odd prime andais a positive integer with 1 < a < p-1, then p-$\displaystyle a^2 $is a primitive root modulop.

Printable View

- Nov 3rd 2010, 09:27 PMJanu42Primitive Root Question
Show that if

*p*is a prime and*p=2q+1*, where*q*is an odd prime and*a*is a positive integer with 1 < a < p-1, then p-$\displaystyle a^2 $is a primitive root modulo*p*. - Nov 11th 2010, 11:17 AMPaulRS
Note that $\displaystyle p \equiv 3 (\bmod. 4)$ what does this tell you about $\displaystyle -1$ ? and about $\displaystyle p-a^2$ ?

Next, prove that all non-quadratic residues module p (except for -1) must be primitive roots module $\displaystyle p$.

Hint : Count

Link the two parts.