# Primitive Root Modulo $p=4q+1$

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.

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.
• I didn't notice that. That observation would shorten the proof significantly. I guess it should have become evident when I was almost rewriting the case for $q$ in the case of $2q$. Thanks for the observation! – Mb123 Dec 19 '15 at 18:22
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$.