7
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Zev Chonoles Feb 3 '12 at 5:54
  • 2
    $\begingroup$ 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$? $\endgroup$ – Arturo Magidin Feb 3 '12 at 6:07
  • 2
    $\begingroup$ duplicate: math.stackexchange.com/questions/103907/… $\endgroup$ – awllower Feb 3 '12 at 9:40
6
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.