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

  • 3
    $\begingroup$ Blast! You beat me. But I swear I'm not adept enough with Latex to type my answer up within 5 minutes! $\endgroup$ – PrimeRibeyeDeal Aug 9 '14 at 12:47
  • 13
    $\begingroup$ You typed 6 paragraphs. I typed 3 lines. $\endgroup$ – Gerry Myerson Aug 9 '14 at 12:48

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.