Basic question on primitive roots

Question

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.

Answer 1

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)$.

Answer 2

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$.

Answer 3

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$).