On Courant/Robbins' "What is mathematics?", it says that:
Due to Fermat's Little Theorem, we have $a^{p-1}\equiv 1 \pmod p$. This suggests that we define $p'=\frac{p-1}{2}$ and factor the previous congruence as:
$$(a^{p'}-1)(a^{p'}+1)\equiv 0 \pmod p \tag{$\color{red}{☭}$}$$
And then we must have $a^{p'}\equiv 1 \pmod p$ or $a^{p'}\equiv -1 \pmod p$. Now, If $a$ is a quadratic residue, that is, for some $x$, we have:
$$a\equiv x^2\pmod p$$
From this, we have:
$$a^{p'}\equiv x^{p-1} \equiv 1\pmod p$$
That is: If $a$ is a quadratic residue, then $a^{p'}\equiv 1\pmod p$ and he says that it can easily be proven that if $a$ is not a quadratic residue, then $a^{p'}\equiv -1\pmod p$. I suppose I know how to prove it:
- If $a$ is a quadratic residue, then $a^{p'}\equiv 1\pmod p$. With contrapositive, we obtain that $a^{p'}\not\equiv 1\pmod p$ then $a$ is not a quadratic residue.
- Also, if $a^{p'}\not\equiv 1\pmod p$ due to the Fermat's little theorem, we have $(\color{red}{☭})$ and as $a^{p'}-1\not\equiv 0 \pmod p$ we must have $a^{p'}+1\equiv 0 \pmod p$.
Is my proof correct?
Your proof is not complete.
It has been shown that, if $a$ is a quadratic residue, then $a^{p'}\equiv1\pmod p$.
Furthermore, it has been shown that, if $a$ is not a quadratic residue, then $a^{p'}\equiv\pm1\pmod p$.
To show that, if $a$ is not a quadratic residue, then $a^{p'}\equiv-1\pmod p$,
it remains to be shown that, if $a$ is not a quadratic residue, then $a^{p' }\not\equiv1\pmod p$.
To show that, consider how many quadratic residues there are,
and how many solutions $a^{p'}-1\equiv0\pmod p$ could have.