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.

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|improve this question
2  
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
add comment

4 Answers

up vote 4 down vote accepted

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.

share|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 \}$. –  user63477 Apr 7 '13 at 13:11
add comment

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

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

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