Explicit formula for Fermat's 4k+1 theorem Let $p$ be a prime number of the form $4k+1$. Fermat's theorem asserts that $p$ is a sum of two squares, $p=x^2+y^2$.
There are different proofs of this statement (descent, Gaussian integers,...). And recently I've learned there is the following explicit formula (due to Gauss):
$x=\frac12\binom{2k}k\pmod p$,
$y=(2k)!x\pmod p$
($|x|,|y|<p/2$). But how to prove it?
Remark. In another thread Matt E also mentions a formula 
$$
x=\frac12\sum\limits_{t\in\mathbb F_p}\left(\frac{t^3-t}{p}\right).
$$
Since $\left(\dfrac{t^3-t}p\right)=\left(\dfrac{t-t^{-1}}p\right)=(t-t^{-1})^{2k}\mod p$ (and $\sum t^i=0$ when $0<i<p-1$), this is, actually, the same formula (up to a sign).

Here is a high level proof. I assume it can be done in a more elementary way. Chapter 3 of Silverman's Arithmetic of Elliptic Curves is a good reference for the ideas I am using.
Let $E$ be the elliptic curve $y^2 = x^3+x$. By a theorem of Weyl, the number of points on $E$ over $\mathbb{F}_p$ is $p- \alpha- \overline{\alpha}$ where $\alpha$ is an algebraic integer satisfying $\alpha \overline{\alpha} =p$, and the bar is complex conjugation. (If you count the point at $\infty$, then the formula should be $p - \alpha - \overline{\alpha} +1$.)
Let $p \equiv 1 \mod 4$. We will establish two key claims: Claim 1: $\alpha$ is of the form $a+bi$, for integers $a$ and $b$, and Claim 2: $-2a \equiv \binom{(p-1)/2}{(p-1)/4} \mod p$. So $a^2+b^2 = p$ and $a \equiv -\frac{1}{2} \binom{(p-1)/2}{(p-1)/4}$, as desired.
Proof sketch of Claim 1: Let $R$ be the endomorphism ring of $E$ over $\mathbb{F}_p$. Let $j$ be a square root of $-1$ in $\mathbb{F}_p$. Two of the elements of $R$ are $F: (x,y) \mapsto (x^p, y^p)$ and $J: (x,y) \mapsto (-x,jy)$.
Note that $F$ and $J$ commute; this uses that $j^p = j$, which is true because $p \equiv 1 \mod 4$. So $F$ and $J$ generate a commutative subring of $R$. If you look at the list of possible endomorphism rings of elliptic curves, you'll see that such a subring must be of rank $\leq 2$, and $J$ already generates a subring of rank $2$. (See section 3.3 in Silverman.) So $F$ is integral over the subring generated by $J$. That ring is $\mathbb{Z}[J]/\langle J^2=-1 \rangle$, which is integrally closed. So $F$ is in that ring, meaning $F = a+bJ$ for some integers $a$ and $b$. 
If you understand the connection between Frobenius actions and points of $E$ over $\mathbb{F}_p$, this shows that $\alpha = a+bi$.
Proof sketch of Claim 2: The number of points on $E$ over $\mathbb{F}_p$ is congruent modulo $p$ to the coefficient of $x^{p-1}$ in $(x^3+x)^{(p-1)/2}$ (section 3.4 in Silverman). This coefficient is $\binom{(p-1)/2}{(p-1)/4}$. So
$$- \alpha - \overline{\alpha}  \equiv \binom{(p-1)/2}{(p-1)/4} \mod p$$
or
$$-2a \equiv \binom{(p-1)/2}{(p-1)/4} \mod p$$
as desired.
Remark:
This is very related to the formula Matt E mentions. For $u \in \mathbb{F}_p$, the number of square roots of $u$ in $\mathbb{F}_p$ is $1+\left( \frac{u}{p} \right)$. So the number of points on $E$ is 
$$p+\sum_{x \in \mathbb{F}_p} \left( \frac{x^3+x}{p} \right).$$
This is essentially Matt's sum; if you want, you could use the elliptic curve $y^2 = x^3-x$ in order to make things exactly match, although that would introduce some signs in other places. So your remark gives another (morally, the same) proof of Claim 2.
