Quadratic non-residues 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$)?

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