Basic question on primitive roots From Ireland and Rosen's A Classical Introduction to Modern Number Theory, p.48:

Let $p$ be a prime of the form $4t+1$. Show that $a$ is a primitive root $\bmod p$ iff $-a$ is a primitive root $\bmod p$.

I can write (letting $p=4t+1$) 
$$\begin{align} 
a^{p-1} &\equiv 1 \bmod p\quad\quad \text{ because }a\text{ is a primitive root}\\

a^{4t} &\equiv 1 \bmod 4t+1\\

a^{4t} -1 &\equiv 0 \bmod 4t+1
\end{align}$$
I notice that $-a$ satisfies this last equation, but I don't feel comfortable with this because I don't think this is enough to prove that $-a$ is in fact a primitive root.
 A: Let $g$ be a primitive root of $p$. Then $(g^{2k})^2 \equiv 1 \pmod{p}$ by Fermat's Theorem,  but $g^{2k}\not\equiv 1 \pmod p$, so $g^{2k}\equiv -1\pmod p$.
It follows that $(-g)^{2k+1}\equiv g \pmod p$. Thus any power of $g$ is congruent to a power of $-g$.  It follows that $-g$ is a primitive root of $p$.
Remark: Let $p$ be an odd prime. Recall that $p^e$ and $2p^e$ have primitive roots. If $e \ge 1$ and $p$ is of the form $4k+1$, and $g$ is a primitive root of $p^e$, then $-g$ is a primitive root of $p^e$. The analogous result holds for $2p^e$.
The proof is the same as for the case $e=1$.  For $\varphi(p^e)=(p-1)p^{e-1}=4kp^{e-1}$. We conclude as above that $g^{2kp^{e-1}}\equiv -1 \pmod{p^e}$, and therefore $(-g)^{2kp^{e-1}+1}\equiv g \pmod{p^e}$.  For $2p^e$,  use the fact that $\varphi(2p^e)=\varphi(p^e)$.
A: An integer $a$ is a primitive root modulo $p$ if the smallest positive integer $k$ such that
$$a^k\equiv 1\bmod p$$
is $k=p-1$, or equivalently, if 
$$a^n\equiv 1\bmod p\implies (p-1)\mid n.$$ Suppose that $a$ is a primitive root. Then if $m$ satisfies
$$(-a)^m\equiv 1\bmod p,$$
we want to show that $(p-1)\mid m$. We see that
$$(-a)^m\equiv (-1)^ma^m\equiv 1\bmod p.$$
If $m$ is even, then
$$(-a)^m\equiv (-1)^ma^m\equiv a^m\equiv  1\bmod p$$
and we would have to have $(p-1)\mid m$ by the assumption that $a$ is a primitive root. 
If $m$ were odd, then 
$$a^m\equiv -1\bmod p,$$
and therefore
$$a^{2m}\equiv 1\bmod p,$$
so $p-1$ divides $2m$. But if $p$ is a prime of the form $4t+1$, then this is impossible (do you see why?)
To finish, note that the statement is symmetric in $a$ and $-a$. 
A: Let $a$ be a primitive root modulo $p$. That means that $a^{p-1}\equiv 1\pmod{p}$, but $a^k\not\equiv 1\pmod{p}$ for any $k$, $1\leq k\lt p-1$.
In particular, if $p$ is odd, $a^{(p-1)/2}$ makes sense and is not congruent to $1$ modulo $p$. But since $(a^{(p-1)/2})^2 = a^{p-1}\equiv 1\pmod{p}$, then $a^{(p-1)/2}$ is a solution to $x^2\equiv 1\pmod{p}$. There are only two solutions: $1$ and $-1$ (since $x^2\equiv 1\pmod{p}$ if and only if $x^2-1\equiv 0\pmod{p}$, if and only if $(x-1)(x+1)\equiv 0\pmod{p}$). We know it's not $1$, so $a^{(p-1)/2}\equiv -1\pmod{p}$.
Therefore, 
$$-a= (-1)a \equiv a^{(p-1)/2}a = a^{(p+1)/2}\pmod{p}.$$
Now... given that the order of $a$ is $p-1$, what is the order of $a^{(p+1)/2}$? If you do this carefully, you'll find that if $p\equiv 1\pmod{4}$ then the order must be the same as the order of $a$; and that if $p\equiv 3\pmod{4}$ then the order must be strictly smaller than the order of $a$. So in fact, you can use this argument to prove that the condition $p\equiv 1\pmod{3}$ is both sufficient and necessary for the equivalence (for odd primes; it is trivial when $p=2$).
