Let p be a prime such that $q = \frac{p − 1}{2}$ is also prime. Suppose that g is an integer satisfying
$g \not\equiv \pm 1 \pmod p$ and $g^q \not\equiv 1 \pmod p$.
Prove that g is a primitive root modulo p.
Asked
Active
Viewed 754 times
2
-
2If $g^q\not\equiv1~(p)$ then the order of $g$ does not divide $q$. But the order of every unit mod $p$ divides $\phi(p)=p-1=2q$. So $g$'s order divides $2q$ but not $q$... – anon Sep 16 '13 at 02:27
-
This appears to be Q1.33 from p.54 of An Introduction to Mathematical Cryptography, by J.H. Silverman, Jill Pipher and Jeffrey Hoffstein. – Roger Marlow Dec 01 '21 at 10:51
1 Answers
4
Hint: The order of $g$ divides $p-1$. But since $(p-1)/2$ is prime, $p-1$ has very few divisors! And we are told that $g^q\not\equiv 1\pmod{p}$, which rules out one of them as the order of $g$. You can decide why $2$ and $1$ are ruled out.
André Nicolas
- 507,029