 Solution

By Fermat, $a^{p-1}=1$. Thus $a^{(p-1)/2}=\pm 1$. The squaring map on ${\mathbb{F}}_p^{\ast }$ has kernel $\{\pm 1\}$, so exactly $(p-1)/2$ inputs are squares; the polynomial $x^{(p-1)/2}-1$ has at most that many roots and already has all squares, proving the two cases.