# How to derive this expression $r ^{ (p-1)/2} \equiv -1 \pmod p$ for primitive root of an odd prime $p$.

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.

-
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

Hint:

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

Therefore,

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

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

-

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

-

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

-