Sum of two squares modulo p

Question

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How would one prove this? One way is to use Cauchy-Davenport, but I don't think that this is the simplest solution.

Answer 1

There are $(p+1)/2$ squares mod $p$ [if $p$ is odd; the case $p=2$ is left for the reader], so $(p+1)/2$ numbers $x^2$, and $(p+1)/2$ numbers $k-y^2$, so the two sets must overlap, and where they overlap you get $x^2=k-y^2\pmod p$.

Answer 2

Since you're using a combinatorics tag, let's solve this using the pigeonhole principle on elements of $\mathbb{F}_p$.

Since the $p=2$ case is easy, let's assume that $p>2$.

Define $S := \{x^2|x\in\mathbb{F}_p\}$ to be the set of squares in $\mathbb{F}_p$, and $T := k - S = \{k - x^2|x\in\mathbb{F}_p\}$ to be the set of squares shifted by $k$. Note that $S$ and $T$ have the same number of elements, which I claim is $\frac{p+1}{2}$.

We momentarily disregard $0$. The map $x\mapsto x^2$ is a $2$-to-$1$ function from $\mathbb{F}_p^\mathrm{x}$ to itself. So the image of the squaring function on $\mathbb{F}_p^\mathrm{x}$ must have $\frac{1}{2}\cdot\#\mathbb{F}_p^\mathrm{x} = \frac{p-1}{2}$ elements. But the image of this function is exactly the set $S$ minus the $0$ element. So $\#S = \#T = \frac{p+1}{2}$.

This situation is akin to when two stars of enormous but stable mass come into proximity with one another and the total sum of their mass has reached critical level and then they implode, forming a neutron star.

In other words, the pigeonhole principle gives us an neutron star $\alpha$ that must be contained in both $S$ and $T$. So $$\alpha = x^2 = k - y^2$$ And then from this we get $$x^2 + y^2 = k$$

Answer 3

A somewhat circular but funny proof:

Clearly $0=0^2+0^2$. For any $a$ between $1$ and $p$ we can find a prime congruent to $a\bmod p$ and $1\bmod 4$ because of dirichlets theorem. This prime is expressible in the form $b^2+c^2$ because of Fermat's sum of two squares theorem.

Answer 4

Clearly all the quadratic residues mod $p$ can be written in such a form. Since $(\mathbb{Z}/p\mathbb{Z}, +)$ has order $p$, the set of quadratic residues is not closed under addition and there is at least one non-residue $k$ which can be expressed as a sum of two squares. We get the rest of the non-residues upon multiplying the equation by a suitable quadratic residue factor.