Consider a prime $p$ $\in\mathbb{N}$ of the form $4t+3$, with $t$ $\in\mathbb{N}$. Prove that a $\in\mathbb{Z}$ is a primitive root $\mod p$ if and only if $-a$ has order $\frac{(p-1)}{2}$.
I showed most of the forwards direction, i.e. that a being a primitive root $\Rightarrow$ the powers ${a^1}$, …, ${a^{\phi(p)}}$, $\phi$ being the Euler totient, are a complete set of representatives for ($\mathbb{Z}/p\mathbb{Z})^X$.
By definition the powers above are distinct, since there are $\phi(p)$ of them and |($\mathbb{Z}/p\mathbb{Z})^X$|= $\phi(p)$.
It follows that if $a$ is a primitive root $\mod p$ then ord(a)=$\phi(p)=p-1$ as $p$ is prime.
However, I don't know how to then show that if a has order $(p-1)$, then $-a$ must have order $\frac{p-1}{2}$. Intuitively it is true, and I think it has something to do with Fermat's little theorem but I am unsure.
Also no idea how to prove the reverse direction, ie that $-a$ has order $\frac{p-1}{2}$ $\Rightarrow$ $a$ is a primitive root $\bmod{p}$
I also haven't used the fact that $p\equiv 1 \bmod{4}$. Would it matter if $p\equiv 3 \bmod{4}$ ?
Best Answer
For the forward direction, note that $a^{(p-1)}$ is $1$ modulo $p$ and $a^{(p-1)/2}$ is a square root of $1$ modulo $p$. As you said, the different powers $a$, $a^2$, $a^3$, $\ldots$ $a^{p-1}$ are distinct. Thus, it must be that $a^{(p-1)/2}$ is congruent to $-1$ modulo $p$ and $a^{(p-1)/2}$ and $a^{p-1}$ are the only powers $a^k$ with $1 \leq k \leq p-1$ that are congruent to $\pm 1 \pmod{p}$. It follows that
$(-a)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \cdot (-1) \equiv (-1)^{(p+1)/2} \pmod{p}$
We now use the fact that $p \equiv 3 \pmod{4}$ to conclude that $(-a)^{(p-1)/2} \equiv 1 \pmod{p}$.
Now note that $(-a)^k$ can only be 1 modulo $p$ if $a^k \equiv \pm 1 \pmod{p}$. Thus, the only possible $k$s with $1 \leq k \leq p-1$ such that $(-a)^k \equiv 1 \pmod{p}$ are $(p-1)/2$ and $p-1$. From the above, it follows that the order of $(-a)$ modulo $p$ is $(p-1)/2$.
For the reverse direction, note that $(-a)^{(p-1)/2} \equiv 1 \pmod{p}$ implies, since $p \equiv 3 \pmod{4}$, that $a^{(p-1)/2} \equiv -1 \pmod{p}$. Thus, $a$ to a power that is an odd multiple of $(p-1)/2$ is $-1$ modulo $p$. In particular, if $a^{n(p-1)/4} \equiv 1 \pmod{p}$, then $n$ must be a multiple of $4$.
Assume the order of $a$ modulo $p$ is $k$. Then $(-a)^{2k} \equiv 1 \pmod{p}$, so $2k$ is a multiple of $(p-1)/2$, the order of $-a$ modulo $p$. Thus, $k$ is a multiple of $(p-1)/4$. The observation in the above paragraph shows then that $k$ is a multiple of $(p-1)$, so $k=p-1$ and $a$ is a primitive root modulo $p$.