3
$\begingroup$

Primitive roots: If $p$ is a prime such that $p\equiv 1 \pmod 4$, and $a$ is a primitive root, then $-a$ is also a primitive root.

In this particular question I did show that in fact $(-a)^{p-1} \equiv 1 \pmod 4$, what is trivial. But, how can I assure that $p-1$ is its order?

Thanks a lot.

$\endgroup$

marked as duplicate by lab bhattacharjee algebra-precalculus Oct 31 '15 at 17:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ You mean : If $a$ is a primitive root,$-a$ is one as well. $\endgroup$ – Peter Oct 31 '15 at 16:14
  • $\begingroup$ There seems to be some confusion in the Question. Apart from the omission of an assumption about $a$ being "a primitive root", as Peter noted, it seems unlikely that being a primitive root mod 4 is the real issue. $\endgroup$ – hardmath Oct 31 '15 at 16:18
  • $\begingroup$ The edit to the title is helpful, but the same change in the body is more important. Also, please spell out in the body that $a$ is a primitive root mod $p$. $\endgroup$ – hardmath Oct 31 '15 at 16:25
3
$\begingroup$

We are given that $a$ has order $p-1$ modulo $p$, and want to show that $-a$ also has order $p-1$. Suppose to the contrary that $(-a)^n\equiv 1\pmod{p}$ for some $n\lt p-1$. Then $(-a)^{2n}\equiv 1\pmod{p}$, so $a^{2n}\equiv 1\pmod{p}$. Since $a$ is a primitive root of $p$, it follows that $n=\frac{p-1}{2}$.

We show that this is impossible. Recall that since $p\equiv 1\pmod{4}$, there is an $x$ such that $x^2\equiv -1\pmod{p}$. Then $$1\equiv (-a)^{(p-1)/2}\equiv(x^2a)^{(p-1)/2}\equiv a^{(p-1)/2}\pmod{p},$$ contradicting the fact that $a$ has order $p-1$.

$\endgroup$
1
$\begingroup$

Assume, $p-1$ is the order of $a$ modulo $p$ and assume $(-a)^m \equiv 1 \pmod p$ for some $m<p-1$. Then $m$ must be odd because otherwise we would have $a^m\equiv 1 \pmod p$, which is impossible.

For such an odd $m$, we have $a^m\equiv -1\pmod p$ and therefore $a^{2m}\equiv 1\pmod p$. But $2m=p-1$ is impossible because $p-1$ is divisible by $4$. So, we have a contradiction again.

$\endgroup$
0
$\begingroup$

If $p\equiv 1 \pmod 4$, it means that $p-1\equiv 0 \pmod 4$.

Therefore $(-a)^{p-1}\equiv (-a)^{0} \equiv 1 \pmod 4$.

I would do it in this way.

$\endgroup$
  • $\begingroup$ Aren't you just repeating what the OP says already in the body of the Question? $\endgroup$ – hardmath Oct 31 '15 at 16:21
  • $\begingroup$ I'm afraid, I can have misunderstood the question. $\endgroup$ – Michael Oct 31 '15 at 16:23

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