order of elliptic curve $y^2 = x^3 - x$ defined over $F_p$, where $p \equiv 3 \mod{4}$

Question

It is said that the elliptic curve $y^2 = x^3 - x$ defined over a prime field $\mathbb{F}_p$, where $p \equiv 3 \mod{4}$ has an order $p + 1$.

When I tried to get the elements of $E = \{(x,y) \in \mathbb{F}_3\times\mathbb{F}_3| y^2 = x^3 - x\} \cup \{\infty\} $, I only got 3 elements, {(0,0),(1,0),(2,0)}, instead of 4.

Did I miss a step or a point during the computation?

Answer 1

By Fermat's Little Theorem, we see that $x^3\equiv x\mod 3$ for all $x\in\Bbb{Z}$. Hence, any (finite) rational solution over $\Bbb{F}_3$ will always have $y = 0$ (and it is easily checked that $(0,a)\in\Bbb{F}_3\times\Bbb{F}_3$ is a solution for all $a\in\Bbb{F}_3$). However, it appears that you have forgotten the point at infinity is also a solution.

Answer 2

Let $p\equiv3\pmod4$ be a prime. We know that $-1$ is not a quadratic residue modulo $p$. This will be the key.

Consider the polynomial $f(x)=x^3-x$ as a function from $\mathbb{F}_p$ to itself. We easily see that $f(x)=0$ if and only if $x\in\{0,\pm1\}$. For all these values of $x$ there is thus exactly one value of $y\in\mathbb{F}_p$ such that $y^2=f(x)$, namely $y=0$. Three solutions so far.

Let $x=a$ be any of the other $p-3$ elements of $\mathbb{F}_p$. We know that $f(a)\neq0$. Furthermore, $f(a)=-f(-a)$, so exactly one of $f(a)$ and $f(-a)$ will be a quadratic residue. When $f(a)$ is a non-zero quadratic residue, the equation $y^2=f(a)$ holds for two distinct values of $a$. When $f(a)$ is a quadratic non-residue, the equation $y^2=f(a)$ has no solutions. Altogether, the pair of choices $x=\pm a$ thus gives rise to exactly two points on the curve.

There are $(p-3)/2$ such pairs $x=\pm a$. We have shown that the equation $$ y^2=x^3-x $$ has exactly $3+2\cdot\frac{(p-3)}2=p$ solutions $(x,y)\in\mathbb{F}_p^2$. When you include the point at infinity, you see that the number of $\mathbb{F}_p$-rational points on this elliptic curve is $p+1$ as claimed.