Show there exist integers $a$ and $b$ such that $a^2+b^2\equiv -1\mod p$

Question

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?$

Answer 1

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.

Answer 2

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$.

Answer 3

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.