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$)?
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$.
We have used the fact that the integers modulo a prime form a field, and over a field the number of zeros of a polynomial can't exceed the degree of the polynomial.