# Sum of two squares modulo p

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.

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

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

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.

• how is this circular? Commented Dec 28, 2019 at 1:01
• I'm sorry but I don't understand how Dirichlet's Theorem guarantees that we can find a prime congruent to $a\pmod p$ as well as $1\pmod 4$. Can you please explain a little... Commented Sep 18, 2022 at 20:16
• First get a $k$ that satisfies $k\equiv a \bmod p$ and $k \equiv 1 \bmod 4$ (one will exist due to chinese remainder theorem) and then consider the progression $k,k+4p,k+8p \dots$. Commented Sep 18, 2022 at 20:49

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.