Primitive Root Modulo $p=4q+1$

Question

Let $p$ and $q$ be primes such that $p=4q+1$. Then $2$ is a primitive root modulo $p$.

Proof.

Note that $q\not=2$ since $4\cdot2+1=9$ is not prime. $\mathrm{ord}_p(2)\vert p-1=4q$, so $\mathrm{ord}_p(2)=1,\;2,\;4,\;q,\;2q,\;\mathrm{or}\;4q$.

Clearly $\mathrm{ord}_p(2) \not= 1$, and $\mathrm{ord}_p(2)\not=2$ since $4\equiv1(\text{mod }p) \implies p=3$ but $3\not=4q+1$ for any positive integer $q$. Also $\mathrm{ord}_p(2)\not=2$ because $2^4=16\equiv1(\text{mod }p)\implies p=3 \text{ or } 5$. It has been shown that $p\not=3$ and $p=5\implies q=1$ which is not prime.

Suppose $\mathrm{ord}_p(2)=q$. Then $2^q\equiv1(\text{mod }p)$. Let $g$ be a primitive root modulo $p$, so that $2\equiv g^i(\text{mod }p)$ for some $i\in\mathbb{Z}$. Then $$g^{iq}\equiv1(\text{mod }p)\implies p-1\vert iq\implies iq=k(p-1)=4kq\implies i=4k$$ for some $k\in\mathbb{Z}$. So $2\equiv g^{4k}(\text{mod }p)$ and $2$ is a square modulo $p$, which means $p\equiv\pm1(\text{mod }8)$. Hence, either $8\vert p-1$ or $8\vert p+1$. If $8\vert p-1$, then $p-1=4q=8l\implies q=2l$ for some $l\in\mathbb{Z}$, so $q$ is even, which is impossible since $q\not=2$. If instead $8\vert p+1$, then $p+1=4q+2=8l\implies2q+1=2l$ for some $l\in\mathbb{Z}$, which is impossible. Thus $\mathrm{ord}_p(2)\not=q$.

Suppose $\mathrm{ord}_p(2)=2q$. Then $2^{2q}\equiv1(\text{mod }p)$. Let $g$ be a primitive root modulo $p$, so that $2\equiv g^i(\text{mod }p)$ for some $i\in\mathbb{Z}$. Thus $$g^{2iq}\equiv1(\text{mod }p)\implies p-1\vert 2iq\implies2iq=4kq\implies i=2k$$ for some $k\in\mathbb{Z}$, so $2$ is a square modulo $p$, which has been shown to be false. Therefore $\mathrm{ord}_p(2)\not=2q$.

Hence $\mathrm{ord}_p(2)=4q=p-1$ and 2 is a primitive root modulo $p$. $\square$

I feel confident that my proof is correct, mostly because I cannot find any obvious errors. Are there any major errors in the proof? If not, are there any details I should have included? For example, should I have specified that $1\leq i\leq p-1$, or was I okay to be lazy there? Is there anything that was unnecessary to include in the proof? Does it need to be 'cleaned up?' Thank you for your time.

Answer 1

Looks good to me. As you observed the key for ruling out the possible orders $q$ and $2q$ is that in either case $2$ would end up being a quadratic residue modulo $p$ - in violation of (an extension of) the law of quadratic reciprocity.

You can actually combine those two cases. Observe that irrespective of whether the order would be $q$ or $2q$ you get the congruence $2^{2q}\equiv1\pmod p$. After all, if $2^q\equiv1$ then also $2^{2q}\equiv1$. So it suffices to show that the congruence $2^{2q}\equiv1$ leads to a contradiction.

Answer 2

I'm not certain that this proof is actually valid. Saying that $g^{2iq} \equiv 1 \Rightarrow (p-1)|2iq$ seems to assume that $O_p(2) = p - 1$ which is what you're trying to prove. If this wasn't being implicitly assumed, there'd be no guarantee even that $(p-1) \leq 2iq$.