Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
2  
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
2  
duplicate: math.stackexchange.com/questions/103907/… –  awllower Feb 3 '12 at 9:40
add comment

3 Answers

up vote 6 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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