Course 428

Elliptic Curves I

Dr Timothy Murphy

Maxwell Theatre Friday, 21 January 2000 10:15–11:45

Attempt 5 questions. (If you attempt more, only the best 5 will be counted.) All questions carry the same number of marks.

1. Explain informally how two points on an elliptic curve are added.

Find the sum P + Q of the points P = (−2, 3), Q = (2, 5) on the curve

y^{2} = x^{3} + 17

over the rationals ℚ. What is 2P? Answer:

(a) The line P Q meets the curve again in a point R. We have

R = −(P + Q).

Let OR meet the curve again in the point S. Then S = −R = P + Q.

If P = Q then we take the tangent at P in place of the line P Q.

(b) The line P Q is given by

det (\begin{matrix}x & y & 1 \\ −2 & 3 & 1 \\ 2 & 5 & 1 \end{matrix}) = 0,

ie

−2x + 4y − 16 = 0,

ie

y = \frac{1}{2}x + 4.

This meets the curve where

(\frac{1}{2}x + 4)^{2} = x^{3} + 17.

We know that two of the roots of this equation are −2, 2; hence the third is given by

−2 + 2 + x = \frac{1}{4},

ie

x = \frac{1}{4}.

From the equation of the tangent,

y = \frac{1}{8} + 4 = \frac{33}{8}.

Thus

P + Q = −(\frac{1}{4}, \frac{33}{8})

= (\frac{1}{4}, −\frac{33}{8}).

2. Express the 5-adic integer 2/3 ∈ ℤ_{5} in standard form

1/3 = a_{0} + a_{1}5 + a_{2}5^{2} + ⋯ (0 ≤ a_{i} < 5).

Does there exist a 5-adic integer x such that x^{2} = 6? Answer: We have

\frac{2}{3} ≡ 4 mod 5

since 3 · 4 ≡ 2 mod 5. Now

\frac{2}{3} − 4 = \frac{−10}{3} = 5\frac{−2}{3}.

But

\frac{−2}{3} ≡ 1 mod 5.

Thus

\frac{2}{3} ≡ 4 + 1 · 5 mod 5^{2}.

Furthermore,

\frac{−2}{3} − 1 = \frac{−5}{3} = 5\frac{−1}{3}.

But

\frac{−1}{3} ≡ 3 mod 5.

Thus

\frac{2}{3} ≡ 4 + 1 · 5 + 3 · 5^{2} mod 5^{3}.

Continuing,

\frac{−1}{3} − 3 = \frac{−10}{3} = 5\frac{−2}{3}.

We have been here before;

\frac{−2}{3} ≡ 1 mod 5.

Thus

\frac{2}{3} ≡ 4 + 1 · 5 + 3 · 5^{2} + 1 · 5^{3} mod 5^{4}.

We have entered a loop; and the pattern will repeat itself indefinitely. We conclude that

\frac{2}{3} = 4 + 1 · 5 + 3 · 5^{2} + 1 · 5^{3} + 3 · 5^{4} + 1 · 5^{5} + 3 · 5^{6} + · · · .

Let us verify this; the sum on the right is

4 + \frac{5}{1 − 5^{2}} + \frac{3 · 5^{2}}{1 − 5^{2}} = 4 + 5\frac{1 + 15}{−24}

= 4 − 5\frac{2}{3}

= \frac{2}{3}.

There does exist a 5-adic integer x such that x^{2} = 6? Here are two ways of seeing this.

(a) By the binomial theorem,

x = (1 + 5)^{1/2}

= 1 + \frac{1}{2}5 + \frac{(1/2)(−1/2)}{2!}5^{2} + \frac{(1/2)(−1/2)(−3/2)}{3!}5^{3} + ⋯

A p-adic series ∑ a_{n} converges if and only if a_{n} → 0. So we have to ensure that

∥\binom{1/2}{n}5^{n}∥_{5} → 0.

It is sufficient to show that

∥\frac{5^{n}}{n!} ∥_{5} → 0.

Let p be a prime. Suppose

p^{e} ∥ n!,

ie p^{e} | n! but p^{e+1} ∤ n!. Then

e = [\frac{n}{p}] + [\frac{n}{p^{2}} ] + · · · .

