# Show that $\left( \frac{q}{p} \right) \equiv q^{(p-1) / 2} \mod p$, where $\left( \frac{q}{p} \right)$ is the Legendre Symbol

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.

-
@JyrkiLahtonen Yeah, its that group. What's the difference? –  Kaish May 25 '13 at 10:35
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

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

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

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

-