# Let $a$ be a quadratic residue modulo $p$. Prove $a^{(p-1)/2} \equiv 1 \bmod p$.

Question:
Let $a$ be a quadratic residue to a prime modulus $p$. Prove $a^{(p-1)/2} \equiv 1 \pmod{p}$.

My attempt at a solution:
\begin{align*} &a\text{ is a quadratic residue}\\\ &\Longrightarrow a\text{ is a residue class of $p$ which has even index $c$ relative to a primitive root $g$}\\\ &\Longrightarrow a \equiv g^c \pmod{p}\\\ &\Longrightarrow a \equiv g^{2k} \pmod{p}\text{ where $2k=c$}\\\ &\Longrightarrow g^{2kv} \equiv g^{c} \pmod{p}\text{ for some natural number $v$}\\\ &\Longrightarrow 2kv \equiv c \pmod{p-1}\text{ (by a proof in class)}\\\ &\Longrightarrow 2kv \equiv 2k \pmod{p-1}\\\ &\Longrightarrow kv \equiv k \pmod{(p-1)/2}\\\ &\Longrightarrow v \equiv k(k^{-1}) \pmod{(p-1)/2}\text{ since $\gcd(2k, p-1)$ is not equal to 1}\\\ &\Longrightarrow k^{-1} \text{ (k inverse exists)}\\\ &\Longrightarrow v \equiv 1 \pmod{(p-1)/2}. \end{align*}

I believe this implies that $g^{(p-1)/2} \equiv 1 \pmod{p}$, is this correct?
Although what I was required to show was $a^{(p-1)/2} \equiv 1 \pmod{p}$, am I on the right track, how do I show this, I've spent quite some time on this and looked over all the proofs in my notes, I can't seem to find out how.

-
This is called Euler Criterium. Hint: use Fermat's little theorem. – Poirot Nov 18 '10 at 23:11
Thanks for the help! If you put your comment as an answer I can "tick mark" it for you – fmunshi Nov 18 '10 at 23:17
No problem. I think that any number theory book has its proof, but you should try first. – Poirot Nov 18 '10 at 23:21
@John: Euler's criterion is not this result but, rather, the less trivial converse. – Bill Dubuque Nov 18 '10 at 23:38
@Bill Dubuque: Euler's criterion is actually this result and its converse (if and only if) – fmunshi Nov 18 '10 at 23:56

Bill has succintly told you how to prove the result. But you were also asking for comments on your proposed argument. I will address that.

In line 5, where did the $v$ come from, and what is its role? Notice that you can take $v=1$ and what you write is true. So how is this giving you any information?

In line 9, you are already using an inverse of $k$, even though you only assert its existence in the next line. You cannot do that: in order to use it, you must first show it exists, and you haven't done it.

But assuming it does exist, and that your entire chain of argument holds, you'll notice that all you concluded was that $v\equiv 1\pmod{(p-1)/2}$. This is of course natural: you have $a=g^c=g^{2k}=g^{2kv}$; you can always take $v=1$ and that will work regardless of $k$, $g$, $a$... And you probably know now that it does not lead to a proof.

So you had not actually proven anything. You've only written $a$ as an even power of a primitive root, and that's it. Lines 1 through 4 are correct; but from line 5 through the end, you are just spinning your wheels and not getting any closer to the result you want.

-
thanks for the help, I can see you really take your time to help people! – fmunshi Nov 20 '10 at 4:23
also note that my attempt at a solution was based of notes that I took in class and tried to decipher at home, it didn't work as you pointed out :) – fmunshi Nov 20 '10 at 4:24
@fmunshi: no problem. Learning to write a proof is often what students find most difficult, and there is no better way than trying. I went through merciless (but well meaning) reams of corrections to my writing as a student, and it certainly helped. – Arturo Magidin Nov 20 '10 at 4:27

HINT $\$ Put $\rm\ a = b^2\$ and use Fermat's little theorem.

NOTE $\$ The converse is also true - it is known as Euler's criterion.

-

Here is my proof of Euler's criterion that I created to avoid the words 'field' and 'Lagrange's theorem' mentioned in Wikipedia's proof of Euler's criterion (here). $$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{\! p},$$

where $p$ is an odd prime (Legendre symbol is only defined for odd primes $p$).

$a\equiv 0\pmod{\! p}$ clearly works.

If $a\not\equiv 0$, then $a^{p-1}\equiv 1\pmod{\! p}$ by Fermat's little theorem, so

$$p\mid (a^{\frac{p-1}{2}}+1)(a^{\frac{p-1}{2}}-1),$$

so by Euclid's lemma (see proof in Wikipedia) $$p\mid a^{\frac{p-1}{2}}+1\ \ \text{ or }\ \ p\mid a^{\frac{p-1}{2}}-1$$

In below theorem I'll use $$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)$$

Theorem: a polynomial of degree $n\ge 1$ has at most $n$ zeroes mod $p$.

Proof: By induction. $x- b\equiv 0\pmod{\! p}$ has exactly one solution. Assume $f(x)_k\equiv 0\pmod{\! p}$ has at most $k$ solutions (where $k\ge 1$ and $f(x)_k$ is a polynomial of degree $k$ with coefficients $a_i$).

If $f(x)_{k+1}\equiv 0\pmod{\! p}$ has no solutions, we're done. Otherwise let a solution be $x_1$. Then

$$f(x)_{k+1}\equiv f(x)_{k+1}-f(x_1)_{k+1}$$

$$\equiv a_{k+1}\left(x^{k+1}-x_1^{k+1}\right)+a_k\left(x^{k}-x_1^{k}\right)+\cdots+a_1\left(x -x_1\right)+a_0\left(1-1\right)$$

$$\equiv (x-x_1)P(x)\pmod{\! p}$$

with $P(x)$ being a polynomial of degree $k$, so $f(x)_{k+1}\equiv 0\pmod{\! p}$ has at most $k+1$ solutions.

We know $a^{p-1}\equiv 1\pmod{\! p}$ has exactly $p-1$ solutions (by little Fermat).

$a^{\frac{p-1}{2}}\equiv 1$ and $a^{\frac{p-1}{2}}\equiv -1$ mod $p$ have at most $\frac{p-1}{2}$ solutions each by above theorem, so each has exactly $\frac{p-1}{2}$ solutions.

There are $\frac{p-1}{2}$ quadratic residues (excluding $0$) and $\frac{p-1}{2}$ quadratic non-residues (see below for proof), from which, with $\left(x^2\right)^{\frac{p-1}{2}}\equiv 1\pmod{\! p}$ by Fermat's little theorem, Euler's criterion follows.

$x^2\equiv y^2\pmod{\! p}\iff x\equiv \pm y\pmod{\! p}$, so $1^2,2^2,\ldots, \left(\frac{p-1}{2}\right)^2$ generate all different non-zero quadratic residues.

-