Solution
= Solution
By Fermat, $a^{p-1}=1$. Thus $a^{(p-1)/2}=\pm1$. The squaring map on $\mathbb F_p^*$ has kernel $\{\pm1\}$, 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.