Thus

e < \frac{n}{p} + \frac{n}{p^{2}} + ⋯

= \frac{n}{p − 1}.

Hence

∥\frac{5^{n}}{n!} ∥_{5} < 5^{−3n/4},

and so our binomial series converges in ℚ_{5}.

(b) Alternatively, we can appeal to Hensel’s Lemma.

Lemma 1 Suppose f(x) ∈ ℤ[x]; and suppose a ∈ ℤ satisfies

f(a) ≡ 0 mod p^{r}

where r > 0. Suppose also that

f′(a) ≢ 0 mod p.

Then a extends to a unique α ∈ ℤ_{p} such that

f(α) = 0,

with α ≡ a mod p^{r}.

[This is proved by showing that the solution modp^{r} extends to a unique solution modp^{r+1}, on expanding

f(x + y) = f(x) + f_{1}(x)y + f_{2}(x)y^{2} + · · · .

Here f_{1}(x) = f′(x), and the result follows on setting x = a, y = cp^{r} where c mod p is chosen so that

f(a) + f′(a)cp^{r} ≡ 0 mod p^{r+1}.]

This applies at once to the polynomial

f(x) = x^{2} − 6,

taking a = 1 with r = 1.

3. Show that the group of the elliptic curve

y^{2} = x^{3} − x^{2} + 1

over the finite field F_{7} is cyclic, and find a generator.

Answer: Let us find the finite points on the curve. The quadratic residues mod7 are: 0, 1, 2, 4. The following table is more-or-less selfexplanatory.

\begin{matrix}x & y^{2} & y \\ 0 & 1 & ±1 \\ 1 & 1 & ±1 \\ 2 & 5 & − − − \\ 3 & 5 & − − − \\ 4 = −3 & 0 & 0 \\ 5 = −2 & 3 & − − − \\ 6 = −1 & 6 & − − − \end{matrix}

Thus there are 5 finite points on the curve. Adding the point at infinity, we see that the curve is of order 6. But the only abelian group of order 6 is the cyclic group ℤ/(6).

There is just one element of order 2, namely (4, 0). There must be two elements of order 3, and two elements of order 6.

Let P = (0, 1). The slope of the tangent at the point (x, y) is

m = \frac{3x^{2} − 2x}{2y}.

Thus the slope at P is m = 0, and so the tangent is

y = 1.

This meets the curve again at the point (1, 1). Hence

2P = −(1, 1) = (1, −1).

Thus 2P ≠ −P = (0, −1). Hence P does not have order 3; so it must have order 6, ie it is a generator of the group.

4. Outline the proof that a point P = (x, y) of finite order on the elliptic

curve

y^{2} = x^{3} + ax^{2} + bx + c (a, b, c ∈ ℤ)

necessarily has integral coordinates x, y ∈ ℤ.

Answer: [The proof below does not use p-adic numbers explicitly, as I do in my notes. However, the idea is the same. In particular, we prove the result by showing that x, y are p-adic integers for each prime p, ie p does not divide the denominators of x and y.]

In homogeneous coordinates the curve has equation

Y^{2}Z = X^{3} + aX^{2}Z + bXZ^{2} + cZ^{3}.

We work in the affine patch Y ≠ 0, setting Y = 1:

Z = X^{3} + aX^{2}Z + bXZ^{2} + cZ^{3}.

Lemma 2 If ∥Z∥_{p} < 1 (ie p | Z) then ∥X∥_{p} < 1, and in fact

∥Z∥_{p} = ∥X∥_{p}^{3}.

Proof of Lemma ▷ If ∥X∥_{p} ≥ 1 then X^{3} dominates the equation, ie all

other terms have smaller p-adic value, which is impossible.

So ∥X∥_{p} < 1; and then the terms aX^{2}Z, bXZ^{2}, cZ^{3} all have p-adic value smaller then Z. Hence Z and X^{3} must have the same p-adic value. ◁

We set

E_{p^{e}} = {[X, 1, Z] : ∥X∥ ≤ p^{−e}, ∥Z∥ < 1}.

