\documentclass[a4paper,12pt]{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{verbatim}
\usepackage{EllipticCurves-exam}
%\newtheorem{lemma}{Lemma}
%\newcommand{\norm}[1]{\|#1\|}
%\let\divides=\mid
\newenvironment{answer}{\textbf{Answer:}\em}{}
%\newenvironment{answer}{\comment}{\endcomment}
\newcommand\legendre[2]{\genfrac(){}{0}{#1}{#2}}
\addtolength{\textheight}{1cm}
\title{\includegraphics[width=3cm]{tcdarms}\\[5mm]
Course 428\\[3mm]
Elliptic Curves I}
\author{Dr Timothy Murphy}
\date{Maxwell Theatre\hfil Friday, 21 January 2000\hfil 10:15--11:45}
\pagestyle{empty}
\addtolength{\topmargin}{-2cm}
\def\C{\mathbb{C}}
\begin{document}
\maketitle
\thispagestyle{empty}
\begin{quotation}\em
\noindent
Attempt 5 questions.
(If you attempt more,
only the best 5 will be counted.)
All questions carry the same number of marks.
\end{quotation}
\begin{enumerate}
\enlargethispage{3cm}
\item %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 $\Q$.
What is $2P$?
\begin{answer}
\begin{enumerate}
\item
The line $PQ$ 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 $PQ$.
\item
The line $PQ$ is given by
\begin{gather*}
\det \begin{pmatrix}
x & y & 1\\
-2 & 3 & 1\\
2 & 5 & 1
\end{pmatrix}
= 0,\\
\intertext{ie}
-2x + 4y -16 = 0,
\intertext{ie}
y = \frac{1}{2} x + 4.
\end{gather*}
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
\begin{gather*}
-2 + 2 + x = \frac{1}{4},
\intertext{ie}
x = \frac{1}{4}.
\end{gather*}
From the equation of the tangent,
\[
y = \frac{1}{8} + 4 = \frac{33}{8}.
\]
Thus
\begin{align*}
P + Q &= -(\frac{1}{4}, \frac{33}{8})\\
&= (\frac{1}{4}, -\frac{33}{8}).
\end{align*}
\end{enumerate}
\end{answer}
\item %2
Express the 5-adic integer $2/3 \in \Z_5$ in standard form
\[
1/3 = a_0 + a_1 5 + a_2 5^2 + \cdots \qquad (0 \le a_i < 5).
\]
Does there exist a 5-adic integer x such that $x^2 = 6$?
\begin{answer}
We have
\[
\frac{2}{3} \equiv 4 \bmod 5
\]
since $3 \cdot 4 \equiv 2 \bmod 5$.
Now
\[
\frac{2}{3} - 4 = \frac{-10}{3} = 5 \frac{-2}{3}.
\]
But
\[
\frac{-2}{3} \equiv 1 \bmod 5.
\]
Thus
\[
\frac{2}{3} \equiv 4 + 1 \cdot 5 \bmod 5^2.
\]
Furthermore,
\[
\frac{-2}{3} - 1 = \frac{-5}{3} = 5 \frac{-1}{3}.
\]
But
\[
\frac{-1}{3} \equiv 3 \bmod 5.
\]
Thus
\[
\frac{2}{3} \equiv 4 + 1 \cdot 5 + 3 \cdot 5^2 \bmod 5^3.
\]
Continuing,
\[
\frac{-1}{3} - 3 = \frac{-10}{3} = 5 \frac{-2}{3}.
\]
We have been here before;
\[
\frac{-2}{3} \equiv 1 \bmod 5.
\]
Thus
\[
\frac{2}{3} \equiv 4 + 1 \cdot 5 + 3 \cdot 5^2 + 1 \cdot 5^3 \bmod 5^4.
\]
We have entered a loop;
and the pattern will repeat itself indefinitely.
We conclude that
\[
\frac{2}{3} = 4 + 1 \cdot 5 + 3 \cdot 5^2 + 1 \cdot 5^3 + 3 \cdot 5^4 + 1 \cdot 5^5 + 3 \cdot 5^6 + \cdots.
\]
Let us verify this;
the sum on the right is
\begin{align*}
4 + \frac{5}{1 - 5^2} + \frac{3\cdot 5^2}{1 - 5^2}
&= 4 + 5 \frac{1 + 15}{-24}\\
&= 4 - 5 \frac{2}{3}\\
&= \frac{2}{3}.
\end{align*}
There does exist a 5-adic integer x such that $x^2 = 6$?
Here are two ways of seeing this.
\begin{enumerate}
\item
By the binomial theorem,
\begin{align*}
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 + \cdots
\end{align*}
A $p$-adic series $\sum a_n$ converges if and only if $a_n \to 0$.
So we have to ensure that
\[
\norm{\binom{1/2}{n} 5^n}_5 \to 0.
\]
It is sufficient to show that
\[
\norm{\frac{5^n}{n!}}_5 \to 0.
\]
Let $p$ be a prime.
Suppose
\[
p^e \parallel n!,
\]
ie $p^e \mid n!$ but $p^{e+1} \nmid n!$.
Then
\[
e = \left[\frac{n}{p}\right] + \left[\frac{n}{p^2}\right] + \cdots.
\]
Thus
\begin{align*}
e &< \frac{n}{p} + \frac{n}{p^2} + \cdots\\
&= \frac{n}{p-1}.
\end{align*}
Hence
\[
\norm{\frac{5^n}{n!}}_5 < 5^{-3n/4},
\]
and so our binomial series converges in $\Q_5$.
\item
Alternatively, we can appeal to Hensel's Lemma.
\begin{lemma}
Suppose $f(x) \in \Z[x]$; and suppose $a \in \Z$ satisfies
\[
f(a) \equiv 0 \bmod p^r
\]
where $r > 0$.
Suppose also that
\[
f'(a) \not\equiv 0 \bmod p.
\]
Then $a$ extends to a unique $\alpha \in \Z_p$ such that
\[
f(\alpha) = 0,
\]
with $\alpha \equiv a \bmod p^r$.
\end{lemma}
[This is proved by showing that the solution $\bmod p^r$
extends to a unique solution $\bmod p^{r+1}$,
on expanding
\[
f(x + y) = f(x) + f_1(x) y + f_2(x) y^2 + \cdots.
\]
Here $f_1(x) = f'(x)$,
and the result follows on setting $x = a,\; y = cp^r$
where $c \bmod p$ is chosen so that
\[
f(a) + f'(a) cp^r \equiv 0 \bmod p^{r+1}.]
\]
This applies at once to the polynomial
\[
f(x) = x^2 - 6,
\]
taking $a = 1$ with $r = 1$.
\end{enumerate}
\end{answer}
\item %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.
\begin{answer}
Let us find the finite points on the curve.
The quadratic residues $\bmod 7$ are: $0,1,2,4$.
The following table is more-or-less self-explanatory.
\[
\begin{array}{c | c l}
x & y^2 & y\\
\hline
0 & 1 & \pm 1\\
1 & 1 & \pm 1\\
2 & 5 & ---\\
3 & 5 & ---\\
4 = -3 & 0 & 0\\
5 = -2 & 3 & ---\\
6 = -1 & 6 & ---
\end{array}
\]
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 $\Z/(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 \neq -P = (0,-1)$.
Hence $P$ does not have order 3;
so it must have order 6,
ie it is a generator of the group.
\end{answer}
\item %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 \qquad (a,b,c \in \Z)
\]
necessarily has integral coordinates $x,y \in \Z$.
\begin{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^2Z = X^3 + aX^2Z + bXZ^2 + cZ^3.
\]
We work in the affine patch $Y \neq 0$, setting $Y = 1$:
\[
Z = X^3 + aX^2Z + bXZ^2 + cZ^3.
\]
\begin{lemma}
If $\norm{Z}_p < 1$ (ie $p \divides Z$)
then $\norm{X}_p < 1$, and in fact
\[
\norm{Z}_p = \norm{X}_p^3.
\]
\end{lemma}
\begin{lemmaproof}
If $\norm{X}_p \ge 1$ then $X^3$ dominates the equation,
ie all other terms have smaller $p$-adic value,
which is impossible.
So $\norm{X}_p < 1$;
and then the terms $aX^2Z, bXZ^2, cZ^3$
all have $p$-adic value smaller then $Z$.
Hence $Z$ and $X^3$ must have the same $p$-adic value.
\end{lemmaproof}
We set
\[
\E_{p^e} = \{[X,1,Z]: \norm{X} \le p^{-e}, \norm{Z} < 1\}.
\]
\begin{lemma}
Suppose $P_1,P_2 \in \E_{p^e}$.
Then $P_1 + P_2 \in \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 \equiv X_1 + X_2 \bmod p^{3e}.
\]
\end{lemma}
\begin{lemmaproof}
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),\quad
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
\begin{align*}
\frac{Z_2 - Z_1}{X_2 - X_1} &= \frac{(X_1^2 + X_1X_2 + X_2^2) + a (X_1 + X_2) Z_2 + b Z_2^2}
{1 - a X_1^2 - b X_1 (Z_1 + Z_2) - c (Z_1^2 + Z_1 Z_2 + Z_2^2)}\\
&= \frac{N}{D},
\end{align*}
say.
Evidently
\[
\norm{N}_p \le p^{-2e}, \quad
\norm{D}_p = 1.
\]
Hence
\[
\norm{M}_p \le p^{-2e}.
\]
Since
\[
C = Z_1 - MX_1,
\]
it follows that
\[
\norm{C}_p le p^{-3e}.
\]
The line $P_1 P_2$ meets the curve where
\[
MX + C = X^3 + a X^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 \equiv X_1 + X_2 \bmod p^{3e}.
\]
\end{lemmaproof}
\begin{corollary}
If $P \in \E_{p^e}$ then
\[
X(nP) \equiv n X(P) \bmod p^{3e}.
\]
\end{corollary}
\begin{lemma}
The only point of finite order in $\E_p$ is $O = [0,1,0]$.
\end{lemma}
\begin{lemmaproof}
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) \equiv q X(P) \bmod p^{3e}
\]
It follows that
\[
\norm{X(qP)}_p = p^e
\]
if $q \neq p$, while
\[
\norm{X(pP)}_p = p^{e+1}.
\]
In either case $qP \neq 0$.
\end{lemmaproof}
\begin{lemma}
If $(x,y)$ is of finite order then
\[
\norm{x}_p \le 1,\quad \norm{y}_p \le 1.
\]
\end{lemma}
\begin{lemmaproof}
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 \notin \E_p$,
\[
\norm{Z}_p \ge 1.
\]
Thus
\[
\norm{y}_p \le 1.
\]
If $\norm{x}_p > 1$ then $x^3$ dominates the equation.
Hence
\[
\norm{x}_p \le 1.
\]
\end{lemmaproof}
Since this is true for all primes $p$,
we conclude that
\[
x,y \in \Z.
\]
\end{answer}
\item %5
Find the order of the point $(0,0)$ on the elliptic curve
\[
y^2 - y = x^3 - x
\]
over the rationals $\Q$.
\begin{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
\begin{gather*}
x^2 - x = x^3 - x
\intertext{ie where}
x = 1,
\intertext{and therefore}
y = 1.
\end{gather*}
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
\begin{gather*}
y^2 - y = 0,
\intertext{ie where}
y = 0.
\end{gather*}
Thus
\[
2P = (1,0) = R,
\]
say.
The slope at $R$ is
\[
m = \frac{2}{-1} = -2.
\]
Thus the tangent is
\begin{gather*}
y = -2(x-1),
\intertext{ie}
y + 2x - 2 = 0.
\end{gather*}
This meets the curve again where
\begin{gather*}
4(x-1)^2 - 2(x-1) = x^3 - x,
\intertext{ie}
x^3 - 4x^2 + 9x - 6.
\end{gather*}
We know that this has roots $1,1$.
Hence the third root is given by
\begin{gather*}
1 + 1 + x = 4,
\intertext{ie}
x = 2.
\end{gather*}
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
\begin{gather*}
-2 + y = 1,
\intertext{ie}
y = 3.
\end{gather*}
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$.
\end{answer}
\item %6
Find all points of finite order on the elliptic curve
\[
y^2 = x^3 - 2
\]
over the rationals $\Q$.
\begin{answer}
We have
\[
\Delta = -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 \mid 2^5,
\]
ie
\[
y = 0, \pm 2, \pm 4.
\]
There is no point with $y = 0$,
since 2 is not a cube.
Suppose $y = \pm 2$.
Then
\begin{gather*}
x^3 - 2 = 4,\\
\intertext{ie}
x^3 = 6.
\end{gather*}
This has no rational solution.
Finally, suppose $y = \pm 4$.
Then
\begin{gather*}
x^3 - 2 = 16,\\
\intertext{ie}
x^3 = 18,
\end{gather*}
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.
\end{answer}
\item %7
Describe carefully (but without proof)
the Structure Theorem for finitely-generated abelian groups.
How many abelian groups of order 36 (up to isomorphism) are there?
\begin{answer}
Every finitely-generated abelian group $A$ is expressible as
the direct sum of cyclic subgroups of infinite or prime-power order:
\[
A = \Z \oplus \Z \oplus \cdots \oplus \Z \oplus
\Z/(p_1^{e_1}) \oplus \Z/(p_2^{e_2}) \oplus \cdots \oplus \Z/(p_r^{e_r}).
\]
Moreover, the number of copies of $\Z$,
and the prime-powers $p_1^{e_1}, \dots, p_r^{e_r}$ occuring in this direct sum
are uniquely determined (up to order) by $A$.
Suppose
\[
\abs{A} = 36 = 2^2 \cdot 3^2.
\]
Then the 2-component $A_2$ and the 3-component $A_3$ of $A$ have orders 4 and 9.
Thus
\[
A_2 = \Z/(4) \text{ or } \Z/(2) \oplus \Z/(2),
\]
and
\[
A_2 = \Z/(9) \text{ or } \Z/(3) \oplus \Z/(3).
\]
It follows that there are just 4 abelian groups of order 36, namely
\begin{gather*}
\Z/(4) \oplus \Z/(9) = \Z/(36),\\
\Z/(2) \oplus \Z/(2) \oplus \Z/(9) = \Z/(18) \oplus \Z/(2),\\
\Z/(4) \oplus \Z/(3) \oplus \Z/(3) = \Z/(12) \oplus \Z/(3),\\
\Z/(2) \oplus \Z/(2) \oplus \Z/(3) \oplus \Z/(3) = \Z/(6) \oplus \Z/(6).
\end{gather*}
\end{answer}
\end{enumerate}
\end{document}