Sum of two squares modulo p

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.