Lemma 3 Suppose P_{1}, P_{2} ∈ E_{p^{e}}. Then P_{1} + P_{2} ∈ E_{p^{e}}. Moreover, if P_{1} = [X_{1}, 1, Z_{1}], P_{2} = [X_{2}, 1, Z_{2}], P + 1 + P_{2} = [X_{3}, 1, Z_{3}] then

X_{3} ≡ X_{1} + X_{2} mod p^{3e}.

Proof of Lemma ▷ Let the line P_{1}P_{2} be

Z = MX + C.

Then

M = \frac{Z_{2} − Z_{1}}{X_{2} − X_{1}} .

Subtracting the equation for the two points, Z_{2} −Z_{1} = (X_{2}^{3} −X_{1}^{3})+a(X_{2}^{2}Z_{2} −X_{1}^{2}Z_{1})+b(X_{2}Z_{2}^{2} −X_{1}Z_{1}^{2})+c(Z_{2}^{3} −Z_{1}^{3}). Writing X_{2}^{2}Z_{2}−X_{1}^{2}Z_{1} = (X_{2}^{2}−X_{1}^{2})Z_{2}+X_{1}^{2}(Z_{2}−Z_{1}), X_{2}Z_{2}^{2}−X_{1}Z_{1}^{2} = (X_{2}−X_{1})Z_{2}^{2}+X_{1}(Z_{2}^{2}−Z_{1}^{2}), we derive

\frac{Z_{2} − Z_{1}}{X_{2} − X_{1}} = \frac{(X_{1}^{2} + X_{1}X_{2} + X_{2}^{2}) + a(X_{1} + X_{2})Z_{2} + bZ_{2}^{2}}{1 − aX_{1}^{2} − bX_{1}(Z_{1} + Z_{2}) − c(Z_{1}^{2} + Z_{1}Z_{2} + Z_{2}^{2})}

= \frac{N}{D} ,

say. Evidently

∥N∥_{p} ≤ p^{−2e}, ∥D∥_{p} = 1.

Hence

∥M∥_{p} ≤ p^{−2e}.

Since

C = Z_{1} − MX_{1},

it follows that

∥C∥_{p}lep^{−3e}.

The line P_{1}P_{2} meets the curve where MX + C = X^{3} + aX^{2}(MX + C) + bX(MX + C)^{2} + c(MX + C)^{3}. Since −[X, 1, Z] = [−X, 1, −Z], The roots of this equation are X_{1}, X_{2}, −X_{3}. Thus

X_{1} + X_{2} − X_{3} = \frac{a + 2bM + 3cM^{2}}{1 + aM + bM^{2} + cM^{3}} C.

We conclude that

X_{3} ≡ X_{1} + X_{2} mod p^{3e}.

◁

Corollary 1 If P ∈ E_{p^{e}} then X(nP) ≡ nX(P) mod p^{3e}.

Lemma 4 The only point of finite order in E_{p} is O = [0, 1, 0].

Proof of Lemma ▷ Suppose P is of order n, and suppose q is a prime factor of n. Then (n/q)P is of order q. Hence we may suppose that P is of prime order q. But

X(qP) ≡ qX(P) mod p^{3e}

It follows that

∥X(qP)∥_{p} = p^{e}

if q ≠ p, while

∥X(pP)∥_{p} = p^{e+1}.

In either case qP ≠ 0. ◁

Lemma 5 If (x, y) is of finite order then ∥x∥_{p} ≤ 1, ∥y∥_{p} ≤ 1.

Proof of Lemma ▷ Conversion from X, Z coordinates to x, y coordinates is given by

[X, 1, Z] = [X/Z, 1/Z, 1] = [x, 1, y].

Thus

y = \frac{1}{Z} .

Since P ∉ E_{p},

∥Z∥_{p} ≥ 1.

Thus

∥y∥_{p} ≤ 1.

If ∥x∥_{p} > 1 then x^{3} dominates the equation. Hence

∥x∥_{p} ≤ 1.

◁

Since this is true for all primes p, we conclude that x, y ∈ ℤ.

5. Find the order of the point (0, 0) on the elliptic curve

y^{2} − y = x^{3} − x

over the rationals ℚ. Answer: Let P = (0, 0). The tangent at the point (x, y) has slope

