While reading the book What is Mathematics? by Courant and Robbins, I've found a statement that I don't know how to prove, although it seems that it shouldn't be really difficult. Literally, they write:

We have just seen that every quadratic residue $a$ of $p$ satisfies the congruence $a^{(p-1)/2} \equiv 1$ (mod $p$). Whithout serious difficulty it can be proved that for every non-residue $b$ we have the congruence $b^{(p-1)/2} \equiv -1$ (mod $p$).

Here, $p$ is a prime number and $a$ and $b$ are any integers not multiples of $p$. The case of quadratic residues is quite easy, you only have to apply Fermat's little theorem, but although they say that it can be proved whithout serious difficulty, I can't see how to do the case of non-residues. I've been looking on the Internet for some ideas, but my knolewdge of the theory of numbers is quite elementary (in fact, I only know some facts which are mentioned in the book: congruences, Fermat's little theorem, ...) and all the proofs I've found are out of my reach. Is there any elementary proof of the fact that $b^{(p-1)/2} \equiv -1$ (mod $p$)?

• A polynomial of degree $d$, considered modulo a prime, can have no more than $d$ zeros. There are $(p-1)/2$ quadratic residues, which uses up all the room for zeros of $x^{(p-1)/2}-1$. – Gerry Myerson Nov 19 '14 at 12:04
• @Mike, done.${}$ – Gerry Myerson Nov 20 '14 at 1:29

Let $b$ be a quadratic non-residue modulo a prime $p$. Let $c=b^{(p-1)/2}$. By Fermat, $c^2\equiv1\pmod p$. It follows that either $c\equiv1\pmod p$ or else $c\equiv-1\pmod p$. Now, the congruence $x^{(p-1)/2}\equiv1\pmod p$ is of degree $(p-1)/2$ and has among its solutions all the quadratic residues, of which there are exactly $(p-1)/2$; therefore, its only solutions are the quadratic residues. So, we can't have $c\equiv1\pmod p$, and we must have $c\equiv-1\pmod p$.
Note that $b^{p-1} \equiv 1 \pmod{p}$, assuming $p$ is a prime which does not divide $b$. Taking the square root of both sides, we get $b^{(p-1)/2} \equiv \pm 1 \pmod{p}$. Of course, it cannot be $1$, because it would then be a quadratic residue, so it has to be $-1$.
• Yes, that was my first try... Maybe I'm losing something, but I can't see why if $b^{(p-1)/2} \equiv 1$ (mod $p$) then $b$ is a quadratic residue. The converse is obviously true, for if $b \equiv x^2$ (mod $p$) for some $x$ then $b^{(p-1)/2} \equiv x^{p-1} \equiv 1$ (mod $p$) because of Fermat's little theorem. – Alex V. Nov 19 '14 at 11:20
• $b^{(p-1)/2}$ is nothing but $(b^{\frac{1}{2}})^{p-1}$, and it is congruent to $1$ modulo $p$. Thus $b^{\frac{1}{2}}$ is an integer, and $b$ is a square modulo $p$. – shardulc Nov 19 '14 at 11:26
• I don't think that's a valid reasoning... You also have $$3^4 = 81 \equiv 1 \;(\text{mod }10)$$ And with your idea we could conclude that $3^{1/2}$ is an integer, because $(3^{1/2})^8 \equiv 1$ (mod $10$). – Alex V. Nov 19 '14 at 13:32
• When you work modulo 7, $2^{1/2}=\pm3$. – Gerry Myerson Nov 19 '14 at 23:06