Show there exist integers $a$ and $b$ such that $a^2+b^2\equiv -1\mod p$ I'm asked to show there exist integers $a$ and $b$ such that $a^2+b^2\equiv -1\mod p$ for any odd prime $p$.
The solution starts by saying that the subsets $\{a^2\}$ and $\{-1-b^2\}$ of $\mathbb Z/p\mathbb Z$ both contain $\frac{p-1}{2}$ elements. Why is this? What even is the subset $\{a^2\}$? Is this related to how there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic non-residues $\mod p?$

This is not nessesarily true. First, Fermat's two square theorem states that if 
$a^2 + b^2 = p$ where $p$ is prime, then $p = 1\pmod 4$.
In particular if $p$ is not prime, then it is a product of prime powers congruent to ${0,1,2} \pmod 4$. Consider the solutions of
$a^2 + b^2 \mod 8$.
It is trivial that ${0, 1, 4, 5} \mod 8$ are solutions. ${2,6} \mod 8$ are possible solutions. Any integer $p=1\pmod 4$ gives $2p=2\pmod 8$, and
$p=3\pmod 4$ gives $2p=6\pmod 8$. The latter, however, cannot be a solution since there are factors $p=3\pmod 4$ dividing $a^2+b^2$, a contradiciton.
The solutions are therefore $a^2 + b^2 = {0, 1, 2, 4, 5} \mod 8$ and
$a^2 + b^2 + 1 = {1, 2, 3, 5, 6} \mod 8$.
Which does not represent all numbers.
