Number of points on elliptic curves over finite fields

Question

I noticed that for elliptic curves of the form

$y^2≡x^3+a\pmod p$

sometimes the number of points is always $p+1$ for any choice of $a$. This seems to be the case for all $p ≡ 5 \pmod 6$.

Moreover, when this does not happen, i.e., for $p ≡ 1 \pmod 6$, it looks like there are exactly zero curves of such form where the number of points is $p+1$.

Can someone point me towards the right direction as to why this happens?

Answer 1

The case $p \equiv 5 \pmod 6$ was already solved here, so I'll just handle the other one.

Denote $S_a = \{ (x,y) | y^2=x^3+a \}$. Then $\bigcup S_a = \mathbb{F}_p^2$. We want to prove $|S_a| \neq p$ for non-zero $a$ (with our point at infinity this would mean that number of points on the curve is $ \neq p+1$).

Firstly, look at $S_0$ (this case actually won't be needed, but I think it's good to show it as well). $y^2=x^3$ either if $(x,y)=(0,0)$ (that's one point) or if $y^2=t$ and $x^3=t$ for some non-zero $t$. Since $\mathbb{F}_p^{\times} \sim \mathbb{Z}_{p-1}$, $t$ is a sixth power, so we have $\frac{p-1}{6}$ choices for $t$, two solutions for $y^2=t$ and three solutions for $x^3=t$. Therefore $|S_0|=1+\frac{p-1}{6} \cdot 2 \cdot 3 = p$.

Now we will just investigate cases:

• $a$ is not a quadratic residue

Then for any $y$, $y^2-a$ is non-zero. So for any particular $y$, equation $y^2-a=x^3$ has either zero or three solutions. Therefore $|S_a|$ is divisible by $3$, so it can't be equal to $p$.

• $a$ is not a cubic residue

Then for any $x$, $x^3+a$ is non-zero, so $y^2=x^3+a$ regarded as an equation for $y$ has zero or two solutions. Thus $|S_a|$ is even, so it's not $p$.

• $a$ is both quadratic and cubic residue

Well, $|S_a|$ is just

$$ \sum_x \#\{y:y^2=x^3+a\} $$

Every term in this sum is equal to two if $x^3+a$ is quadratic residue, zero if it's quadratic non-residue, and one if it's zero. Consider $b$ that is a quadratic non-residue. Then

$$ \#\{y:b^3y^2=x^3+a\} + \#\{y:y^2=x^3+a\} = 2 $$

for any $x$, so

$$ 2p = \sum_x \#\{y:b^3y^2=x^3+a\} + \#\{y:y^2=x^3+a\} = \sum_x \#\{y:b^3y^2=x^3+a\} + |S_a|$$

But $\sum_x \#\{y:b^3y^2=x^3+a\}$ is the same as $\sum_x \#\{y:y^2=x^3+ab^{-3}\} = |S_{ab^{-3}}|$: and now $ab^{-3}$ is a quadratic non-residue, so we already know that it's not equal to $p$. Therefore we also have $|S_a| \neq p$.

Answer 2

I will explain the idea of why there are $ p+1$ points when $p\equiv 2 \pmod{3}$, $p$ prime odd.

First, observe that the map $x\mapsto x^3$ is a bijection on $k=GF(p)$, the field with $p$-elements, if $p\equiv 2 \pmod{3}$.

Hence the same is true for the map $f$ given by $x\mapsto x^3+1$ .

Now, there are $\frac{p-1}2$ numbers that are squares and not 0. This give $p-1$ points with $y$ coordinate non 0. There is also one with $y=0$, namely $(-1,0)$, and one point at infinity.