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.
Best Answer
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.