# Prove that there are $p+1$ points on the elliptic curve $y^2 = x^3 + 1$ over $\mathbb{F}_p$, where $p > 3$ is a prime such that $p \equiv 2 \pmod 3$.

Let $p > 3$ be a prime such that $p \equiv 2 \pmod 3$. Define the elliptic curve $E$ over $\mathbb{F}_p$ by $y^2 = x^3 + 1$. Prove that $E(\mathbb{F}_p)$ consists of $p+1$ points.

Using Fermat's little theorem you can prove that $x^3 + 1$ is a bijection on $\mathbb{F}_p$. Hence, $$\#E(\mathbb{F}_p) = \#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x^3 + 1\} + \#\{\infty\} = \#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x\} + 1.$$ But then I am stuck trying to prove that $y^2 = x$ has $p$ solutions $(x,y) \in \mathbb{F}_p^2$.

• How this is true :$$\#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x^3 + 1\} + \#\{\infty\} = \#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x\} + 1.$$ – curious Dec 3 '13 at 11:47
• @curious Consider the equations $y^2 = x^3 + 1$ and $y^2 = z$ over $\mathbb{F}_p$. The map $(x,y) \mapsto (z = x^3 + 1,y)$ is a bijection between their respective solution sets, because $x \mapsto x^3 + 1$ is a bijection on $\mathbb{F}_p$. In particular, the equations have the same number of solutions. – Ricardo Buring Dec 3 '13 at 19:08

If any of $x,y$ is zero, then $x=y=0$ is the only solution pair. Otherwise, there are $\displaystyle\frac{p-1}2$ quadratic remainders $x$ and for each one exactly $2$ pieces of $y$'s belong ($\pm y$ once $y^2\equiv x$). It's altogether $1+2\cdot\displaystyle\frac{p-1}2=p$.

Or, an even easier approach: for each $y\in\Bbb F_p$ there is exactly one such $x$.

• Your easy approach is nice. Thank you. – Ricardo Buring Nov 11 '12 at 14:33

It is much more easy to prove. Like known from RSA the equation const = x^3 mod n has exactly one solution for x, namely x = const ^ d mod n there d = inv(3, phi(n)).

The only condition is, geatest common divisor gcd(3, phi(n)) must be one. In our case Euler's totient function phi equals p-1. The condition is true since p = 2 mod 3,

since p - 1 = 1 mod 3 it follows gcd(3, p-1) = 1.

For y^2 unequal to zero we get two points for a specific value of y. Since y^2 minus one has (p-1)/2 different values. we totally get (p - 1) points plus the point for y = 0 the point (p-1, 0) and the point at infinity. So, we have a total of (p - 1) + 1 + 1 = p + 1 points.