1
$\begingroup$

Let $p$ be a prime such that $q=\frac{1}{2}(p-1)$ is also prime. Suppose that $g$ is an integer satisfying $$g\not\equiv \pm 1 \mod p \text{ and } g^q \not\equiv 1 \mod p$$ Prove that $g$ is a primitive root modulo $p$.

Well $q=\frac{1}{2}(p-1) \iff 2q=p-1=\phi(p)$. So $g^{2q}=g^{\phi(p)} \mod p$.

Where do I go from here?

$\endgroup$
2
$\begingroup$

By Fermat's Little Theorem, $g^{2q} \equiv g^{\phi(p)}\equiv 1\mod{p}$. Since $q$ is prime, the order of $g$ in $(\mathbb{Z}/p)^\times$ is either $1$, $2$, $q$, or $2q$. The first three of these are ruled out by the given conditions, so that $g$ generates $(\mathbb{Z}/p)^\times$ and therefore is a primitive root modulo $p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.