Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

While studying Elementary Number theory by David M. Burton I came across this line:

because $r$ is a primitive root of $p$, $$ r ^{ (p-1)/2} \equiv -1 (\mod p) $$ where $p$ is an odd prime.

Could someone please explain how is it derived? Thanks in advance.

share|cite|improve this question
If you already know why $r^{p-1}\equiv +1\quad (\mathrm{mod}\ p)$ consider what square roots $+1$ has modulo a prime $p$. Which of them can be congruent to $r^{(p-1)/2}$? – Jeppe Stig Nielsen Apr 7 '13 at 10:14
up vote 4 down vote accepted


If $r$ is a primitive root of $p$, there exists $\{1,2,\dots (p-1) \}$ remainders when powers of $r$ is divided by $p$.

We know that GCD$(r,p)=1$, therefore using Fermat's little theorem:

$r^{\phi(p)} \equiv 1 \mod p \implies r^{p-1} \equiv 1 \mod p$

$r^{\frac{p-1}{2}} \equiv \pm1 \mod p$ , it can't be $1 \mod p$ as it is already taken by $r^{p-1}$(There can be no two remainders when p is divided by $\{r^{1},r^{2}, \dots r^{p-1} \}$.

Note: As Don Antonio suggests in his comment, as $r$ is given to be a primitive root, it can't be $ 1 \mod p$ unless the power of $r$ is raised to $p-1$.


$r^{\frac{p-1}{2}} \equiv p-1 \mod p \equiv -1 \mod p$

There's an interesting approach through pigeon-hole principle, too.

Elementary approach:

You have got $r$ balls in circle, you divide it in a group of $p$, let the balls left be $k$. Every time you increase the number of balls to power of $r$ to the power upto $(p-1)$, you will get a distinct number of balls left in the end, try reasoning why only ONE ball is left when you have $r^{p-1}$ balls in a circle.

share|cite|improve this answer
Could you please explain through pigeon-hole method too. – rishabh Apr 7 '13 at 12:59
You have $(1, \dots p-1$) remainders $\mod p$, once you cross over $(p-1)$ distinct remainders, the remainders repeat and thus should be from the set $\{1,2, \dots ,p-1 \}$. – Inceptio Apr 7 '13 at 13:11

If $0 \ne a \in \Bbb{Z}_{p}$, we have by Euler-Fermat $$ 1 = a^{{p-1}} = (a^{\frac{p-1}{2}})^{2}, $$ so $$a^{\frac{p-1}{2}} = \pm 1,$$ because the polynomial $x^2 -1$ has only the two roots $\pm 1$ in the field $\Bbb{Z}_{p}$. (Recall $p$ is an odd prime.)

Now by definition a primitive root $r$ has order $p-1$, so $$ r^{\frac{p-1}{2}} \ne 1, $$ therefore $$ r^{\frac{p-1}{2}} = -1. $$

share|cite|improve this answer

This being a primitive root means that $r$ is a generator for the multiplicative group mod p. This implies that $r^{p-1}=1 (mod\: p)$ and that p-1 is the lowest power of r to make it equal to the identity, this is what is called the order of $r$

Now use the fact that $p$ is a odd prime, which implies that $p-1$ is even. Therefore $(p-1)/2$ is an integer and we know that: $(r^{(p-1)/2})^2=1 (mod\: p)$. Therefore $r^{(p-1)/2}$ has order of at most 2. It cannot have order 1(being the identity) because then $r$ would not be a generator. Therefore the order is 2. Then conclude that it most be $-1 (mod\: p)$.

share|cite|improve this answer

Hint $\ $ In $\rm\,\Bbb Z_p\,$ (or any domain), $ $ if $\rm\:r\:$ has order $\rm\,2n\,$ then $\rm\:0\, =\, r^{2n}\!-1 = (r^n-1)(r^n\!+1)\:$ so $\rm\:r^n = \pm1.\:$ But $\rm\,r\,$ has order $\rm\,2n\:\Rightarrow\:r^n\ne 1,\:$ therefore $\rm\,r^n = -1.$

share|cite|improve this answer

Your Answer


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.