m = \frac{3x^{2} − 1}{2y − 1}.

In particular, the tangent at P has slope 1. Hence the tangent is

y = x.

This meets the curve again where

x^{2} − x = x^{3} − x

ie where

x = 1,

and therefore

y = 1.

Thus

2P = −(1, 1) = Q,

say. The line OQ (where O is the neutral element [0, 1, 0]) is x = 1. This meets the curve again where

y^{2} − y = 0,

ie where

y = 0.

Thus

2P = (1, 0) = R,

say. The slope at R is

m = \frac{2}{−1} = −2.

Thus the tangent is

y = −2(x − 1),

ie

y + 2x − 2 = 0.

This meets the curve again where

4(x − 1)^{2} − 2(x − 1) = x^{3} − x,

ie

x^{3} − 4x^{2} + 9x − 6.

We know that this has roots 1, 1. Hence the third root is given by

1 + 1 + x = 4,

ie

x = 2.

Thus the tangent meets the curve again at the point

S = (2, −2).

The line OS, ie x = 2, meets the curve again where

y^{2} − y = 6.

One solution is y = −2; so the other is given by

−2 + y = 1,

ie

y = 3.

Thus

2R = (2, 3) = T,

say. The slope at T is

m = \frac{11}{5}.

Let the tangent at T be

y = mx + c.

This meets the curve where

(mx + c)^{2} − (mx + c) = x^{3} − x.

Thus the tangent meets the curve again where

2 + 2 + x = m^{2}.

Evidently x is not integral. Hence T is of infinite order, and so therefore is P = (0, 0), since T = 4P.

6. Find all points of finite order on the elliptic curve

y^{2} = x^{3} − 2

over the rationals ℚ. Answer: We have

Δ = −4(−2)^{3} = 2^{5}.

By the (strong) Nagel-Lutz Theorem, a point (x, y) on the curve of finite order has integer coordinates x, y, and either y = 0 or else

y^{2} | 2^{5},

ie

y = 0, ±2, ±4.

There is no point with y = 0, since 2 is not a cube. Suppose y = ±2. Then

x^{3} − 2 = 4,

ie

x^{3} = 6.

This has no rational solution. Finally, suppose y = ±4. Then

x^{3} − 2 = 16,

ie

x^{3} = 18,

which again has no rational solution. We conclude that the only point on the curve of finite order is the neutral element 0 = [0, 1, 0], or order 1.

7. Describe carefully (but without proof) the Structure Theorem for finitelygenerated abelian groups.

How many abelian groups of order 36 (up to isomorphism) are there?

Answer: Every finitely-generated abelian group A is expressible as the direct sum of cyclic subgroups of infinite or prime-power order:

A = ℤ ⊕ ℤ ⊕ ⋯ ⊕ ℤ ⊕ ℤ/(p_{1}^{e_{1}}) ⊕ ℤ/(p_{2}^{e_{2}}) ⊕ ⋯ ⊕ ℤ/(p_{r}^{e_{r}}).

Moreover, the number of copies of ℤ, and the prime-powers p_{1}^{e_{1}}, …, p_{r}^{e_{r}} occuring in this direct sum are uniquely determined (up to order) by A.

Suppose

|A| = 36 = 2^{2} · 3^{2}.

Then the 2-component A_{2} and the 3-component A_{3} of A have orders 4 and 9. Thus

A_{2} = ℤ/(4) or ℤ/(2) ⊕ ℤ/(2),

and

A_{2} = ℤ/(9) or ℤ/(3) ⊕ ℤ/(3).

It follows that there are just 4 abelian groups of order 36, namely

ℤ/(4) ⊕ ℤ/(9) = ℤ/(36),
ℤ/(2) ⊕ ℤ/(2) ⊕ ℤ/(9) = ℤ/(18) ⊕ ℤ/(2),
ℤ/(4) ⊕ ℤ/(3) ⊕ ℤ/(3) = ℤ/(12) ⊕ ℤ/(3),
ℤ/(2) ⊕ ℤ/(2) ⊕ ℤ/(3) ⊕ ℤ/(3) = ℤ/(6) ⊕ ℤ/(6).