Let $E$ be the elliptic curve $y^2=x^3+1$ and $p \equiv 1 \pmod{3}$ a prime. Computing the number of points mod $p$ of $E$ using the naive method gives:
$$ \#E(\mathbb F\_p) = 1+ \sum\_{x=0}^{p-1} \left( 1 + \left(\frac{x^3+1}{p}\right)\right) \equiv p+1 + \sum\_{x=0}^{p-1}(x^3+1)^{\frac{p-1}2}\pmod{p}$$
developing the right hand side and simplifying there is only one term of the sum surviving and we get:
$$ \#E(\mathbb F\_p) \equiv p+1-\binom{\frac{p-1}2}{\frac{p-1}3}\pmod{p}$$ 
Hasse theorem now implies that if $p$ is large enough (say $p>16$) then the minimal residue of 
$$ \binom{\frac{p-1}2}{\frac{p-1}3}\pmod{p}$$
is smaller than $2\sqrt{p}$. As this last result seems completely unrelated to elliptic curves my question is if there is a more direct proof of this fact not using Hasse's theorem.


Using instead the elliptic curve $y^2 = x^3+x$ and a prime $p \equiv 1 \pmod{4}$ one finds the similar result that the least minimal residue of 
$$ \binom{\frac{p-1}2}{\frac{p-1}4}\pmod{p} $$
is also bounded in absolute value by $2\sqrt{p}$.


My motivation is simple curiosity, I fell on it playing with some examples and now I can't take it out of my head.



Congruence for the number of points in the elliptic curve $y^2 = x^3+b \pmod{p}$
This is really just my comment above, but maybe it's a reasonable answer. Congruences between certain binomial coefficients and the representations of primes by some quadratic forms go back to Gauss and Jacobi. The two examples given in the question and a number of other examples are discussed in the paper [Binomial coefficients and Jacobi sums](http://www.ams.org/journals/tran/1984-281-02/S0002-9947-1984-0722761-X/S0002-9947-1984-0722761-X.pdf) by Hudson and Williams (which also gives references to the original works of Gauss, Jacobi and others). One main idea is to work out congruences for binomial coefficients in terms of Jacobi sums (Theorem 5.1 of the paper). Here are a couple more interesting facts from the paper: 


If $p\equiv 1 \pmod{7}$ then 
$$
\binom{3(p-1)/7}{(p-1)/7} \equiv -2x \pmod{p},
$$
where $p=x^2+7y^2$. This is due to Jacobi. Also if $p\equiv 1 \pmod{12}$, then $\binom{(p-1)/2}{(p-1)/12}$ is $\pm \binom{(p-1)/2}{(p-1)/4} \pmod{p}$ and the sign can be determined by looking at the representation of $p$ as the sum of two squares. (Corollary 4.2.2 of the paper.)


