# Congruence for the number of points in the elliptic curve $y^2 = x^3+b \pmod{p}$

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.

• You don't need the full strength of Hasse's theorem for this, because the elliptic curves you consider have complex multiplication by the cyclotomic rings $\mathbb{Z}[\omega]$ and $\mathbb{Z}[i]$, respectively. Because of that, the sums you mention are essentially the real parts of Jacobi sums: e.g. in the first case, the Jacobi sum is $\sum_{a \mod p}χ(a)ψ(1-a)$, where χ is the quadratic residue character, and ψ is a nontrivial cubic character. Jacobi sums have absolute value equal to √p, as can be shown by explicit calculation. Ireland & Rosen is a good reference. – Alison Miller Apr 20 '14 at 4:31
• Also: if p=A^2+3B^2 (which can be done uniquely for any p that is 1 mod 3), the remainder you are getting is equal to 2A. This can be proved using the Jacobi sum mentioned above, which is equal to A + B √-3. – Alison Miller Apr 20 '14 at 4:45
• The second result you mention goes back to Gauss, and is related to writing $p$ as a sum of two squares. Jacobi seems to have discussed identities related to the first congruence, which as Alison Miller notes above is related to $x^2+3y^2$. This paper by Hudson and Williams discusses these and other such congruences using Jacobi sums: ams.org/journals/tran/1984-281-02/S0002-9947-1984-0722761-X/… – Lucia Apr 20 '14 at 5:11

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