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?$
 A: Let $A=\{a^2 : a\in \mathbb{Z}/p\mathbb{Z}\}$ and $B=\{-1-b^2:b\in\mathbb{Z}/p\mathbb{Z}\}=-1-A$. Then $A$ and $B$ have the same number of elements, $\frac{p-1}{2}+1=\frac{p+1}{2}$. Note that $0 \in A$. Therefore, $A$ and $B$ cannot be disjoint.
A: If you want to overkill the problem because you are bored during the pandemic social-distancing, you can use the Chevalley-Warning Theorem.  Consider the polynomial $$f(x,y,z):=x^2+y^2+z^2$$ in $\mathbb{F}_p[x,y,z]$.  Then, the number of variables is $3$, which is greater than the degree of $f$.  The theorem declares that the number of solutions, $n$, of $(u,v,w)\in\mathbb{F}_p^3$ to the equation $f(u,v,w)=0$ must satisfy $$n\equiv 0\pmod{p}\,.$$  Because $f(0,0,0)=0$, we conclude that $n>0$.  Therefore, $n\geq p$.  Ergo, there exists a solution $(u,v,w)\in\mathbb{F}_p$ to $f(u,v,w)=0$ such that $(u,v,w)\neq (0,0,0)$.  Without loss of generality, let $w\neq 0$.  Then, $a:=uw^{-1}$ and $b:=vw^{-1}$ satisfies $a^2+b^2+1\equiv 0\pmod{p}$.

Here is another unnecessarily complicated proof using the Combinatorial Nullstellensatz.  We want to show that $u^2+v^2+w^2=0$ has a different solution than $(u,v,w)=(0,0,0)$.   Define
$$g(x,y,z):=1-\big(x^2+y^2+z^2\big)^{p-1}-(1-x^{p-1})(1-y^{p-1})(1-z^{p-1})\,.$$
We see that the total degree of $g(x,y,z)$ is $3(p-1)$, and a highest-degree term $x^{p-1}y^{p-1}z^{p-1}$ has a nonzero coefficient (namely, $1$) in $g(x,y,z)$.  By the Nullstellensatz, $g(u,v,w)\neq 0$ for some $(u,v,w)\in\mathbb{F}_p^3$.  Since $g(0,0,0)=0$, we conclude that $(u,v,w)\neq (0,0,0)$.  However, this means $1-u^{p-1}=0$, $1-v^{p-1}=0$, or $1-w^{p-1}=0$, implying that $$0\neq g(u,v,w)=1-(u^2+v^2+w^2)^{p-1}\,.$$  Consequently, $u^2+v^2+w^2=0$.  The rest is as in the former proof.

My last proof uses the Cauchy-Davenport Theorem.  Note that the subset $Q\subseteq\mathbb{F}_q$ consisting of quadratic residues has $\dfrac{p+1}{2}$ elements.  Then, by the Cauchy-Davenport Theorem,
$$|Q+Q|\geq \min\big\{p,|Q|+|Q|-1\big\}=\min\Biggl\{p,2\left(\frac{p+1}{2}\right)-1\Biggr\}=p\,.$$
Hence, $Q+Q=\mathbb{F}_p$.  Thus, for any $t\in\mathbb{F}_p$, there are $a,b\in\mathbb{F}_p$ such that $a^2+b^2=t$.  In particular, this holds when $t=-1$.
A: 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.
