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

-
You can write $a^{p-1}\equiv 1\bmod p$ for any $a$ relatively prime to $p$ - that's Fermat's Little Theorem. The definition of being a primitive root is that $a^k\not\equiv1\bmod p$ for any $k<p-1$. –  Zev Chonoles Feb 3 '12 at 5:54
If $a$ is a primitive root, then $a^{(p-1)/2}$ is a solution to $x^2\equiv 1\pmod{p}$ that is not congruent to $1$; so it must be congruent to $-1$. Hence $-a = (-1)a = a^{(p+1)/2}$. Do you know how to compute the multiplicative order of $x^k$ if you know the multiplicative order of $x$? –  Arturo Magidin Feb 3 '12 at 6:07
–  awllower Feb 3 '12 at 9:40

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

-

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

-
Where did you use a fact that $p \equiv 1 \pmod 4$ in your proof ? –  pedja Feb 3 '12 at 8:37
@pedja: The third line... –  awllower Feb 3 '12 at 9:39
@pedja: More than once! Already in the first line, middle, when saying $(g^{2k})^2\equiv 1$. –  André Nicolas Feb 3 '12 at 13:46

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

-