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.

Show that if $p$ is any odd prime then

$$\left( \frac{q}{p} \right) \equiv q^{\frac{p-1}{2}} \mod p.$$

stating any theory that you use. In particular, you may assume the existence of a primitive element in $G_p$.

Here $\left( \frac{q}{p} \right)$ is the Legendre Symbol and $G_p$ is the group of elements $g \mod p$ such that $\gcd(g,p) = 1$. I said that for some $a \in \mathbb{Z}$, we have

$$a \equiv q^{(p-1) / 2} \mod p \implies a^2 \equiv q^{(p-1)} \equiv 1 \mod p$$

by Fermat's little theorem. And so, by definition of the Legendre symbol, we have that if $q$ is a quadratic residue mod $p$ then $\left( \frac{q}{p} \right) \equiv q^{(p-1) / 2} \mod p$. I'm now stuck on how to show that it is $\equiv -1 $ if it isn't a quadratic residue. Obviously the hint with primitive elements comes into play somehow, but I can't see how it does.

Can someone help me please.

share|improve this question
    
@JyrkiLahtonen Yeah, its that group. What's the difference? –  Kaish May 25 '13 at 10:35
1  
Say $p=5$. The integers congruent to $1\pmod p$ are $1,6,11,16,\ldots,-4,-9,\ldots$. The residue classes coprime to $5$ are $\{\overline{1},\overline{2},\overline{3}$ and $\overline{4}$. A finite list as opposed to an infinite list. Furthermore, that infinite list is not a group under any obvious operation. –  Jyrki Lahtonen May 25 '13 at 10:40

3 Answers 3

up vote 0 down vote accepted

Let $g$ be a primitive root of $p$, a generator of the group of $p-1$ units. Suppose that $a$ is a QR. Then $a\equiv b^2\pmod{p}$ for some $b$. But $b$ is congruent to a power $g^e$ of $g$. So $a$ is congruent to $g^{2e}$. And by Fermat's Theorem, $(g^{2e})^{(p-1)/2}\equiv 1\pmod{p}$.

Note that all $(p-1)/2$ numbers congruent to an even power of $g$ are automatically QR.

Since there are $(p-1)/2$ QR, the numbers congruent to an odd power of $g$ are all NR. An odd power of $g$ cannot be congruent to $1$ modulo $p$. Let $x=a^{(p-1)/2}$. Then $x^2\equiv 1\pmod{p}$, so $x\equiv \pm 1\pmod{p}$. If $a$ is an NR, then $a^{(p-1)/2}\not\equiv 1 \pmod{p}$, so it is $\equiv -1\pmod{p}$.

share|improve this answer
    
Whats $e$? Just some random integer that gives us $b \mod p$? –  Kaish May 25 '13 at 10:45
    
Yes. If we insist that it be between $0$ and $p-2$, it is uniquely determined, and is often called the index of $b$ with respect to $g$. It is therefore an analogue of the logarithm, and is often nowadays called the discrete logarithm. –  André Nicolas May 25 '13 at 10:50
    
I just had a thought, here, we (or you) prove that it is either $\pm 1 \mod p$, but the symbol isn't supposed to show that. An element can be a quadratic reisudue and be $-1 \mod p$ and it can not be a quadratic residue and be $-1 \mod p$, so how does this show that's what the symbol is? –  Kaish May 25 '13 at 15:21
1  
The real result is: If $a$ is a QR, then $a^{(p-1)/2}\equiv 1$. If $a$ is a NR, then $a^{(p-1)/2}\equiv -1$. Now because the Legendre symbol $(a/p)$ is defined as $1$ if $a$ is QR, $-1$ if $a$ is NR, the real result can be written as $(a/p)\equiv a^{(p-1)/2}\pmod{p}$. –  André Nicolas May 25 '13 at 16:59

Hint (assuming I have correctly guessed what the question really is):

Let $g$ be a primitive element. Find $a$ in such a way that $q\equiv g^a\pmod p$. Show that $x=q^{(p-1)/2}\equiv1$, iff $a$ is even. Show that $x^2\equiv1\pmod p$ irrespective of parity of $a$, so...

share|improve this answer
    
I've already shown that $x^2 \equiv 1 \mod p$ so I can then just say from here we can see that $x \equiv \pm 1 \mod p$? –  Kaish May 25 '13 at 10:44
    
You have probably done that as an another exercise earlier? If not, then you should justify that somehow. The point here is to tie the sign of $x$ together with parity of $a$. –  Jyrki Lahtonen May 25 '13 at 10:46
    
Oh, I meant I did it in this question when I used Fermat to show that $a^2 \equiv (blah)$, can that bit not be used again? –  Kaish May 25 '13 at 10:55

As you said, by Fermat's little theorem $$ 0 \equiv q^{p-1} - 1 = (q^{(p-1)/2} + 1)(q^{(p-1)/2} - 1) \pmod p. $$ If $q$ is a quadratic residue, then $q^{(p-1)/2} \equiv 1 \pmod p$ again by Fermat, and if it is not, then $q^{(p-1)/2}+1$ must equals $0$ in $\mathbb{Z}_p$ since it is a field.

share|improve this answer

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.