\input amssym.def 
\input amssym.tex
%\def\Bbb{\bf}
%\nopagenumbers
\magnification=\magstep1
%\hoffset=1truecm
%\voffset=2truecm
\baselineskip = 5.2 true mm
\def\notdiv{{\not\hskip-.5pt |\ }}
\font\frkkk=eufm10
\font\twelverm=cmr12
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\ninebf=cmbx9
\font\eightrm=cmr8
\font\sixrm=cmr6
\font\sevrm=cmr7
\font\scrpp=eusm10 
\font\frkk=eufm10
\font\deffont=cmssi10
\font\chaptitle=cmbx10 at 14 pt
\tolerance=10000
\def\sqr{\ifmmode\square\else{$\square$}\fi}
\def\square{\vcenter{
            \hrule height.1mm
            \hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
            \hrule height.1mm}}                  % This is a slimmer sqr.
%\def\sqr{$\vcenter{\hrule height .3mm
%\hbox {\vrule width .3mm height 2mm \kern 1.4mm
%\vrule width .3mm} \hrule height .3mm}$}
%
\null
%
%\vsize=19.5 true cm
%\hsize=11.5 true cm
%\vskip 5 true cm
%\def\leqslant{\le}
\def\c{{\cal C}}
\def\pk{\phi _\kappa}
\def\im{{\hbox{\sl im}}}
\def\hs{H_{\varsigma}}
\def\hpk{\hat \phi _\kappa}
\font\sc=cmssqi8 
\def\scc#1{\hbox{\sc #1}}
\def\sf{{\scc F}}
\def\pnbq{{\Bbb P}^n(\overline {\Bbb Q} )}
\def\hk{{\hat \kappa}}
\def\bq{{\overline {\Bbb Q}}}
\def\hq{{\hat q}}
\def\pv{\prod\limits_v }
\def\pnk{{\Bbb P}^n(K)}
\def\mnkvw{{\Bbb M}^n(K[{\bf v}^2,{\bf w}^2])}
\def\pnkv{{\Bbb P}^n(K[{\bf v}^2])}
\def\kj{\kappa (J)}
\def \qmods {{\Bbb Q}^*/({\Bbb Q}^*)^2}
\def \qmodss { {\Bbb Q}^*/({\Bbb Q}^*)^2 \times 
  {\Bbb Q}^*/({\Bbb Q}^*)^2 }
\def \qs{{\Bbb Q}^*}
\def \qss{({\Bbb Q}^*)^2}
\def\bbQ{\Bbb Q}
\def\bbF{\Bbb F}
\def\bbZ{\Bbb Z}
\def\bbR{\Bbb R}
\def\bbC{\Bbb C}
%
\chaptitle
\noindent
\centerline{Elliptic Curves. Solutions to Sheet 1.}
\rm
\par
\bigskip
\noindent {\bf 1.}
\noindent {\bf (a).} The only points on $Y^2 = X^3 + 2 X$ over
$\bbF_5$ are: ${\bf o}, (0,0)$. The group table is
the same as that of $C_2$ (``cyclic~2'' group; i.e. the integers
modulo~2 under addition), with $0,1$ replaced by ${\bf o}, (0,0)$,
respectively. 
\par
\noindent {\bf (b).} The only points on $Y^2 = X^3 + 1$ over
$\bbF_5$ are: ${\bf o}, (0,1), (0,4), (4,0), (2,2), (2,3)$. The
point~$(2,2)$ has order~6, and
the group table is the same as that of $C_6$
(``cyclic~6'' group; i.e. the integers 
modulo~6 under addition), with $0,1,2,3,4,5$ replaced by
${\bf o}, (2,2), (0,4), (4,0), (0,1), (2,3)$, respectively.
Note that it's also correct to say that the group is $C_2 \times C_3$,
since $C_2\times C_3$ is isomorphic to $C_6$.
\medskip
\noindent {\bf 2.} We have: $2YY' = 3X^2 + 4$, and so the slope
at the point~$(2,4)$ is: $(3\cdot 2^2 + 4)/(2\cdot 4) = 2$. 
The line tangent to the curve at~$(2,4)$ is: $Y=2X$.
The $x$-coordinate of the third point of intersection is
therefore: $2^2 - 2 - 2 = 0$, with $y$-coordinate $y=2\cdot 0 = 0$.
Hence, $(2,4) + (2,4) + (0,0) = {\bf o}$, and so
$(2,4) + (2,4) = (0,-0) = (0,0)$. Now, note that we always
have $-(x,y) = (x,-y)$ and so $-(0,0) = (0,0)$, giving: $2(0,0) = {\bf o}$.
Hence, $4(2,4) = 2(0,0) = {\bf o}$. Also, check that
$3(2,4) = 4(2,4) - (2,4) = -(2,4) = (2,-4)$. Summarising:
the first~4 multiples of~$(2,4)$ are: $1(2,4) = (2,4),\,
2(2,4) = (0,0),\, 3(2,4) = (2,-4),\, 4(2,4) = {\bf o}$, and
so~4 is the smallest positive multiple of $(2,4)$
equal to~{\bf o}.
\medskip
\noindent {\bf 3.} 
\par\noindent {\bf (a).} Case 1. $m$ is odd. The birational
transformation $(X,Y) \mapsto (X/f_m , Y/f_m^{(m+1)/2})$ [with
inverse transformation: $(X,Y) \mapsto (Xf_m , Yf_m^{(m+1)/2})$]
maps the given curve to: $f_m^{(m+1)} Y^2 = f_m^{(m+1)} X^m + \ldots + f_0$,
which is the same as: $Y^2 = X^m + c_{m-1} X^{m-1} + \ldots + c_0$,
where $c_i = f_i/f_m^{m+1-i} \in \bbQ$ [N.B. our birational
transformation is legitimate,
since $(m+1)/2$ is an integer]. So, our new right hand side is monic 
and is still defined over~$\bbQ$. Now, write each $c_i = n_i/d_i$,
where each $n_i,d_i\in \bbZ$, with each $n_i,d_i$ coprime.
Let $d$ be the least common multiple of $d_0,\ldots d_{(m-1)}$;
that is to say, $d$ is the smallest integer divisible by all
of the denominators of the coefficients~$c_i$. Now, the
birational
transformation $(X,Y) \mapsto (Xd^2 , Yd^m)$ [with 
inverse transformation: $(X,Y) \mapsto (X/d^2 , Y/d^m)$] maps
to the curve: $Y^2/d^{2m} = X^m/d^{2m} + c_{m-1} X^{m-1}/d^{2m-2}
\ldots + c_0$, which is the same as:
$Y^2 = X^m + g_{m-1} X^{m-1} + \ldots + g_0$, where $g_i = c_i d^{2(m-i)}$.
But now, each $d_i | d$ and so each $c_i d \in \bbZ$, giving that
each $g_i \in \bbZ$, as required. 
\par Case 2. $f_m$ is a square. Let $w$ be such that
$f_m = w^2$. The birational
transformation $(X,Y) \mapsto (X , Y/w)$ [with 
inverse transformation: $(X,Y) \mapsto (X, Yw)$] 
maps the given curve to: $f_m Y^2 = f_m X^m + \ldots + f_0$, 
which is the same as: $Y^2 = X^m + c_{m-1} X^{m-1} + \ldots + c_0$, 
where $c_i = f_i/f_m \in \bbQ$. We are again in the situation where
our right hand side is monic
and is still defined over~$\bbQ$. So now apply the same second
birational transformation as in Case~1.
\par\noindent {\bf (b).} The birational transformation
$(X,Y) \mapsto (5X , 5^2Y )$ [with
inverse $(X,Y) \mapsto ((1/5)X , (1/5^2)Y )$] maps the given
curve to the curve: $Y^2 = X^3 + 75 X^2 + 625$.
The birational transformation
$(X,Y) \mapsto (X  + 25 , Y )$ [with 
inverse $(X,Y) \mapsto (X  - 25 , Y )$] maps this to
the curve: $Y^2 = X^3 - 1875 X + 31875$, as required.
\medskip
\noindent {\bf 4.}
\par\noindent {\bf (a).} Since $p \equiv 2$~(mod~$3$),
we have $\hbox{gcd}(3,p-1) = 1$,
and so there exist $\lambda, \mu \in \bbZ$ such that
$3\lambda + (p-1)\mu = 1$. For any $x,y\in\bbF_p^*$,
we have $x^{p-1} = y^{p-1} = 1$ [by Fermat's Little Theorem],
and so:
$$ x^3 = y^3 \Rightarrow 
\bigl( x^3 \bigr)^\lambda \cdot 1^\mu
= \bigl( y^3 \bigr)^\lambda \cdot 1^\mu
\Rightarrow
\bigl( x^3 \bigr)^\lambda \cdot \bigl(x^{p-1}\bigr)^\mu
= \bigl( y^3 \bigr)^\lambda \cdot \bigl(y^{p-1}\bigr)^\mu
$$
$$
\ \ \ \ \ \Rightarrow x^{ 3\lambda + (p-1)\mu } 
= y^{ 3\lambda + (p-1)\mu } 
\Rightarrow x = y.
$$
Thus the map $x \mapsto x^3$ is injective on $\bbF_p^*$
and so is a bijection. Since $0^3 = 0$, the map is
also a bijection on $\bbF_p$.
Now, rearrange the equation
of the curve as: $X^3 = Y^2 - A$. We see that, for
each $Y = 0,\ldots, p-1$ in $\bbF_p$, there is precisely
one $X \in \bbF_p$ such that $X^3 = Y^2 - A$, giving
rise to a total of precisely~$p$ affine points, which
becomes $p+1$ points when we include the point at infinity.
\smallskip
\par\noindent {\bf (b).}
Since $p\equiv 3$~(mod~$4$), we have that $\bigl( {-1 \over p} \bigr)
= -1$ [i.e.\ $-1$ is not congruent to a square mod~$p$].
First note that $X=0$ gives rise to precisely one point~$(0,0)$.
Now, pair each $X\in\bbF_p^*$ with its negative $-X$ mod~$p$.
If $X(X^2 + B) = 0$ then the pair $X,-X$ gives rise to precisely
two points: $(X,0),(-X,0)$. If $X(X^2 + B) \not= 0$
then one of $X(X^2 + B)$ and $-X(X^2 + B)$ will be a nonzero
quadratic residue mod~$p$ and the other will be
a quadratic nonresidue mod~$p$ [using the fact that $-1$
is a quadratic nonresidue mod~$p$ and the standard property
of Legendre symbols that: $\bigl( {mn \over p} \bigr)
\bigl( {m \over p} \bigr) \bigl( {n \over p} \bigr)$].
Whichever one is a nonresidue will contribute no points;
which one is a residue will contribute two points:
$(X,Y),(X,-Y)$. In all cases, each pair $X,-X$ will contribute
two points. This gives rise to a total of precisely~$p$ affine points, which
becomes $p+1$ points when we include the point at infinity.
%\medskip
%\noindent {\bf 5.}
%\par\noindent {\bf (a).} We first solve for $g_1,g_0$ and $h_1,h_0$
%such that $Q(X) = (X^2 + g_1X + g_0)^2 + (h_1X + h_0)$. Equating
%coefficients of $X^3$ forces $g_1 = f_3/2$. Successiviely equating
%coefficients of $X^2,X^1,X^0$ now solves for $g_0,h_1,h_0$,
%giving:
%$$ g_1 = f_3/2,\ g_0 = (4f_2-f_3^2)/8,\ h_1 = f_1 - f_3(4f_2-f_3^2)/8,\
%h_0 = f_0 - (4f_2-f_3^2)^2/64.
%$$
%\noindent Now define $G(X) = X^2 + g_1 X + g_0$ and $H(X) =
%h_1 X + h_0$, where $g_1,g_0,h_1,h_0$ are as in the above
%equation, and we see that indeed $Q(X) = G(X)^2 + H(X)$.
%Our curve can be written as: $(Y + G(X))(Y-G(X)) = H(X)$.
%The birational transformation $(X,Y) \mapsto (Y+G(X),
%X(Y+G(X))$ [that is: $(X,Y) \mapsto (T,S)$, given in
%the hint] has inverse $(X,Y) \mapsto (Y/X, X - G(Y/X) )$
%and transforms the given curve to: $ X ( X - 2 G(Y/X) ) = H(Y/X) $.
%After multiplying both sides by~$X$ and expanding, this
%can be rewritten as:
%$$ 2Y^2 + 2g_1XY + h_1Y = X^3 - 2g_0 X^2 - h_0 X.$$ 
%[You could write this as: $(Y + G(X))(Y-G(X)) = H(X)$ $\leftrightarrow$
%$T( T - 2 G(S/T) ) = H(S/T)$ [where $T = Y + G(X),\ S = X(Y + G(X)),\
%X = S/T,\ Y = T - G(S/T)]$, which in turn is: 
%$2S^2 + 2g_1 TS + h_1 S = T^3 - 2g_0 T^2 - h_0T$,
%if you prefer].
%One can now easily proceed
%to remove the term $2g_1XY$ by $(X,Y) \mapsto (X,Y+g_1X/2)$
%and the term $h_1Y$ by $(X,Y) \mapsto (X,Y+h_1/4)$, giving
%the curve: $Y^2 = (1/2) X^3 + \ldots$. Finally, remove the
%$X^2$ term and then make the right hand side monic \& defined over~$\bbZ$, 
%exactly as in Question~1~(a).
%\par\noindent {\bf (b).} First apply to $\c_1$ the birational transformation
%$(X,Y)\mapsto (1/X , Y/X^2)$ [self-inverse] which maps $\c_1$
%to: $Y^2 = 9 X^4 + 2$. The map $(X,Y) \mapsto (X,Y/3)$
%[with inverse $(X,Y) \mapsto (X,3Y)$] maps this to
%$Y^2 = X^4 + 2/9$. In the notation of part~(a),
%we can take $G(X) = X^2$ and $H(X) = 2/9$, and so $g_1=g_0=h_1=0$
%and $h_0 = 2/9$. The curve is therefore birationally
%equivalent to: $ 2Y^2 = X^3 - (2/9)X$; that is, $Y^2 = (1/2)X^3 - (1/9)X$.
%We finally apply $(X,Y) \mapsto (18X , 108Y)$
%[with inverse $(X,Y) \mapsto (X/18 , Y/108)$], which maps this
%curve to: $(Y/108)^2 = (1/2)(X/18)^3 - (1/9)(X/18)$, which is
%the same as: $Y^2 = X^3 - 72X$, as required. 
%\par
%For $\c_2$, the important thing to recognise is that
%it has the $\bbQ$-rational point $(1,3)$, which allows us
%to make the constant term a square after a linear change in~$X$.
%Namely, $(X,Y) \mapsto (X-1,Y)$ [with inverse $(X,Y) \mapsto (X+1,Y)$]
%maps $\c_2$ to the curve: $Y^2 = 2(X+1)^4 + 7$; that is,
%$Y^2 = 2X^4 + 8X^3 + 12X^2 + 8X + 9$. Now, $(X,Y) \mapsto (1/X,
%Y/X^2)$ [self-inverse] maps this to
%$Y^2 = 9X^4 + 8X^3 + 12X^2 + 8X + 2$. Since the coefficient
%of~$X^4$ is now a square, we can clearly proceed
%as for $\c_2$ to get the curve in the required form.
%\par Although the question does not require it, here in fact (for those
%who are curious)
%is a series of birational transformations which transform
%$Y^2 = 9X^4 + 8X^3 + 12X^2 + 8X + 2$ to the form $Y^2 = X^3 + AX +B$.
%This gives you an idea of how large the numbers
%can become (although the coefficients of the final
%answer aren't too bad).
%In the notation of part~(c), we have: $g_1 = 4/9, g_0 = 46/81,
%h_1 = 280/729, h_0 = -658/6561$, and so our curve is
%birationally equivalent to: $Y^2 +(4/9)XY +(140/729)Y
%= (1/2)X^3 - (46/81)X^2 + 329/6561$.
%One now removes the $XY$ and $Y$ terms by the
%map $(X,Y) \mapsto (X, Y + (2/9)X + 70/729)$
%[with inverse: $(X,Y) \mapsto (X, Y - (2/9)X - 70/729)$],
%which birationally transforms this curve to the curve:
%$Y^2 = (1/2) X^3 - (14/27)X^2 + (203/2187)X + 4900/531441$.
%Now apply: $(X,Y)\mapsto (X-28/81,Y)$ [with inverse
%$(X,Y)\mapsto (X+28/81,Y)$], which maps this curve
%to the curve: $Y^2 = (1/2)X^3 - (7/81)X$. Finally, the
%map: $(X,Y) \mapsto (18X, 108Y)$ [with inverse
%$(X,Y) \mapsto (X/18, Y/108)$] maps this to
%the curve: $Y^2 = X^3 - 56X$, which is in the required
%form. In summary: $\c_2 : Y^2 = 2X^4 + 7$  is birationally
%equivalent to $Y^2 = X^3 - 56X$.
%\par\noindent {\bf (c).} First, the map $(X,Y) \mapsto (X,Y/i)$
%[with inverse: $(X,Y) \mapsto (X,iY)$]
%maps the given curve to the curve: $Y^2 = X^4 + 1$. In the notation
%of part~(a), we can take $G(X) = X^2$ and $H(X) = 1$, so that
%our curve can be birationally transformed over~$\bbQ$ to
%$2Y^2 = X^3 - X$; that is: $Y^2 = (1/2)X^3 - (1/2)X$.
%Finally, applying $(X,Y) \mapsto (2X, 4Y)$
%[with inverse: $(X,Y) \mapsto (X/2, Y/4)$] birationally
%transforms this curve to: $Y^2 = X^3 - 4X$, as required.
%\par It is not possible to birationally transform over $\bbR$
%the curve $Y^2 = -X^4 - 1$
%to the form $Y^2 = X^3 + AX + B$, since any such birational
%transformation would give a map between the $\bbR$-rational
%points of the two curves; but the second curve has
%infinitely many $\bbR$-rational points (take all $X$ sufficiently
%large, e.g. all $X > 2\hbox{max}(1,|A|,|B|)$), whereas
%the first curve has no $\bbR$-rational points.
%[Note that this also implies that there is no such birational
%transformation over~$\bbQ$, either.]
%The curves $Y^2 = -X^4 - 1$
%and $Y^2 = X^3 - 4X$ are called {\it twists} of each
%other, since they are both defined over~$\bbQ$, are birationally
%equivalent over~$\bbC$, but are not birationally 
%equivalent over~$\bbQ$].
%\par
%Over $\bbQ (\sqrt{-2})$, the curve $Y^2 = -X^4 - 1$ has the
%$\bbQ (\sqrt{-2})$-rational point $(1,\sqrt{-2})$. Applying
%the transformation $(X,Y) \mapsto (X-1, Y)$
%[with inverse $(X,Y) \mapsto (X+1, Y)$] we get:
%$Y^2 = -X^4 - 4X^3 - 6X^2 - 4X - 2$. Now, applying
%$(X,Y) \mapsto (1/X , Y/X^2)$ [self-inverse], we get:
%$Y^2 = -2 X^4 - 4X^3 - 6X^2 - 4X - 1$. Now, we apply
%$(X,Y) \mapsto (X, Y/\sqrt{-2})$
%[with inverse $(X,Y) \mapsto (X, Y\sqrt{-2})$] to get:
%$Y^2 = X^4 + 2X^3 +3X^2 + 2X + 1/2$. From part~(a), we can
%now say that this is birationally equivalent (over~$\bbQ$
%and so over $\bbQ (\sqrt{-2})$) to a curve
%of the form $Y^2 = X^3 + AX + B$, with $A,B\in \bbZ$.
%\medskip
\medskip\noindent {\bf 5.}
\par\noindent {\bf (a).} $(2,0) + (-(2,0)) = {\bf o}$,
where $-(2,0)$ is the inverse of $(2,0)$; but we know
that $-(2,0) = (2,-0) = (2,0)$ and so $(2,0) + (2,0) = {\bf o}$;
that is, $(2,0)$ is of order~$2$, as required.
\par\noindent {\bf (b).} In general, a point $(x,y)$
on $Y^2 = X^3 + f_2X^2 + f_1X + f_0$
has inverse: $(x,-y)$  and so $(x,y)$ is of order~2
exactly when $(x,y) + (x,y) = {\bf o} \iff (x,y) = (x,-y)$.
But $y=-y$ precisely when $y=0$. So, we see that all points
of order~2 are of the form~$(x,0)$ where~$x$ is a root
of the cubic $X^3 + f_2X^2 + f_1X + f_0$. There are at
most~3 such points over any field, since a cubic has
at most 3~roots in any field. In the complex numbers, of course,
there will always be exactly~3 such points.
Applying this to the curve $Y^2 = X(X^2-3)$, we see that $X(X^2 - 3)$
has one $\bbQ$-rational root $X=0$, giving $(0,0)$
as the only $\bbQ$-rational point of order~2; the other
two roots give the points $(\sqrt{3}, 0)$ and $(-\sqrt{3},0)$,
which are the remaining two $\bbC$-rational points of order~2.
The curve $Y^2 = X^3 - 7$ has no $\bbQ$-rational point of order~2
(since $X^3 - 7$ has no $\bbQ$-rational roots); over~$\bbC$,
there are the 3~points of order~2 given by:
$(\omega_1,0),(\omega_2,0),(\omega_3,0)$, where
$\omega_k = 7^{1/3}e^{2\pi i k /3}$, for $k=0,1,2$.
Finally, the curve $Y^2 = X(X-1)(X-7)$ has the points of
order~2: $(0,0),(1,0),(7,0)$ all of which are
both $\bbC$-rational and $\bbQ$-rational.
Group structures of the $2$-torsion groups over~$\bbQ$ for
the three curves are clearly: $C_2, C_1$ and $C_2 \times C_2$,
respectively (since all members except~{\bf o} have order~2). 
\medskip
\noindent {\bf 6.} Using $2YY' = 3X^2$, we see that the
slope of the curve at~$(0,2)$ is $3\cdot 0^2 / (2\cdot 2) = 0$,
and so the tangent to the curve at $(0,2)$ is
the line: $Y=2$. The $x$-coordinate of the third point of
intersection is then: $0^2 - 0 - 0 = 0$, with corresponding
$y$-coordinate~$2$. In summary: The line $Y=2$ intersects
the curve at $(0,2)$ with multiplicity~3. Hence:
$(0,2) + (0,2) + (0,2) = {\bf o}$, and so: $3(0,2) = {\bf o}$.
But, $1(0,2) = (0,2)$ and $2(0,2) = (0,-2)$, and so~$3$
is the smallest $k \ge 1$ such that $k(0,2) = {\bf o}$;
that is, $(0,2)$ has order~$3$.
\medskip
\noindent
{\bf 7.}
\par\noindent {\bf (a).} As usual, $-(\alpha , 0) = (\alpha , 0)$,
and so $(\alpha , 0) + (\alpha , 0) = {\bf o}$; that is, $(\alpha , 0)$
is a point of order~2, as required.
We now compute $(x',y')
= (x,y) + (\alpha , 0)$. First, the line through $(x,y)$ and
$(\alpha , 0)$ is: $Y = (y/(x-\alpha )) (X-\alpha)$. Substituting
this into the curve gives: $X^3 - (m^2 + \alpha - a) X^2 + \ldots = 0$,
where $m = y/(x-\alpha )$. The sum of the roots of this cubic
is: $m^2 + \alpha - a$, and so the $x$-coordinate of the
third point of intersection is given by:
$x' = m^2 + \alpha - a - x - \alpha  = m^2 - x - a
= y^2/(x-\alpha)^2 - x - a = (\alpha x + a\alpha + b)/(x-\alpha)$.
So, we have:
$$ T : x \mapsto {\alpha x + a\alpha + b\over x-\alpha}.$$
\noindent We now check $T^2(x) = T(T(x))$, which is:
$$  T : x \mapsto
{\alpha (\alpha x + a\alpha + b)/(x-\alpha) + a\alpha + b
\over (\alpha x + a\alpha + b)/(x-\alpha)-\alpha}.$$  
\noindent On multiplying numerator and denominator by
$x-\alpha$ and simplifying, we get:
$(\alpha^2 + a\alpha + b)x/(\alpha^2 + a\alpha + b)x$,
which is~$x$, as required [Note that $\alpha^2 + a\alpha + b \not= 0$,
since the cubic $(X-\alpha)(X^2 + aX + b)$ has distinct roots].
\par\noindent {\bf (b).} For~$Y^2 = (X-\alpha_1)(X-\alpha_2)
(X-\alpha_3)$, the formula for~$T_1$ is the same as for~$T$
in part~(a), but with $\alpha,a,b$ replaced by $\alpha_1,
-\alpha_2 - \alpha_3, \alpha_2\alpha_3$, respectively. That is:
$$ T_1 : x \mapsto {\alpha_1 x - \alpha_1\alpha_2 - \alpha_1\alpha_3
+ \alpha_2\alpha_3 \over x - \alpha_1}.$$
\noindent The formula for $T_2$ is the same as for~$T_1$, but
with $\alpha_1,\alpha_2,\alpha_3$ replaced by $\alpha_2,\alpha_3,\alpha_1$,
respectively. The formula for $T_3$ is the same as for~$T_2$, but (again)  
with $\alpha_1,\alpha_2,\alpha_3$ replaced by $\alpha_2,\alpha_3,\alpha_1$, 
respectively. These are then: 
$$ T_2 : x \mapsto {\alpha_2 x - \alpha_2\alpha_3 - \alpha_2\alpha_1
+ \alpha_3\alpha_1 \over x - \alpha_2}.$$
$$ T_3 : x \mapsto {\alpha_3 x - \alpha_3\alpha_1 - \alpha_3\alpha_2
+ \alpha_1\alpha_2 \over x - \alpha_3}.$$
On computing $T_1 T_2 (x) = T_1 (T_2 (x))$, and
simplifying (by removing a common factor of $\alpha_1 - \alpha_2$
from the numerator and denominator), we get the formula for~$T_3$;
that is: $T_1 T_2 = T_3$. The formula for $T_3$ is invariant
under $\alpha_1 \leftrightarrow \alpha_2$ and so $T_2 T_1 = T_3$, also.
Hence $T_1 T_2 = T_3 = T_2 T_1$, and so $T_1$ and $T_2$ commute.
By symmetry, $T_1$ and $T_3$ commute, as do $T_2$ and $T_3$.
Furthermore, $T_1 T_2 T_3 = T_3^2$ (since $T_1T_2 = T_3$), and we know
from part~(a) that $T_3^2 : x\mapsto x$; hence $T_1 T_2 T_3 : x\mapsto x$,
as required.
\par Finally, the fixed points of $T_1$ are the solutions
to $T_1(x) = x$, that is:
$$
\alpha_1 x - \alpha_1\alpha_2 - \alpha_1\alpha_3
+ \alpha_2\alpha_3 =  (x - \alpha_1) x,$$
which has solutions: 
$$ x_1 = \alpha_1 + \sqrt{(\alpha_1 - \alpha_2)(\alpha_1 - \alpha_3)},
\ \
x_2 = \alpha_1 - \sqrt{(\alpha_1 - \alpha_2)(\alpha_1 - \alpha_3)}.
$$
Computing $T_2(x_1)$ and $T_2(x_2)$ gives $x_2,x_1$, respectively.
\medskip
\noindent {\bf 8.}
{\bf (a).} Let $L$ be the tangent line to the curve
at~$P$, and let~$R$ be the third point of intersection; that is,
the line and the curve meet at $P,P,R$. Then $P+P+R = {\bf o}$.
Then, $3P = {\bf o} \iff R=P \iff$ $L$ intersects $\cal E$ only at~$P$
(3 times). 
\par\noindent {\bf (b).} The Hessian matrix is:
$$ \pmatrix{ -6X_0 & 0 & -2AX_2 \cr
              0 & 2X_2 & 2X_1 \cr
              -2AX_2 & 2X_1 & -2AX_0 - 6BX_2 \cr}.
$$
\noindent  The determinant is: 
\par $-6X_0\bigl(
2X_2 ( -2AX_0 - 6BX_2 ) - (2X_1)(2X_1) \bigr)
 -2AX_2 \bigl( 0 - (2X_2)(-2AX_2) \bigr)$
\par
$= 8(3AX_0^2X_2 + 9BX_0X_2^2 + 3X_0X_1^2 - A^2 X_2^3)$. 
\par\noindent
The only projective point $(X_0,X_1,X_2)$ on the curve with
$X_2=0$ is $(0,1,0) = {\bf o}$, for which the statement
is true, since $3{\bf o} = {\bf o}$ and $(X_0,X_1,X_2) = (0,1,0)$
makes the Hessian determinant~$0$. When $X_2 \not= 0$, we can
write everything in affine form, with $x = X_0/X_2$ and $y = X_1/X_2$, 
when we see that the Hessian determinant (after dividing
through by~$8 X_2^3$) is~0 exactly when:
\medskip
\hskip 5 cm $3Ax^2 + 9Bx + 3xy^2 - A^2 = 0$.\hfill (1)
\medskip
\noindent  
Also, the point $P  = (x,y)\not= {\bf o}$, written in affine form,
has order~3 exactly when $2(x,y) = (x,-y)$ which happens
if and only if the $x$-coordinate of $2(x,y)$ is~$x$. But, as usual,
the $x$-coordinate of $2(x,y)$ is $m^2 - 2x$,
where $m = (3x^2 + A)/(2y)$  (note that $y\not= 0$ here,
since $y=0$ would make $P$ be of order~$2$). 
%So, $P$ is of order~$3$ exactly when
So, $P$ being of order~$3$ implies
$\bigl( (3x^2 + A)/(2y) \bigr)^2 - 2x = x$,
that is:
\medskip
\hskip 5 cm $-9 x^4  - 6 A x^2 + 12xy^2 - A^2 = 0$. \hfill (2)
\medskip
\noindent
Finally, we use the fact the $(x,y)$ is a point on the
curve, so that $y^2 = x^3 + Ax + B$, and so we can replace
$y^2$ by $x^3 + Ax + B$ in equations~(1),(2). This makes
both equations become the same equation:
$3x^4 + 6Ax^2 + 12 B x - A^2 = 0$, as required.  
%\smallskip
%\par{\bf (c).} The above showed that $x$ is the $x$-coordinate
%of a point of order~$3$ precisely when $3x^4 + 6Ax^2 + 12 B x - A^2 = 0$.
%Now, the discriminant of $q(x) = 3x^4 + 6Ax^2 + 12 B x - A^2 = 0$
%is the resultant $q(x)$ and $q'(x)$, which is
%the determinant of the matrix:
%$$ \pmatrix{ 0 & 0 & 3 & 0 & 6A & 12B & -A^2 \cr
%             0 & 3 & 0 & 6A & 12B & -A^2 & 0 \cr
%	     3 & 0 & 6A & 12B & -A^2 & 0 & 0 \cr
%	     0 & 0 & 0 & 12 & 0 & 12A & 12B \cr
%	     0 & 0 & 12 & 0 & 12A & 12B & 0 \cr
%	     0 & 12 & 0 & 12A & 12B & 0 & 0 \cr
%	     12 & 0 & 12A & 12B & 0 & 0 & 0 }
%$$
%giving: $2^8 3^4 (4 A^3 + 27 B^2 )^2$.
%Since the original curve is an elliptic curve, we know
%that $4 A^3 + 27 B^2 \not= 0$, and since $\hbox{Char }K \not= 2,3$,
%we know that the above discriminant is nonzero, and so
%the roots of the quartic $x_i$ (for $i=1,\ldots ,4$) are distinct.
%Each $x_i$ gives rise to two distinct points $(x_i,y_i), (x_i,-y_i)$
%of order~$3$ [note that $y_i\not= 0$, since the points are
%not of order~$2$], giving $8$ points of order~$3$ in~$\overline K$.
%Together with {\bf o}, this gives $9$ points that are $3$-torsion.
\smallskip
\par{\bf (c).} By part~(b), 
the $x$-coordinate of any point of order~3 must
be a root of the quartic $3x^4 + 6Ax^2 + 12 B x - A^2$,
which has at most~4 roots $x_1,\ldots ,x_4$.
Each~$x_i$ gives rise to at most two points $(x_i,y_i), (x_i,-y_i)$
on the curve, giving at most $8$ points of order~$3$.
Together with {\bf o}, this gives at most $9$ points that are $3$-torsion.
\medskip
\vfil \eject %\end
\input amssym.def 
\input amssym.tex
%\def\Bbb{\bf}
%\nopagenumbers
%\magnification=\magstep1
%\hoffset=1truecm
%\voffset=2truecm
\baselineskip = 5.2 true mm
\font\frkkk=eufm10
\font\twelverm=cmr12
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\ninebf=cmbx9
\font\eightrm=cmr8
\font\sixrm=cmr6
\font\scrpp=eusm10 
\font\frkk=eufm10
\font\deffont=cmssi10
\font\chaptitle=cmbx10 at 14 pt
\tolerance=10000
\def\sqr{\ifmmode\square\else{$\square$}\fi}
\def\square{\vcenter{
            \hrule height.1mm
            \hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
            \hrule height.1mm}}                  % This is a slimmer sqr.
%\def\sqr{$\vcenter{\hrule height .3mm
%\hbox {\vrule width .3mm height 2mm \kern 1.4mm
%\vrule width .3mm} \hrule height .3mm}$}
%
\null
%
%\vsize=19.5 true cm
%\hsize=11.5 true cm
%\vskip 5 true cm
%\def\leqslant{\le}
\def\c{{\cal C}}
\def\e{{\cal E}}
\def\pk{\phi _\kappa}
\def\im{{\hbox{\sl im}}}
\def\hs{H_{\varsigma}}
\def\hpk{\hat \phi _\kappa}
\font\sc=cmssqi8 
\def\scc#1{\hbox{\sc #1}}
\def\sf{{\scc F}}
\def\pnbq{{\Bbb P}^n(\overline {\Bbb Q} )}
\def\hk{{\hat \kappa}}
\def\bq{{\overline {\Bbb Q}}}
\def\hq{{\hat q}}
\def\pv{\prod\limits_v }
\def\pnk{{\Bbb P}^n(K)}
\def\mnkvw{{\Bbb M}^n(K[{\bf v}^2,{\bf w}^2])}
\def\pnkv{{\Bbb P}^n(K[{\bf v}^2])}
\def\kj{\kappa (J)}
\def \qmods {{\Bbb Q}^*/({\Bbb Q}^*)^2}
\def \qmodss { {\Bbb Q}^*/({\Bbb Q}^*)^2 \times 
  {\Bbb Q}^*/({\Bbb Q}^*)^2 }
\def \qs{{\Bbb Q}^*}
\def \qss{({\Bbb Q}^*)^2}
\def\bbQ{{\Bbb Q}}
\def\bbF{{\Bbb F}}
\def\bbZ{{\Bbb Z}}
\def\bbR{{\Bbb R}}
\def\bbC{{\Bbb C}}
\def\Q{{\Bbb Q}}
\def\F{{\Bbb F}}
\def\Z{{\Bbb Z}}
\def\R{{\Bbb R}}
\def\C{{\Bbb C}}
%
\chaptitle
\noindent
\centerline{Elliptic Curves. Solutions to Sheet 2.}
\rm
\bigskip
\noindent {\bf 1.} {\bf (a).}
Let $x,y\in K$ be such that $|x| \not= |y|$, without loss of generality,
say that $|x| < |y|$. Since $K$ is non-Archimedean, we
know that $|x \pm y | \leqslant \hbox{max}( |x|, |y| ) = |y|$,
and so it is sufficient to show that 
$|x \pm y | \not< |y|$. Imagine $|x \pm y | < |y|$; then
$|y| = |(x \pm y) - x| \leqslant \hbox{max}(|x \pm y |, |x|) < |y|$,
a contradiction, as required. [Note that an immediate
consequence is the implication:
$| u \pm v | < | u | \Rightarrow |u| = |v|$].
\par\noindent {\bf (b).}
Let $x_1, \ldots , x_n \in K$
be such that
$|x_\ell| > |x_i|$ for all $i\not= \ell$.
Let $x = x_1 + \ldots + x_{\ell-1} + x_{\ell+1} + \ldots + x_n$
and let $y = x_\ell$.
Then $|x| \leqslant 
\hbox{max}(|x_i| : 1\leqslant i \leqslant n, i\not= \ell\} < |y|$
and so: 
$|x_1 + \ldots + x_n| = |x + y| = |y| = |x_\ell|$, by part~(a).
\smallskip
\par\noindent {\bf (c).} 
Since $K,|\ |$ satisfies the triangle inequality $|x+y| \leqslant |x|+|y|$,
we can apply the standard trick from first year Analysis:
$|x| \leqslant |(x - y) + y| \leqslant |x-y| + |y|$
to give: $|x| - |y| \leqslant |x-y|$; similarly
$|y| - |x| \leqslant |x-y|$, and so: $|\ |x| - |y|\ |_\infty 
\leqslant | x - y |$.
If $s_n \rightarrow s$
in $K,|\ |$ then $|s_n - s| \rightarrow 0$ in $\R$,
and so $|\ |s_n| - |s|\ |_\infty \leqslant | s_n - s | \rightarrow 0$,
giving $|s_n| \rightarrow |s|$
in $\bbR, |\ |_\infty$, as required. 
\par
%Suppose
%that $s_n \rightarrow s \not= 0$ in~$\bbQ_p$.
%Then $|s| = p^r$ for some $r \in \Z$. Let 
%$\epsilon = \hbox{min}(p^r - p^{r-1}, p^{r+1} - p^r) > 0$. Then
%there exists $N$ such that, for all $n > N$, 
%$|\ |s_n|_p - |s|_p\ |_\infty < \epsilon$. But, since any $|s_n|_p$
%is an integer power of~$p$, there are no possible $|s_n|_p$
%within $\epsilon$ of $|s|_p$ apart from $|s|_p$ itself,
%and so $|s_n|_p = |s|_p$, as required. {\it Alternatively:}
Suppose $s \not= 0$; then $|s| > 0$ and taking $\epsilon = |s|$,
there exists $N$ such that $|s_n - s| < |s|$ for all $n > N$,
so that $|s_n| = |s|$ for all $n > N$ (since if $|s_n| \not= |s|$
then~(a) would give $|s_n - s| = \hbox{max}(|s_n|,|s|)
\geqslant |s|$, a contradiction).
%\medskip
%\smallskip
%\par\noindent {\bf (d).}
%Let $\sum_{n=1}^\infty x_n$
%converge to $x \in K, |\ |$. From lectures, we know
%that $|x_n| \rightarrow 0$ in $\R$. If all $x_n = 0$ then the
%result is trivial. Otherwise there exists $|x_i| > 0$ and
%there exists $N$ such that, for all $n > N$, $|x_n| < |x_i|$.
%The finite set $|x_1|,\ldots ,|x_N|$ has a maximum element
%$|x_m|$, say, which will also satisfy $|x_m| > |x_n|$
%for all $n > N$. 
%So, the set $\{ | x_i | : i \geqslant 1\} \subset \bbR$ indeed
%has a maximum element, namely $|x_m|$.
%\par Define $s_k = \sum_{n=1}^k x_n$, so that $s_k \rightarrow x$.
%Then each $|s_k| \leqslant \hbox{max}(|x_1|,\ldots ,|x_k|) \leqslant |x_m|$;
%since, by~(c), $|s_k| \rightarrow |x|$, this gives
%that $|x| \leqslant |x_m| = \hbox{max}_i |x_i|$, also.
%\par Suppose that there exists $\ell$ such that
%$|x_\ell| > |x_i|$ for all $i\not= \ell$.
%Then, for all $k > \ell$, we have:
%$|s_k| = |x_\ell|$, by~(b). This means that $|s_k|$
%does not converge to~$0$ in~$\R$, and so
%$\sum_{n=1}^\infty x_n$ does not converge to~$0$
%in $K,|\ |$.
\medskip
\noindent {\bf 2.} 
{\bf (a).} $3/50 = 5^{-2}\cdot 3/2$ (where $5$ has no
common factor with either the numerator and denominator
of $3/2$)
and so 
$| 3/50 |_5 = 5^2$. Similarly, $3/50 = 3^{1}\cdot 1/50$ and so 
$| 3/50 |_3 = 3^{-1}$. Similarly, $3/50 = 7^0 \cdot 3/50$,
and so $| 3/50 |_7 = 7^0 = 1$.
\par
$d_5(2/3 , 1/5) = | 2/3 - 1/5 |_5 = | 7/15 |_5 = 5$,
$d_7(2/3 , 1/5) = | 7/15 |_7 = 7^{-1}$, $d_{11}(2/3, 1/5)
= | 7/15 |_{11} = 1$.
\par\noindent {\bf (b).} $ |3/7|_3 = 3^{-1}$, $ |3/7|_7 = 7$.
For all other primes~$p$, $\hbox{gcd}(p,3) = \hbox{gcd}(p,7) = 1$
and so $ |3/7|_p = 1$. Note also that $ |3/7|_{\infty} = 3/7$.
The given product $\prod | 3/7 |_i$ has all factors equal to~1
apart from the factors: $ |3/7|_3 = 3^{-1}$, $ |3/7|_7 = 7$
and $ |3/7|_3 = 3/7$, whose product is~$1$. Hence the given
product $\prod | 3/7 |_i$ is~1.
For any $x\in\Q$, write $x = \pm n/d$, where $n$ and $d$ are integers
with $\hbox{gcd}(n,d) = 1$, and write $n,d$ in terms of
their primes factorisations: $n = p_1^{s_1}\cdot \ldots p_k^{s_k}$
and $d = q_1^{t_1}\cdot \ldots q_\ell^{t_\ell}$, where $p_1,\ldots p_k,
q_1,\ldots q_\ell$ are distinct primes. For any prime~$p$,
if $p = p_i$ for some~$i$, then $|x|_p = p_i^{-s_i}$.
If $p = q_j$ for some~$j$, then $|x|_p = q_j^{t_j}$.
If $p=\infty$, then $|x|_p = n/d = (p_1^{s_1}\cdot \ldots p_k^{s_k})/
( q_1^{t_1}\cdot \ldots q_\ell^{t_\ell})$. For all other primes~$p$,
we have $|x|_p = 1$. It follows that
the product
$\prod | x |_i$ is equal to $(p_1^{-s_1}\cdot \ldots p_k^{-s_k})\cdot
 q_1^{t_1}\cdot \ldots q_\ell^{t_\ell}\cdot (p_1^{s_1}\cdot \ldots p_k^{s_k})/
( q_1^{t_1}\cdot \ldots q_\ell^{t_\ell})$, which is again equal
to~$1$.
\medskip
\noindent {\bf 3.}
{\bf (a).} $| 1/5^n |_5 = 5^n \rightarrow \infty$; this means
that $| 1/5^n |_5$ does not converge, and so
$1/5^n$ does not converge in~$\Q_5$ (since, if $a_n \rightarrow \ell$
then $| a_n |_p \rightarrow | \ell |_p$). 
\par\noindent {\bf (b).} {\it Method 1.} 
$ | n |_5 \le 5^{-1}$ for $n = 5,10,15,\ldots$
and $ | n |_5  = 1$ otherwise; this means that $| n |_5$ does not converge
(since there is a subsequence $| n |_5$ for $5 \not | n$ converging to~$1$
and a subsequence $| n |_5$ for 
$5 | n$ and $5^2 \not | n$ converging to~$1/5$), 
and so $n$ does not converge in~$\Q_5$ (since, if $a_n \rightarrow \ell$
then $| a_n |_p \rightarrow | \ell |_p$).
\par\noindent {\bf (b).} {\it Method 2.}
$n = \sum 1$, which does not converge, since $| 1 |_5 = 1$
which does not converge to~0 (using the result from lectures
which says that $\sum c_i$ converges iff $| c_i |_p \rightarrow 0$).
\par\noindent {\bf (c).} $n! = 5^r\cdot k$, where $r > n/5 - 1$,
since every fifth factor of $1\cdot 2\cdot \ldots n$ 
(i.e. the factors $5,10,15,\ldots $) contributes at least
one new factor of~5. Hence $ | n!  - 0 |_5 = | n! |_5 < 5^{-(n/5 - 1)}
\rightarrow 0$, and so $n!$ converges to~0 in $\Q_5$. 
\par
\noindent
{\bf (d).} 
$| (3+10^n) - 3 |_5 = |10^n|_5 = |5^n\cdot 2^n|_5 = 5^{-n} \rightarrow
0$, and so $3+10^n$ converges to~$3$ in $\Q_5$.
\par
\noindent {\bf (e).} $|10^n|_5 = |5^n\cdot 2^n|_5 = 5^{-n} \rightarrow 
0$ in $\Q_5$ and so $\sum 10^n$ converges in $\Q_5$
(using the result from lectures
which says that $\sum c_i$ converges iff $| c_i |_p \rightarrow 0$).  
\par
\noindent
{\bf (f).}
$| 7^n |_5 = 1$ which does not converge to~0,
and so $\sum 7^n$ does not converge in $\Q_5$ (using the
same result from lectures as used in part (e)).
%\par 
%Write $n = 5^r\cdot k$, where $\hbox{gcd}(5,k) = 1$, so that
%$| n|_5 = 5^{-r} = 1/5^r > 1/n$. Hence $ |1/n |_5 < n$,
%and so $ |5^n/ n|_5 = |5^n|_5 / |n|_5 = 5^{-n} / |n|_5
%< 5^{-n}\cdot n = n/5^n \rightarrow 0$. Hence (using the 
%which says that $\sum c_i$ converges iff $| c_i |_p \rightarrow 0$),
%we have that $\sum {5^n\over n}$
%converges in $\Q_5$.
%\medskip
%\noindent {\bf 5.} {\bf (a).} Note first that $|1/2|_{257} = 1$
%and so the $257$-adic expansion
%of $1/2$ is $a_0,a_1a_2a_3\ldots = a_0 + a_1p^1 + a_2p^2 + \ldots$
%(where $p=257$).
%Using: $2 (a_0 + a_1p^1 + a_2p^2 + \ldots) = 1$,
%we see that $2 a_0 \equiv 1$ mod~257, and so $a_0 = 129$.
%Now choose~$x=129$,
%so that $x-r = a_1\cdot 257^1 + \ldots$,
%and so $|x-r|_{257} \leqslant 257^{-1}$, as required.
%%$|x-1/2|_{257} \leqslant 257^{-1}
%%\iff | 2x - 1 |_{257} \leqslant |2|_{257} 257^{-1}= 257^{-1}
%%\iff 257 | (2x-1) \iff 2x \equiv 1 (\hbox{mod }257)$.
%%So, we can take $x = 129$ (the inverse of 2 mod 257), for
%%example.
%\par\noindent {\bf (b).} If there were such an $x\in \Z$, then
%we would have $|x|_3 \leqslant 1$ (since $|x|_p \leqslant 1$
%for any integer~$x$), whereas $| r |_3 = | 7/9 |_3 = 9  > 1$.
%Hence, $| x - r |_3 = \hbox{max}( | r |_3 , |x|_3 ) = 9$
%(using the result that $|a+b|_p = \hbox{max}( |a|_p, |b|_p)$
%when $|a|_p \not= |b|_p$), contradicting $| x - r |_3 \leqslant 3^{-7}$.
%Hence, no such~$x$ exists.
%\par\noindent
%{\bf (c).} Note first that $|1/4|_5 = 1$ and so the $5$-adic expansion
%of $1/4$ is $a_0,a_1a_2a_3\ldots
%= a_0 + a_1p^1 + a_2p^2 + a_3p^3 + \ldots$
%(where $p=5$). 
%Using: $4 (a_0 + a_1p^1 + a_2p^2 + a_3p^3 + \ldots) = 1$,
%we see first that $4 a_0 \equiv 1$ mod~5, and so $a_0 = 4$. Proceeding
%inductively, we find in turn that $a_1 = 3, a_2 = 3, a_3=3$,
%and so: $1/4 = 4 + 3\cdot 5^1 + 3\cdot 5^2 + 3\cdot 5^3 + a_4\cdot 5^4
%+ \ldots$. If we now choose~$x$ to be $x=4 + 3\cdot 5^1 +
% 3\cdot 5^2 + 3\cdot 5^3 = 469$, we see that $x-r = a_4\cdot 5^4 + \ldots$,
%and so $|x-r|_5 \leqslant 5^{-4}$, as required.
\medskip
\noindent {\bf 4.}
%N.B. $| r - x^2 |_p = |x^2 - r |_p$, so it makes
%no difference whether we use $| r - x^2 |_p$ or $|x^2 - r |_p$.
%\par\noindent
{\bf (a).} We are looking for $x$ such that $|x^2 +1|_5 \leqslant 5^{-4}$.
Take $x_0 = a_0 = 2$ as the initial approximation for which
$|a_0^2 + 1|_5 = |5|_5 = 5^{-1}$. Take $x_1 = a_0 + 5a_1 = 2+5a_1$. Then
we want $(2 + 5a_1)^2 \equiv -1$ mod~$5^2$, and so $20 a_1 \equiv -5$
mod~$5^2$, which is the same as $4a_1 \equiv -1$ mod~$5$, and
so $a_1 = 1$. This gives a better approximation: $x_1 = 2 + 1\cdot 5 = 7$,
which satisfies $|x_1^2 + 1|_5 = 5^{-2}$. Simlarly, we then
find $a_2 = 2$ and so $x_2 = 7 + 2\cdot 5^2 = 57$. Then, finally,
we similarly find $a_3 = 1$ and so $x_3 = 57 + 1\cdot 5^3 = 182$,
satisfying $|x^2 + 1|_5 = 5^{-4}$, as required.  
\par
\noindent {\bf (b).} If
there were an integer~$x$ such that $|x^2 - 7/8|_3 \leqslant
3^{-7}$, then we would have $x^2 \equiv 7/8$ mod~$3^7$ and
so $x^2 \equiv 7/8$ mod~$3$. But $7/8 \equiv 2$ mod~$3$, which is
not a quadratic residue (since $0^2 \equiv 0, 1^2 \equiv 1, 2^2\equiv 1$
mod~3); this means that no such~$x$ can exist.
\par\noindent {\bf (c).} If there
were an integer~$x$ such that $|x^2 - 5/4 |_5
\leqslant 5^{-4}$ then consider the possibilities for $|x^2|_5$.
If $|x^2|_5 > |5/4|_5$ then (using the result
that $|a+b|_p = \hbox{max}( |a|_p, |b|_p)$
when $|a|_p \not= |b|_p$) we have 
$|x^2 - 5/4 |_5 = \hbox{max}(|x^2|_5 , |5/4|_5)
=
|x^2|_5 > |5/4|_5
= 5^{-1} > 5^{-4}$, contradicting $|x^2 - 5/4 |_5 
\leqslant 5^{-4}$.
If $|x^2|_5 < |5/4|_5$ then (using the same result)
we have
$|x^2 - 5/4 |_5 = \hbox{max}(|x^2|_5 , |5/4|_5)
=
|5/4|_5
= 5^{-1} > 5^{-4}$, again contradicting $|x^2 - 5/4 |_5
\leqslant 5^{-4}$. It must then be that $|x^2|_5 = |5/4|_5 = 5^{-1}$,
but this is again impossible since $|x^2|_5 = 5^r$ where
$r$ is an even integer. Hence no such~$x$ exists.
\medskip 
\noindent {\bf 5.} $200$ mod $7$ is~$4$, so write: $200 = 4 + 7\cdot 28
= $ (similarly) $ 4 + 7\cdot (0 + 7\cdot 4) = 4 + 0\cdot 7^1 + 4\cdot 7^2
= 4,04$. 
\par For $3/14$, it is easier first to write:
$3/14 = 7^{-1}\cdot 3/2$. First find the $7$-adic expansion of~$3/2$,
with the idea that the $7$-adic expansion of $3/14$ will then
just be the $7$-adic expansion of $3/2$ shifted one place
to the left). Now, $|3/2|_7 = 1$ and so $3/2 = a_0,a_1a_2\ldots$.
Using $2( a_0 + 7a_1 + 7^2a_2 + \ldots) = 3$, we first find
$2a_0 \equiv 3$ mod~$7$ and so $a_0 = 5$. Continuing as usual,
we find that $a_1 = 3, a_2=3, a_3=3\ldots$. At this point,
we suspect that $3/2 = 5,\bar{3}$. We can prove this rigorously
as follows. Let $\alpha = 5,\bar{3}$. Then $\alpha - 5 = 0,\bar{3}$,
and so $7^{-1}(\alpha - 5) - 3 = 3,\bar{3} - 3 = 0,\bar{3} = \alpha - 5$.
Hence, $\alpha - 5 - 21 = 7\alpha - 35$ and so $\alpha = 3/2$,
proving that $3/2 = 5,\bar{3}$ in $\Q_7$. Finally,
$3/14 = 7^{-1}\cdot 3/2 = 53,\bar{3}$. 
\par 
%The $5$-adic expansion $23,4$ is just
%$2\cdot 5^{-1} + 3\cdot 5^0 + 4\cdot 5^1 = 117/5$.
Let $\beta = 2,\overline{34} \in \Q_5$. Then $\beta - 2 = 0,\overline{34}$
and so $5^{-2}(\beta - 2) = 34,\overline{34}$, giving:
$5^{-2}(\beta - 2) - 3\cdot 5^{-1} - 4\cdot 5^0 = 0,\overline{34}
= \beta - 2$, and so: $\beta = -67/24$.
\medskip\noindent {\bf 6.} Let $x\in \Q$.
Write $x = \pm n/d$, where $n$ and $d$ are integers
with $\hbox{gcd}(n,d) = 1$, and write $n,d$ in terms of
their primes factorisations: $n = p_1^{s_1}\cdot \ldots p_k^{s_k}$
and $d = q_1^{t_1}\cdot \ldots q_\ell^{t_\ell}$, where $p_1,\ldots p_k,
q_1,\ldots q_\ell$ are distinct primes. If $x\in \Z$ then $\ell = 0$
(i.e. there are no occurrences of $q_j$) and we see that
when $p=p_i$ for some~$i$, 
$|x|_p = p_i^{-s_i} \leqslant 1$, and otherwise $|x|_p = 1$;
hence $|x|_p \leqslant 1$ for all~$p$; that is to say:
$x\in \Z_p \hbox{ for all }p$.
\par Conversely, assume that $x\in \Z_p \hbox{ for all }p$.
Then there could not be any occurrence of $q_j$ [since then
at $p=q_j$ we would have $|x|_p = q_j^{t_j} > 1$, contradicting
$x\in \Z_p$. Hence, $x$ has no denominator and is in~$\Z$.
\medskip
\noindent {\bf 7.} First note that $-28 = 2^2\cdot (-7)$.
In $\Q_2$, we know that any integer congruent to~1 mod~8
is a square, and so certainly $-7$ is a square; hence
so is $-28 = 2^2\cdot (-7)$.
\par
In $\Q_3$, we observe that $|-28|_3 = 1$ and $-28 \equiv 2$ (mod~3)
which is not a quadratic residue mod~3; hence~$-28$ is not
a square in $\Q_3$. In $\Q_5$,
we observe that $|-28|_5 = 1$ and $-28 \equiv 2$ (mod~5)
which is not a quadratic residue mod~5; hence~$-28$ is not 
a square in $\Q_5$. In $\Q_7$, if there were an $x$ such that
$x^2 = -28$, then $|x^2|_7 = |-28|_7 = 7^{-1}$, contradicting
the fact that $|x^2|_7 = 7^r$ where~$r$ is an even integer;
hence $-28$ is not a square in $\Q_7$.
In $\Q_{11}$,
we observe that $|-28|_{11} = 1$ and $-28 \equiv 5$ (mod~11)
which is a quadratic residue mod~11 since $5 \equiv 4^2$
(mod~11); hence~$-28$ is
a square in $\Q_{11}$.
[The above repeatedly used the result that, when $p\not= 2$
and when $|a|_p = 1$ then $a$ is a square in $\Q_p$ iff it
is a square mod~$p$.]
%\medskip\noindent {\bf 2.} In $\Q_2$, let $x=4$. Then
%$x^3 + x - 3 = 65$ which is an integer congruent to~1 mod~8,
%and so, from lectures, is a square in $\Z_2$; that is,
%$65 = \alpha^2$ for some $\alpha \in \Q_2$ [and, of course,
%$|\alpha|_2^2 = |\alpha^2|_2 = |65|_2 = 1$, so that $|\alpha|_2 =1$,
%and so $\alpha$ must be in $\Z_2$].
%Then $x=4, y=\alpha$
%give the required pair in $\Z_2$.
%\par In $\Q_3$, let $x=2$. Then $x^3 + x - 3 = 7$, which
%satisfies: $|7|_3 = 1$, and $7 \equiv 1^2$ is a quadratic
%residue mod~3. Hence (by the same result from notes quoted
%at the end of the soln to qn~8) we have that there exists
%$\beta \in \Q_3$ s.t. $7 = \beta^2$ [and, of course, as above,
%this $\beta \in \Z_3$, also].
%\par In $\Q_5$, let $x=1$. Then $x^3 + x - 3 = -1$, which
%satisfies: $|-1|_5 = 1$, and $-1 \equiv 2^2$ is a quadratic
%residue mod~5. Now apply the same argument as for~$\Q_3$.
%\par In $\Q_7$, let $x=-1$. Then $x^3 + x - 3 = -5$, which
%satisfies: $|-5|_7 = 1$, and $-5 \equiv 3^2$ is a quadratic
%residue mod~5. Now apply the same argument as for~$\Q_3$.
%\par Similarly for $\Q_{13}$, with~$x=1$, and $\Q_{19}$, with $x=0$.
%%\par In $\Q_{13}$, let $x=1$. Then $x^3 + x - 3 = -1$, which
%%satisfies: $|-1|_{13} = 1$, and $-1 \equiv 5^2$ is a quadratic
%%residue mod~13. Now apply the same argument as for~$\Q_3$.
%%\par In $\Q_{19}$, let $x=0$. Then $x^3 + x - 3 = -3$, which
%%satisfies: $|-3|_{19} = 1$, and $-3 \equiv 4^2$ is a quadratic
%%residue mod~19. Now apply the same argument as for~$\Q_3$.
%\par Note that $\Delta = 4\cdot 1^3 + 27\cdot (-3)^2 = 247 = 13\cdot 19$,
%and so the curve will still be an elliptic curve for any
%$p$ not dividing $2\Delta$, that is, for any $p\not=2,13,19$. 
%For all primes $p \geqslant 11$, $p\not=13,19$ the number of
%points on the elliptic curve mod~$p$ (not including the point at infinity)
%over $\F_p$ is in the range
%$[p- 2\sqrt{p},p + 2\sqrt{p}]$, and for $p\geqslant 11$, we
%have $p- 2\sqrt{p} \geqslant 11 - 2\sqrt{11} > 4$. At most 3
%of these points over $\F_p$ are of the form $(v,0)$,
%and so there must be at least one point of the form
%$(v,w)$ over $\F_p$, with $w\not=0$. Now, let $x=v$; then
%$v^3 + v - 3$ must be a quadratic residue mod~p and
%nonzero mod~p. Now again apply the same argument as for $p=3$. 
\medskip
\noindent
{\bf 8.} In~$\R$, we have for example the
root $\sqrt{2}$.
In $\Q_2$, note that $17 \equiv 1$ mod~8, and so $17$
is a square in $\Q_2$. In $\Q_{17}$, note that $|2|_{17} = 1$
and $2$ is a quadratic residue mod~$17$, so that $2$ is a square
in~$\Q_{17}$.
\par Finally, let $p \not= 2,17$. Then each of $({2\over p}), ({17\over p}),
({34\over p})$ is $1$ or $-1$. They cannot all be $-1$
since $({34\over p}) = ({2\over p}) ({17\over p})$ [and $-1 \not= (-1)(-1)$],
so at least one of them must be~1.
Wlog, say that  $({2\over p}) = 1$. Then $|2|_p = 1$ and $2$ is
a quadratic residue mod~$p$, so that $2$ must be a square in $\Q_p$.
\medskip\noindent {\bf 9.} Suppose there were an $x\in \Q_3$
such that $x^3 = 4$ in $\Q_3$. Then $|x|_3^3 = |4|_3 = 1$
and so $|x|_3 = 1$, which means that
$x$ can be written $x = a_0,a_1a_2\ldots$.
Reducing $x$ modulo~9 would then give
the integer $a_0 + 3a_1$ whose cube is~$4$ modulo~9. But $0,\ldots 8$
square to give: $0,1,8,0,1,8,0,1,8$, respectively, so that
$x^3 = 4$ is an impossible congruence mod~9. Hence~$4$ is
not a cube in $\Q_3$.
\par
Let $f(x) = x^3 - 28$ and let $x_0 = 1$. Then $| f(x_0) |_3
= |-27 |_3 = 3^{-3}$, whereas $| f'(x_0) |_3 = | 3 |_3 = 3^{-1}$.
Hence $| f(x_0) |_3 < | f'(x_0) |_3^2$, and so by Hensel's
Lemma there must be a root
of $f(x)$ in $\Q_3$; that is $28$ must be a cube in $\Q_3$.
\par
Let $f(x) = x^3 - 13$ and let $x_0 = -1$.
Then $| f(x_0) |_7 
= |-14 |_3 = 7^{-1}$, whereas $| f'(x_0) |_7 = | 3 |_7 = 1$. 
Hence $| f(x_0) |_7 < | f'(x_0) |_7^2$, and so by Hensel's
Lemma again there must be a root 
of $f(x)$ in $\Q_7$; that is $13$ must be a cube in $\Q_7$.
\medskip
\noindent {\bf 10.} 
The number of positive multiples of an integer $k>0$ which are
$\leqslant n$ is clearly $\bigl[ {n\over k} \bigr]$. To count the
power of $p$ dividing $n!$, since $p$ is prime, it is enough to
count the powers of $p$ dividing $1,2,3,\ldots ,n$ and add these
powers up. Now, the number of multiples of $p$ among $1,2,3,\ldots ,n$
is $[ {n\over p} ]$. Each multiple of $p^2$ among
$1,2,3,\ldots ,n$ gives an additional power of $p$ dividing into $n!$,
giving $\bigl[ {n\over p} \bigr] + \bigl[ {n\over p^2} \bigr]$
so far. Continuing in this way we get that the total power of $p$
is as in the given formula. This gives that $|n!|_p = p^{-M}$,
where $M = \bigl[ {n\over p} \bigr] + \bigl[ {n\over p^2} \bigr] + \ldots
\leqslant {n\over p} + {n\over p^2} + \ldots = {n\over p-1}$.
Hence $|n!| \geqslant p^{-{n\over p-1}}$, and so
$|1/n!| \leqslant p^{n\over p-1}$. Suppose that $|x| < p^{-{1\over p-1}}$
and let $\tau = |x|/p^{-{1\over p-1}} < 1$.
Then $\bigl| {x^n \over n!} \bigr| = \tau^n p^{-{n\over p-1}} 
\bigl| {1 \over n!} \bigr| \leqslant \tau^n p^{-{n\over p-1}} 
p^{n\over p-1} = \tau^n \rightarrow 0$. Hence, $\hbox{exp}_p(x)$
converges (using the result from lectures
which says that $\sum c_i$ converges iff $| c_i |_p \rightarrow 0$).
\par
On the other hand, if $|x| \geqslant p^{-{1\over p-1}}$,
note that, for any $n=p^\ell$, the above ${n\over p}, {n\over p^2},\ldots
{n\over p^\ell} = p^{\ell-1}, p^{\ell-2}, \ldots , 1 \in \Z$ and
so $M = p^{\ell-1} + p^{\ell-2}, \ldots + 1 = {p^\ell - 1\over p - 1}$; 
this means that the subsequence
$\bigl| {x^{p^\ell}\over (p^\ell)!}\bigr| \geqslant 
(p^{-{1\over p-1}})^{p^\ell} p^{p^\ell - 1\over p - 1}
= p^{-1 \over p-1}$, and so $\bigl| {x^n \over n!} \bigr| \not\rightarrow 0$.
Hence $\hbox{exp}_p(x)$ does not converge when
$|x| \geqslant p^{-{1\over p-1}}$.
\par When $K = \Q_p$ ($p\not= 2$), any $|x|_p < 1$
must satisfy $|x|_p \leqslant p^{-1}$ [since $|x|_p = p^r$
for some $r\in \Z$] $< p^{-{1\over p-1}}$,
since $p\geqslant 3$. Any $|x|_p \geqslant 1$
satisfies $|x| \geqslant p^{-{1\over p-1}}$.
When $K = \Q_2$, any $|x|_2 < 1/2$
must satisfy $|x|_2 \leqslant 2^{-2}$ [since $|x|_p = p^r$
for some $r\in \Z$] $< p^{-{1\over p-1}} = 2^{-1}$.
Any $|x|_p \geqslant 1/2$
satisfies $|x| \geqslant p^{-{1\over p-1}}= 2^{-1}$.
\vfil\eject
\chaptitle
\noindent
\centerline{Elliptic Curves. Solutions to Sheet 3.}
\rm
\par
\bigskip
\noindent {\bf 1} Let $\c$ be the curve $2 Y^2 = X^4 - 17$.
Over~$\R$, the curve has the point
$(4,\sqrt{239/2})$. 
In $\Q_2$, let $x=11$. Then
$11^4 - 17 = 2^5 \cdot 457$; but 457 is an integer congruent to~1 mod~8,
and so, from lectures, there exists $\gamma \in \Z_2 \subset \Q_2$ such that
$457 = \gamma^2$; then $(11, 4\gamma)$ is a point on the curve
over~$\Q_2$. For the next few primes,
we shall repeatedly use the result from lectures that, if $p\not= 2$
and $|a|_p = 1$, then $a$ is a square in $\Q_p$ iff it
is a square mod~$p$. Now, note that $-8,-34,-34,-8,10,-8$ are
quadratic residues modulo~$p=3,5,7,11,13,17$, respectively,
and so there exists $\gamma \in \Q_p$
such that $\gamma^2 = -8,-34,-34,-8,10,-8$, respectively;
this gives the $\Q_p$-rational points on the
curve: $(1,\gamma), (0,\gamma/2), (0,\gamma/2),
(1,\gamma), (4,\gamma/2), (1,\gamma)$, respectively.
Hence $\c$ has $\Q_p$-rational points for all primes
up to and including $p=17$ [in fact, it was only necessary to
do here $p=2,3,5,7,11,17$ here].
%\par Let $p$ be any prime $p\geqslant 19$.
%If $-34$ is a quadratic residue mod~$p$, then (as above)
%there exists $\gamma \in \Q_p$ such that $\gamma^2 = -34$,
%in which case $(0,\gamma/2)$ is a $\Q_p$-rational point
%on the curve. On the other hand, if -34 is not a quadratic
%residue mod~$p$, then consider the variant curve:
%$\c' : 2 Y^2 = -34(X^4 - 17)$ [that is:
%$\c' : Y^2 = -17(X^4 - 17)$], which has the point $(0,17)$.
%Furthermore, the quartic has no repeated roots mod~$p$
%[since the resultant is nonzero mod~$p$ for any $p\not= 2,17$] 
%and the curve is nonsingular mod~$p$.
%Therefore, from lectures, $\c'$ is an elliptic curve, 
%and its number of affine points is at most
%$p + 2\sqrt{p}$. At most~4 $x$-values give
%$-17(x^4 - 17) \equiv 0$ mod~$p$, and so there are at least
%$p-4$ values of~$x$ for which $-17(x^4 - 17)$
%is nonzero mod~$p$. If these were all quadratic residues mod~$p$,
%the this would give rise to $2(p-4)$ points on~$\c'$
%[via $(x,y),(x,-y)$ for each such~$x$],
%which is impossible for $p \geqslant 19$ [using the fact
%that $2(p-4) \leqslant p + 2\sqrt{p} \Rightarrow (\sqrt{p} - 1)^2 \leqslant 9
%\Rightarrow \sqrt{p} \leqslant 4$]. 
%Hence, these exists
%$x_0 \in \Z$ such that $-17(x_0^4 - 17)$ is a nonzero quadratic
%nonresidue mod~$p$. Since $-34$ is also a quadratic nonresidue mod~$p$,
%it follows that $(-34)\bigl(-17(x_0^4 - 17)\bigr)$,
%and so $2(x_0^4 - 17)$ is a nonzero quadratic residue mod~$p$
%[using the rule that the product of two quadratic nonresidues mod~$p$
%always gives a quadratic residue mod~$p$].
\par Let $p$ be any prime $p\geqslant 13$ and $p\not= 17$.
Our curve~$\c$ (after multiplying both sides by~$2$) is
birationally equivalent to $V^2 = 2 X^4 - 34$, where $V = 2Y$;
note that $2 X^4 - 34$ has discriminant $-2^{11} 17^3$.
Recall Theorem~1.15 from lectures, 
that any curve $y^2 = Q(x)$, where $Q(x) = f_4 x^4 + \ldots + f_0$
has nonzero discriminant over~$\F_p$, 
has at least $p - 1 - 2\sqrt{p} > 4$
affine points over~$\F_p$, and so at least~$5$ affine points.
At most~$4$ of these can have $2 x^4 - 34 \equiv 0$~(mod~$p$),
and so there exists
$x_0 \in \Z$ 
such that $2(x_0^4 - 17)$ is a nonzero quadratic residue mod~$p$.
As above, there exists $\gamma \in \Q_p$ such that
$\gamma^2 = 2(x_0^4 - 17)$, and so $(x_0,\gamma/2)$ is a
$\Q_p$-rational point on our original curve~$\c$.
Hence $\c$ has points in~$\R$ and every~$\Q_p$.
\par {\it Alternative method for the above parts:}
Note that for $p \notdiv 2\Delta$
(that is: $p \not= 2,17$, so that $\widetilde \c$ is still an
elliptic curve mod~$p$) and $p \geqslant 5$, we have
$\# {\widetilde \c} (\F_p) \geqslant p+1 - 2\sqrt{p} > 1$, and so the
number of affine points is $ > 0$; these are non-singular, since
${\widetilde \c}$ is still an elliptic curve mod~$p$. Also, 
by a theorem from lectures, any non-singular point on 
${\widetilde \c} (\F_p)$ lifts to a point on $\c (\Q_p)$; 
also, any affine non-singular point on ${\widetilde \c} (\F_p)$ 
lifts to an affine point on $\c (\Q_p)$
(since the point at infinity on $\c (\Q_p)$ maps to the point at 
infinity on ${\widetilde \c} (\F_p)$ under the reduction map mod~$p$).
This shows the existence of such $x,y \in \Q_p$ for
all~$p$ except $p = 2,3$ and bad primes, so only still need
to consider $p = 2,3,17$. Also, note that for $p = 3$ there
is the non-singular affine point $(1,1)$ on ${\widetilde \c} (\F_3)$, 
and for $p = 17$ there is the non-singular affine point 
$(1,3)$ on ${\widetilde \c} (\F_{17})$, and as before these must 
lift to affine points $(x,y) \in \c(\Q_p)$.
Over~$\R$, the curve has the point
$(4,\sqrt{239/2})$.
In $\Q_2$, let $x=11$. Then
$11^4 - 17 = 2^5 \cdot 457$; but 457 is an integer congruent to~1 mod~8,
and so, from lectures, there exists $\gamma \in \Z_2 \subset \Q_2$ such that
$457 = \gamma^2$; then $(11, 4\gamma)$ is a point on the curve
over~$\Q_2$.
This completes the alternative method of showing
that $\c$ has points in~$\R$ and every~$\Q_p$.
\par Now, imagine that $\c$ had a $\Q$-rational point; that is,
imagine that there exist $X,Y\in \Q$ such that $2 Y^2 = X^4 - 17$.
Let $X = t/r$, where $r,t\in \Z$ and $\hbox{gcd}(r,t) = 1$.
Then $2(r^2 Y)^2 = t^4 - 17 r^4 \in \Z$. For any prime~$p$,
this gives that $|2|_p |r^2 Y|_p^2 \leqslant 1$. When $p\not= 2$,
we have $|2|_p = 1$ and so $|r^2 Y|_p^2 \leqslant 1$
and so $|r^2 Y|_p \leqslant 1$. When $p=2$,
we have $2^{-1} |r^2 Y|_2^2 \leqslant 1$; but this still
gives $|r^2 Y|_2 \leqslant 1$ [since $|r^2 Y|_2 > 1$
would mean $|r^2 Y|_2 \geqslant 2^1$ and so $2^{-1} |r^2 Y|_2^2 
\geqslant 2^{-1} 2^2 > 1$]. Overall, we have shown that
$|r^2 Y|_p \leqslant 1$ for all~$p$; since also $r^2 Y \in \Q$,
this gives that $r^2 Y \in \Z$; let us say: $s = r^2 Y \in \Z$.
Therefore $r,s,t\in\Z$ satisfy $2 s^2 = t^4 - 17 r^4$
and $\hbox{gcd}(r,t) = 1$.
\par Let $q$ be any prime such that $q | s$. Note that
$q\not= 17$ [since if $17 | s$ then our equation
$2 s^2 = t^4 - 17 r^4$ would force $17 | t$, and so
$17^2 | 2 s^2$ and $17^2 | t^4$, which would give $17^2 | 17 r^4$,
forcing $17 | r$, which
would contradict $\hbox{gcd}(r,t) = 1$]. 
Note also that
we must not then have $q|r$ [since if $q|s$ and $q|r$, then
our equation $2 s^2 = t^4 - 17 r^4$ would force $q | t$, which
would contradict $\hbox{gcd}(r,t) = 1$]. 
Reducing our equation modulo~$q$ gives that $0 \equiv t^4 - 17 r^4$
and so $(t^2/r^2)^2 \equiv 17$ mod~$q$ [note that division
by $r^2$ is allowable mod~$q$ since $r$ is not divisible by~$q$].
Hence $17$ is a nonzero quadratic residue mod~$q$.
For $q\not= 2$, quadratic reciprocity then allows us to
deduce that~$q$ is a quadratic residue mod~$17$
[since $17 \equiv 1$ (mod~$4$)]. Furthermore, one can check
directly that $2$ is a quadratic residue mod~$17$, since
$2 \equiv 6^2$ mod~$17$. Overall, we have shown that
every prime~$q$ dividing~$s$ must be a quadratic residue
mod~$17$, 
and we can take $s>0$ (if necessary, replacing~$s$ by~$-s$),
so that~$s$ is the product of its prime factors.
It follows that $s$ itself must be a quadratic residue mod~$17$,
since it is a product of quadratic residues mod~$17$.
Hence $s^2$ is a nonzero fourth power [also known as
a {\it quartic residue}] mod~$17$.
Note also that reducing our equation mod~$17$ gives
$2 s^2 \equiv t^4$ (mod~$17$), so that $2 s^2$ is also
a nonzero fourth power mod~$17$. Since $s, 2s^2$ are
both nonzero fourth powers mod~$17$, it follows that
$2 = (2s^2)/s^2$ is also a fourth power mod~$17$.
On the other hand, one can compute directly that
$0^4,1^4,2^4,3^4,4^4,5^4,6^4,7^4,8^4,9^4,10^4,11^4,12^4,13^4,14^4,
15^4,16^4$ are congruent mod~$17$ to: 
$0,1,16,13,1,13,4,4,16,16,4,4,13,1,13,16,1$, respectively,
so that in fact $2$ is not a fourth power mod~$17$.
This contradication show that our original curve $\c$
has no $\Q$-rational points.
\par\noindent {\bf 2.} Since $p \equiv 2$~(mod~$3$),
we have $\hbox{gcd}(3,p-1) = 1$,
and so there exist $\lambda, \mu \in \bbZ$ such that
$3\lambda + (p-1)\mu = 1$. For any $x,y\in\bbF_p^*$,
we have $x^{p-1} = y^{p-1} = 1$ [by Fermat's Little Theorem],
and so:
$$ x^3 = y^3 \Rightarrow 
\bigl( x^3 \bigr)^\lambda \cdot 1^\mu
= \bigl( y^3 \bigr)^\lambda \cdot 1^\mu
\Rightarrow
\bigl( x^3 \bigr)^\lambda \cdot \bigl(x^{p-1}\bigr)^\mu
= \bigl( y^3 \bigr)^\lambda \cdot \bigl(y^{p-1}\bigr)^\mu
$$
$$
\ \ \ \ \ \Rightarrow x^{ 3\lambda + (p-1)\mu } 
= y^{ 3\lambda + (p-1)\mu } 
\Rightarrow x = y.
$$
Thus the map $x \mapsto x^3$ is injective on $\bbF_p^*$
and so is a bijection.
\par Now, let 
$a\in \Z$ be such that $p\notdiv a$.
From above, there must exist $x_0 \in \Z$ such
that $x_0^3 \equiv a$ (mod~$p$); clearly
$p\notdiv x_0$. Let $f(x) = x^3 - a$.
Then $|f(x_0)|_p = |x_0^3 - a|_p < 1$,
since $x_0^3 - a \equiv 0$ (mod~$p$).
Also, $|f'(x_0)|_p = |3 x_0^2|_2 = 1$,
since $|3|_p = 1$ and $p\notdiv x_0$.
Hence $|f(x_0)|_p < |f'(x_0)|_p^2$, and so by Hensel's Lemma,
there exists
$x\in \Z_p$ with $f(x) = 0$, that is, $x^3 = a$, as required.
\medskip\noindent {\bf 3.} Recall the standard fact
about resultants (stated in Section~$0$, the preliminary reading),
that there exist polynomials $p(x),q(x)\in R[x]$
such that:
$p(x) f(x) + q(x) g(x) = \hbox{Res}\bigl( f(x), g(x) \bigr)$
Since the discriminant~$D$ is the resultant of $f(x)$
and $f'(x)$, there must exist polynomials $p(x),q(x)\in R[x]$
such that $p(x) f(x) + q(x) f'(x) = D$,
and so: $p(a_0) f(a_0) + q(a_0) f'(a_0) = D$.
Since $|a_0|\leqslant 1$, and since $p(x),q(x),f(x),f'(x)\in R[x]$,
we must have $|p(a_0)|,|f(a_0)|,|q(a_0)|,|f'(a_0)| \leqslant 1$
and so $|D| \leqslant \hbox{max}( |p(a_0) f(a_0)|,|q(a_0) f'(a_0)| )
\leqslant 1$, which also implies $|D^2| = |D|^2 \leqslant |D|$.
Now, we are given that $|f(a_0)| < |D|^2$
and so $| p(a_0) f(a_0) | \leqslant | f(a_0) | < |D^2| \leqslant |D|$.
Hence $|D| \not= |p(a_0) f(a_0) |$, and
so $|q(a_0) f'(a_0)| = |D - p(a_0) f(a_0)| = \hbox{max}( |D|, |p(a_0) f(a_0)|)
= |D|$ [using the fact that, if $|u| \not= |v|$
then $|u\pm v| = \hbox{max}(|u|,|v|)$].
Since also $|q(a_0)| \leqslant 1$, this gives
that $|f'(a_0)| \geqslant |D|$. Finally,
$|f(a_0)| < |D|^2 \leqslant |f'(a_0)|^2$, and so $f(X)$
has a root $a\in R$ by Hensel's Lemma.
\medskip\noindent 
{\bf 4.} We first (as suggested in the hint) show:
\par\noindent {\bf Lemma (*).} 
For any $\alpha = a + b\sqrt{d} \in \Q_p(\sqrt{d})$,
$|\alpha|_p \leqslant 1 \Rightarrow |\alpha + 1|_p \leqslant 1$. 
\par\noindent {\bf Proof.} Assume $|\alpha |_p \leqslant 1$,
so that $| a^2 - b^2 d |_p \leqslant 1$. 
The result is trivial for $b=0$, so we can assume $b\not= 0$. Let:
\par\noindent $f(x) = \bigl( x - (a + b\sqrt{d}) \bigr) 
        \bigl( x - (a - b\sqrt{d}) \bigr)
= x^2 - 2ax + a^2 - b^2 d$. 
\par Imagine $|2a|_p > 1$. Then $g(x) = f(x) / (2a)
= {x^2\over 2a} - x + {a^2 - b^2 d \over 2a}$ would
be defined over $\Z_p$, with $|g(0)|_p = | {a^2 - b^2 d \over 2a} |_p
< 1 = |-1|_p^2 = | g'(0) |_p^2$, so by Hensel's Lemma, there would
exist a root in $\Z_p$, contradicting the fact that
$a + b\sqrt{d}, a - b\sqrt{d} \not\in \Z_p$ (since $d$ is non-square
and $b\not= 0$).
\par Hence $|2a|_p \leqslant 1$. So: 
\par\noindent
$|\alpha + 1 |_p = |a+1 + b\sqrt{d}|_p
= |(a + 1)^2 - b^2 d|_p^{1/2} 
= | (a^2 - b^2 d) + 2a + 1 |_p^{1/2} \leqslant 1$
(since $|a^2 - b^2 d|_p, |2a|_p, |1|_p \leqslant 1$),
completing the proof of Lemma~(*).
\par
For any $\alpha = a + b\sqrt{d} \in \Q_p(\sqrt{d})$, let
$\overline \alpha$ denote $a - b\sqrt{d}$; also,
let:
\par\noindent $\alpha_1 = a_1 + b_1\sqrt{d},\ 
\alpha_2 = a_2 + b_2\sqrt{d} 
\in \Q_p(\sqrt{d})$, where $a,b,a_1,b_1,a_2,b_2\in \Q_p$.
\par
Note that $|\alpha|_p = |a^2 - b^2 d|_p^{1/2} \geqslant 0$,
and that:
\par\noindent $|\alpha|_p = 0 \iff
a^2 - b^2 d = 0 \iff a = b = 0 \iff \alpha = 0$
(since~$d$ is non-square).
\par
$|\alpha_1 \alpha_2 |_p
= | \alpha_1 \alpha_2 \overline{\alpha_1 \alpha_2} |_p^{1/2}
= | \alpha_1 \overline \alpha_1 \alpha_2 \overline \alpha_2 |_p^{1/2}
= | \alpha_1 \overline \alpha_1 |_p^{1/2}
  | \alpha_2 \overline \alpha_2 |_p^{1/2}
= | \alpha_1 |_p |\alpha_2 |_p$.
\par
Also, without loss of generality, $|\alpha_1|_p \leqslant |\alpha_2|_p$,
so that $| {\alpha_1 \over \alpha_2} |_p \leqslant 1$.
Then:
\par\noindent $| \alpha_1 + \alpha_2 |_p = 
| {\alpha_1 \over \alpha_2} + 1 |_p | \alpha_2 |_p
\leqslant $ [by Lemma~(*)] $| \alpha_2 |_p = 
\hbox{max}\bigl( |\alpha_1|_p, |\alpha_2|_p \bigr)$.
\par Hence, $|\ |_p$ is a non-Archimedean valuation on $\Q_p(\sqrt{d})$.
Finally, note that when $\alpha = a$ [with $b=0$], our definition
of $|\ |_p$ on $\Q_p(\sqrt{d})$ gives
$|\alpha|_p = | a^2 - 0^2 d |_p^{1/2} = | a^2 |_p^{1/2}
= | a |_p$, which agrees with the usual $|\ |_p$ on $\Q_p$,
so that our non-Archimedean valuation on $\Q_p(\sqrt{d})$
extends that on $\Q_p$.
\medskip\noindent {\bf 5.} In projective form, the point is:
$(-64/25,59/125,1)$. The coordinate with largest $5$-adic value
is $59/125$, and on dividing all coordinates
through by this, we can also represent
the point as: $(-320/59,1,125/59)$, which is in $5$-adic standard
form (that is, $1$ is the maximum of the $5$-adic valuations
of the coordinates). Reducing mod~$5$ gives $(0,1,0)$ on $\widetilde \e$,
which is the point at infinity.
\medskip\noindent {\bf 6.} Suppose that $(x,y)$ on $\e$ reduces
mod~$p$ to $(0,0)$ on~$\widetilde \e$. Then $|x|_p, |y|_p < 1$,
indeed $|x|_p, |y|_p \leqslant p^{-1}$ (since any $p$-adic
value is one of: $\ldots ..., p^{-2}, p^{-1}, 1, p^1, p^2, \ldots$,
so that if a $p$-adic value is $< 1$ then it must be $\leqslant p^{-1}$),
so that $|x|_p^3 \leqslant p^{-3}$. But $|p|_p = p^{-1}$ and
so $|x|_p^3 \not= |p|_p$ which means that $|x^3 + p|_p =
\hbox{max}(|x|_p , |p|_p) = p^{-1}$. Since $x,y$ satisfy
$y^2 = x^3 + p$, we must therefore have: $|y|_p^2 = p^{-1}$,
which contradicts the fact that $|y|_p^2 = p^{2r}$ for some
integer~$r$. 
\medskip\noindent {\bf 7.}
\par \noindent {\bf (a).} Let $\e : Y^2 = X^3 + p^2$. Then
the point $(0,p)$ on $\e$ reduces modulo~$p$ to the
cusp~$(0,0)$ on $\widetilde \e : Y^2 = X^3$, which is another
way of saying that $(0,0)$ on $\widetilde \e$ lifts to the
point $(0,p)$ in~$\e (\Q_p)$.  
\par \noindent {\bf (b).} Question~3 is an example of this.
\par \noindent {\bf (c).} Let $\e : Y^2 = X^3 + X^2 + p^2$. Then 
the point $(0,p)$ on $\e$ reduces modulo~$p$ to the 
node~$(0,0)$ on $\widetilde \e : Y^2 = X^3 + X^2$, which is another
way of saying that $(0,0)$ on $\widetilde \e$ lifts to the  
point $(0,p)$ in~$\e (\Q_p)$.
\par \noindent {\bf (d).} Let $\e : Y^2 = X^3 + X^2 + p$ and
$\widetilde \e : Y^2 = X^3 + X^2$. Then the node~$(0,0)$ on
$\widetilde \e$ does not lift to any point in~$\e(\Q_p)$ by the
same argument as in Question~2.
\medskip\noindent {\bf 8.} Take $F(X,Y) = X + Y + t X Y^p$,
clearly non-commutative. One only has to check associativity.
$$ F(F(X,Y),Z) = F( X + Y + t X Y^p, Z )
= X + Y + t X Y^p + Z + t(X + Y + t X Y^p) Z^p
$$
$$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
= X + Y + t X Y^p + Z + t X Z^p + t Y Z^p,$$
since the remaining term $t^2 X Y^p Z^p \in I = t^2 \F_p[t]$
and so $t^2 X Y^p Z^p = 0$ in $R = \F_p[t]/I$.
Also:
$$ F(X, F(Y,Z))
= X + F(Y,Z) + t X F(Y,Z)^p
= X + Y + Z + t Y Z^p + t X (Y + Z + t Y Z^p)^p
$$
$$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
= X + Y + Z + t Y Z^p + t X (Y^p + Z^p + (t Y Z^p)^p),
$$
since all other terms in the binomial expansion
of $(Y + Z + t Y Z^p)^p$ are divisible by~$p$ and
so are equal to~$0$ in $R$, which has characteristic~$p$.
But $(t Y Z^p)^p = t^2 (t^{p-2} Y^p Z^{p^2})\in I$ 
and so $(t Y Z^p)^p = 0$ in~$R$, so that the above
are the same, giving associativity, as required.
\medskip\noindent {\bf 9.} 
Recall from lectures that the first step in deriving the
formal group of an elliptic curve is to write the
equation $\e : Y^2 = X^3 + A X + B$ as: 
$\e' : w = f(z,w) = z^3 + A w^2 z + B w^3$,
where $z = -x/y, w = -1/y$.
We then Inductively define $f_n(z,w)$ by: $f_1(z,w) = f(z,w)$
and $f_{m+1}(z,w) = f_m( z, f(z,w) )$ and define
$$ w(z) = \lim_{m\rightarrow \infty} f_m(z,0) \in \Z[A,B][[z]],$$
which satisfies $w(z) = f\bigl( z, w(z) \bigr)$.
The terms of $f_1(z,w) = z^3 + A w^2 z + B w^3$ all have
weighted degree~$\equiv 3$ [where we give $z$ weight~1, $w$ weight~$3$,
$A$ weight~$-4$ and $B$ weight~$-6$].
Suppose that this is also true of $f_m(z,w)$;
then $f_{m+1}(z,w) = f_m ( z, z^3 + A w^2 z + B w^3 )$, where
$z$ has weighted degree~$1$, $z^3 + A w^2 z + B w^3$ is homogeneous
of weighted degree~$3$,
and so the same will be true of~$f_{m+1}$.
So, by induction, all terms of every $f_m$ and so all terms
of $w(z)$ will have weighted degree~$3$, and so
$w(z) = \sum c_n z^n$, where $c_n = 0$ unless $n\equiv 3$ mod~$4$.
We now perform the addition 
$ (z_1,w_1) + (z_2,w_2)$. As usual, we first write
the line $z = \lambda w + \mu$ through the points,
given by $\lambda = (w(z_1) - w(z_2))/(z_1 - z_2)$
and $\mu = (z_1 w(z_2) - z_2 w(z_1))/(z_1 - z_2)$,
both in $\Z[A,B][[z_1,z_2]]$. Letting $z_1$ and $z_2$ each
have weight~$1$, the numerator $w(z_1) - w(z_2)$
is homogeneous of weighted degree~$3$, and so
$\lambda$ is homogeneous of weighted degree~$2$.
Similarly, $\mu$ is homogeneous of weighted degree~$3$.
As in lectures, substituting $w = \lambda z + \mu$ into $\e'$ gives
$\lambda z + \mu = z^3 + A(\lambda z + \mu)^2 z + B (\lambda z + \mu)^3$,
and so:
$$(1 + A \lambda^2 + B \lambda^3) z^3 
+ ( 2 A \lambda \mu + 3 B \lambda^2 \mu ) z^2 + \ldots = 0.$$
Let $(z_3, w(z_3))$ be the third point of intersection of
$\e'$ and the line $z = \lambda w + \mu$, so that $z_1,z_2,z_3$
are the roots of the above cubic, giving
that $z_1 + z_2 + z_3 = -(\hbox{coeff of }z^2)/(\hbox{coeff of }z^3)$,
so:
$$ z_3 = -z_1 - z_2 - {2 A \lambda \mu + 3 B \lambda^2 \mu\over
1 + A \lambda^2 + B \lambda^3} \in \Z[A,B][[z_1,z_2]],
$$
since the denominator is of the form $1 + \phi(z)$,
where $\phi(z)$ has no constant term [and so is an invertible
power series, with $1/(1 + \phi(z)) = 1 - \phi(z) + \phi(z)^2 + \ldots$].
The sum $(z_1,w_1) + (z_2,w_2) + (z_3,w_3) =$ the identity,
and so $(z_1,w_1) + (z_2,w_2) = -(z_3,w_3)$.
Negation $(x,y) \mapsto (x,-y)$ induces $(z,w)\mapsto (-z,-w)$
[since $z=-x/y, w=-1/y$], so that the
$z$-coordinate of $(z_1,w_1) + (z_2,w_2)$ is given
by $F_\e(z_1,z_2)$, where:
$$
F_\e(z_1,z_2)
= z_1 + z_2 + (\hbox{ terms of degree }\geqslant 2) \in \Z[A,B][[z_1,z_2]].
$$
But note that the expression for $z_3$ above consists
of the terms $z_1,z_2$, both homogeneous of weighted degree~$1$,
and the fraction whose numerator $2 A \lambda \mu + 3 B \lambda^2 \mu$
is homogeneous of weighted degree~$1$, and whose
denominator $1 + A \lambda^2 + B \lambda^3$ is homogeneous of
weighted degree~$0$. Therefore the final power series giving
the formal group must be homogeneous of weighted degree~$1$.
\par For the case when our curve is of the form $Y^2 = X^3 + AX$
(so that $B=0$),
each term of the formal group must be an integer multiple
of $A^k z_1^{n_1} z_2^{n_2}$.
Since the weighted degree is~1 and since $A$ has weight~$-4$,
we see that the degree purely in $z_1,z_2$ must by $\equiv 1$
mod~$4$, as required.
\par When our curve is of the form $Y^2 = X^3 + B$ (so that $A = 0$)
the fact that $B$ has weight~$-6$ similarly gives that
each term of the formal group has degree $\equiv 1$
mod~$6$ in $z_1,z_2$.
\vfil \eject %\end
\input amssym.def 
\input amssym.tex
%\def\Bbb{\bf}
%\nopagenumbers
%\magnification=\magstep1
%\hoffset=1truecm
%\voffset=2truecm
\baselineskip = 5.2 true mm
\font\frkkk=eufm10
\font\twelverm=cmr12
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\ninebf=cmbx9
\font\eightrm=cmr8
\font\sixrm=cmr6
\font\scrpp=eusm10 
\font\frkk=eufm10
\font\deffont=cmssi10
\font\chaptitle=cmbx10 at 14 pt
\tolerance=10000
\def\sqr{\ifmmode\square\else{$\square$}\fi}
\def\square{\vcenter{
            \hrule height.1mm
            \hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
            \hrule height.1mm}}                  % This is a slimmer sqr.
%\def\sqr{$\vcenter{\hrule height .3mm
%\hbox {\vrule width .3mm height 2mm \kern 1.4mm
%\vrule width .3mm} \hrule height .3mm}$}
%
\null
%
%\vsize=19.5 true cm
%\hsize=11.5 true cm
%\vskip 5 true cm
%\def\leqslant{\le}
\def\etq{{\cal E}_{\lower 1pt\hbox{\eightrm tors}}({\Bbb Q})}
\def\ctq{{\cal C}_{\lower 1pt\hbox{\eightrm tors}}({\Bbb Q})}
\def\cotq{{\cal C}_{\lower 1pt\hbox{\eightrm oddtors}}({\Bbb Q})}
\def\dotq{{\cal D}_{\lower 1pt\hbox{\eightrm oddtors}}({\Bbb Q})}
\def\c{{\cal C}}
\def\q{{\Bbb Q}}
\def\d{{\cal D}}
\def\e{{\cal E}}
\def\pk{\phi _\kappa}
\def\im{{\hbox{\sl im}}}
\def\hs{H_{\varsigma}}
\def\hpk{\hat \phi _\kappa}
\font\sc=cmssqi8 
\def\scc#1{\hbox{\sc #1}}
\def\sf{{\scc F}}
\def\pnbq{{\Bbb P}^n(\overline {\Bbb Q} )}
\def\hk{{\hat \kappa}}
\def\bq{{\overline {\Bbb Q}}}
\def\hq{{\hat q}}
\def\pv{\prod\limits_v }
\def\pnk{{\Bbb P}^n(K)}
\def\mnkvw{{\Bbb M}^n(K[{\bf v}^2,{\bf w}^2])}
\def\pnkv{{\Bbb P}^n(K[{\bf v}^2])}
\def\kj{\kappa (J)}
\def \qmods {{\Bbb Q}^*/({\Bbb Q}^*)^2}
\def \qmodss { {\Bbb Q}^*/({\Bbb Q}^*)^2 \times 
  {\Bbb Q}^*/({\Bbb Q}^*)^2 }
\def \qs{{\Bbb Q}^*}
\def \qss{({\Bbb Q}^*)^2}
\def\bbQ{{\Bbb Q}}
\def\bbF{{\Bbb F}}
\def\bbZ{{\Bbb Z}}
\def\bbR{{\Bbb R}}
\def\bbC{{\Bbb C}}
\def\Q{{\Bbb Q}}
\def\F{{\Bbb F}}
\def\Z{{\Bbb Z}}
\def\R{{\Bbb R}}
\def\C{{\Bbb C}}
%
\chaptitle
\noindent
\centerline{Elliptic Curves. Solutions to Sheet 4.}
\rm
\bigskip
\noindent {\bf 1.} In all of the following, we use
the result from lectures that (when the coefficients
of $\cal E$ are in $\Bbb Z$) $\etq$ is isomorphic to a subgroup
of $\widetilde {\cal E}$ mod~$p$, where $p\not=2$ is a prime
not dividing the discriminant. Note that this typically
gives a much faster way of computing $\etq$ than the
Nagell-Lutz result. N.B. (a),(b),(c) are about the level that
could be asked as part of a 3-hour exam.
\par\noindent {\bf (a).} There are the obvious points
$P = (0,1)$ of order~$3$ and $Q = (-1,0)$ of order~$2$ in $\etq$,
which generate a subgroup of $\etq$ of size~$6$ (namely,
the~$6$ points $mP+nQ$ for $0\leqslant m \leqslant 2$ and
$0\leqslant n \leqslant 1$). Further, $\Delta = 4A^3 + 27B^2 = 27$,
so we can reduce modulo any prime except~$2$ (which must always
be avoided) and~$3$. Over ${\Bbb F}_5$, there are only
six points: ${\bf o}, (0,\pm 1), (2,\pm 3), (4,0)$. So, we conclude
that $\etq$ has size at most~$6$, which means that it consists
of precisely the $C_6 = C_2\times C_3$ group
of points we have found already.
\par Note that, if $P=(0,1)$ and $Q=(-1,0)$, then the complete
list of torsion points is: ${\bf o}, P = (0,1), 2P = (0,-1),
Q = (-1,0), P+Q = (2,-3), 2P+Q = (2,3)$.
\par\noindent {\bf (b).} Here, the (birational over~$\Bbb Q$)
transformation $(X,Y) \mapsto (X-1,Y)$ takes the given
curve to: $Y^2 = X(X+1)(X-1) = X^3 - X$, which has discriminant $-4$, 
and so we can reduce modulo the prime~$3$
Over~${\Bbb F}_3$
there are the points: ${\bf o}, (0,0), (1,0), (2,0)$ giving
that $\etq$ has size at most~$4$. But, in fact, $\etq$
contains ${\bf o}, (0,0), (-1,0), (1,0)$, which means
the this $C_2\times C_2$ group gives all of $\etq$.
[{\it Alternatively, even without using a birational transformation
to the form $Y^2=X^3 + AX + B$, we could just work entirely
with the given equation of the curve, noting that
the original cubic $X(X-1)(X-2)$ has no repeated
roots~mod~$3$, so that $Y^2 = X(X-1)(X-2)$ is an elliptic curve
mod~$3$, and then noting that the only points are:
${\bf o}, (0,0), (1,0), (2,0)$.}]
\par\noindent {\bf (c).} The (birational over~$\Bbb Q$)
transformation $(X,Y) \mapsto (3^2X, 3^3Y)$ takes the
given curve to: $Y^2 = X^3 + 1$ which we have already seen
in part~(a) to have a $C_2\times C_3$ group as its
torsion group.
\par Note that, if $P = (0,1/27)$ and $Q = (-1/9,0)$ then the
complete list of torsion points is given by: ${\bf o}, P=(0,1/27),
2P=(0,-1/27), Q = (-1/9,0), P+Q = (2/9,-1/9), 2P+Q = (2/9,1/9)$.
%\par\noindent {\bf (d). [optional]} The discriminant of $X^3 - 219X + 1654$
%is $\Delta = 4(-219)^3 + 27\cdot 1654^2 = 31850496 = 2^{17}3^5$, so we need
%only avoid the primes~$2,3$ (alternatively, it would be
%sufficient to compute that $\Delta \not\equiv 0$ mod~$5$, since
%that is all we shall require). 
%Reducing modulo~$5$ gives the
%nine points: ${\bf o}, (0,\pm 2), (1,\pm 1), (2,\pm 2), (3,\pm 2)$,
%and so $\etq$ has size at most~$9$. A short integer search for possible
%$x$-coordinates reveals the point $P = (11,24)$ of order~$9$, as can
%be checked by computing $P,2P,3P,\ldots, 9P = {\bf o}$). Hence,
%$\etq$ is just the $C_9$ group consisting of these points.
%\par Note that, if $P = (11,24)$, then the complete list of torsion
%points is: ${\bf o}, P = (11,24), 2P = (-13,48), 3P = (3,-32),
%4P = (35,-192), 5P = (35,192), 6P = (3,32), 7P = (-13,-48), 8P = (11,-24)$.
%%%\par\noindent {\bf (c).} There are the obvious points: ${\bf o},
%%%(0,0), (-1,0),(-4,0)$, all of order~$2$ in $\etq$. There's a further
%%%obvious point: $(2,6)$, and note that $2(2,6) = (0,0)$ so that
%%%$(2,6) \in \etq$ also, and is of order~$4$. The points $P = (-1,0)$ 
%%%and $Q = (2,6)$ generate a $C_2 \times C_4$ group in $\etq$
%%%whose members are: $mP + nQ$ for $0\leqslant m \leqslant 1$ 
%%%and $0\leqslant n \leqslant 3$. So, this group of size~$8$
%%%is a subgroup of $\etq$. Now, over~$\Bbb Q$, we can transform $\cal E$
%%%(after the map: $(x,y)\mapsto (9x+15,27y)$) to
%%%the curve: $Y^2 = X^3 - 351X + 1890$. This new cubic has
%%%discriminant $4(-351)^3 + 27(1890)^3 = -76527504 = 2^4 3^{14}$,
%%%and so we only need to avoid the primes~$2,3$. [N.B. If you don't
%%%like the idea of factorising a number like $76527504$,
%%%you can just observe that a map $x \mapsto kx + \ell$ only
%%%changes the discriminant of a polynomial by a power of $k$,
%%%and so we only need to avoid the primes dividing the discriminant
%%%of $X(X+1)(X+4)$ which is ~$144$ (i.e. the primes~$2,3$) plus
%%%any primes dividing the coefficient $9$ in ``$9x+15$''.
%%%This gives a computationally easier way to see that we only   
%%%need to avoid the primes~$2,3$]. Reducing $Y^2 = X^3 - 351X + 1890$
%%%modulo~$5$ gives: $Y^2 = X^3 - X$ [N.B. The fact that $4(-1)^3 + 27\cdot 0^2
%%%\not\equiv 0$ mod~$5$ gives a further independent proof that~$5$
%%%is a legitimate choice of prime].
%%%This has the
%%%points: ${\bf o}, (0,0), (1,0), (2,\pm 1), (3,\pm 2), (4,0)$
%%%over ${\Bbb F}_5$, and so $\etq$ has size at most~$8$. Hence,
%%%$\etq$ is precisely the $C_2\times C_4$ group of points
%%%given above.   
%\par\noindent {\bf (c).} There are the obvious $2$-torsion points
%${\bf 0}, (0,0), (-81,0), (-256,0)$.  
%A short integer search for possible further points reveals:
%$P = (24,840)$. Note that $2P = (144,-3600)$ and $4P = 2(144,-3600)
%= (0,0)$, so that $8P = 2(0,0) = {\bf o}$, which means that
%$P \in \etq$ and is of order~$8$. The point~$P$, together
%with the independent point~$Q=(-81,0)$ of order~$2$, generate
%a $C_2\times C_8$ group, which is a subgroup of $\etq$.
%Finally, if we reduce our curve modulo~$2,3,5,7$, the corresponding reduced
%curves are, respectively: $Y^2 = X(X+1)X,\ Y^2 = X^2(X+1),\ Y^2 = X(X+1)^2,\
%Y^2 = X(X+4)^2$, each of which has repeated roots and so
%not an elliptic curve (N.B.\ {\it there is no need
%to transform to the form
%$Y^2 = X^3 + AX + B$}).
%The first success is when $p=11$, when the
%curve reduces to $Y^2 = X(X+4)(X+3) = X^3 + 7X^2 + X$,
%which is an elliptic curve (mod~11), since there are no repeated
%roots~(mod~11). So, we can compute
%all points on the elliptic curve $Y^2 = X^3 + 7X^2 + X$ mod~$11$,
%and we find
%a total of~$16$ points, given by:
%${\bf o}, (0,0), (1,3), (1,8), (2,4), (2,7), (3,4), (3,7)$, 
%$(4,2), (4,9), (6,1), (6,10), (7,0), (8,0), (10,4), (10,7)$.
%This means that $\etq$ consists
%precisely of the~$16$ points given above.
%\par Note that, if $P=(24,840)$ and $Q = (-81,0)$, then the complete
%list of torsion points is given by: ${\bf o}, P = (24,840), 2P = (144,-3600),
%3P = (864,30240), 4P = (0,0), 5P = (864,-30240), 6P = (144,3600),
%7P = (24,-840), Q = (-81,0), P+Q = (-216,1080), 2P+Q = (-144,-1008),
%3P+Q = (-96,480), 4P+Q = (-256,0), 5P+Q = (-96,-480),
%6P+Q = (-144,1008), 7P+Q = (-216,-1080)$.
%\par\noindent {\bf (d).} Here, the (birational over~$\Bbb Q$)
%transformation $(X,Y) \mapsto (X-1,Y)$ takes the given
%curve to: $Y^2 = X(X+1)(X-1) = X^3 - X$, which has discriminant $-4$, 
%and so we can reduce modulo the prime~$3$
%Over~${\Bbb F}_3$
%there are the points: ${\bf o}, (0,0), (1,0), (2,0)$ giving
%that $\etq$ has size at most~$4$. But, in fact, $\etq$
%contains ${\bf o}, (0,0), (-1,0), (1,0)$, which means
%the this $C_2\times C_2$ group gives all of $\etq$.
%[{\it Alternatively, even without using a birational transformation
%to the form $Y^2=X^3 + AX + B$, we could just work entirely
%with the given equation of the curve, noting that
%the original cubic $X(X-1)(X-2)$ has no repeated
%roots~mod~$3$, so that $Y^2 = X(X-1)(X-2)$ is an elliptic curve
%mod~$3$, and then noting that the only points are:
%${\bf o}, (0,0), (1,0), (2,0)$.}]
%\par\noindent {\bf (e).} The (birational over~$\Bbb Q$)
%transformation $(X,Y) \mapsto (3^2X, 3^3Y)$ takes the
%given curve to: $Y^2 = X^3 + 1$ which we have already seen
%in part~(a) to have a $C_2\times C_3$ group as its
%torsion group.
%\par Note that, if $P = (0,1/27)$ and $Q = (-1/9,0)$ then the
%complete list of torsion points is given by: ${\bf o}, P=(0,1/27),
%2P=(0,-1/27), Q = (-1/9,0), P+Q = (2/9,-1/9), 2P+Q = (2/9,1/9)$.
%\par\noindent {\bf (f).} The (birational over~$\Bbb Q$) map
%$(X,Y) \mapsto ( 4X , 8Y + 4)$ takes the given curve
%to the curve: $Y^2 = X^3 - 16X + 848$. The discriminant
%$4(-16)^3 + 27(848)^2 \equiv 1\cdot 2^3 + 0 \equiv 2$ mod~$3$,
%so that $3$ does not divide~$4(-16)^3 + 27(848)^2$, and so it's
%legitimate to reduce mod~$3$.
%The reduced curve mod~$3$ is:
%$Y^2 = X^3 + 2X + 2$ which has {\bf o} as its only point.
%It follows that $\etq$ contains only {\bf o}, also.
%%\par\noindent {\bf (h).} $Y^2 = X^3 - X^2 + 1/4$.
\medskip\noindent
{\bf 2.} Let $\phi : \c (\q ) \rightarrow \d (\q)$
be the usual isogeny, which is a group homomorphism with
kernel: ${\bf o}, (0,0)$, and let $\hat\phi : \d (\q ) \rightarrow \c (\q)$
be the usual dual isogeny, which is also a group homomorphism with 
kernel: ${\bf o}, (0,0)$. Now, let $\cotq$ be the set of torsion
elements of $\c (\q)$ which have odd order. First check
that $\cotq$ is a subgroup: (1) The identity {\bf o} has order~1,
which is odd, so ${\bf o}\in \cotq$, (2) If $P,Q$ have odd torsion
orders $m,n$, respectively, then $mn(P+Q) = n(mP) + m(nQ) = {\bf o}$
and so the order of~$P+Q$ divides $mn$, giving that the order
of $P+Q$ is odd, i.e.\ $P+Q
\in \cotq$, (3) The order of $-P$ is the same as the order
of $-P$, so $P\in\cotq \Rightarrow -P \in \cotq$. Similarly
define $\dotq$, a subgroup of $\d (\q)$. 
\par
Now, consider any $P\in \cotq$. Then $P$ must have odd
order~$m$, say. Let $R = \phi (P)$. Then $mR = m\phi(P)
= \phi (mP) = \phi ({\bf o}) = {\bf o}$, which means
that the order of~$R$ divides~$m$, and so the order
of~$R$ is odd; that is: $R\in \dotq$. Hence, $\phi$
gives a map from $\cotq$ to $\dotq$, which certainly satisfies
the homomorphism property $\phi (P+Q) = \phi(P) + \phi(Q)$
for all $P,Q\in \cotq$, since
$\phi$ satisfies this property on the larger set $\c (\q )$.
Furthermore,
the kernel of $\phi : \cotq \rightarrow \dotq$ must only
contain {\bf o} [since $(0,0) \not\in \cotq$], and so
$\phi : \cotq \rightarrow \dotq$ is an injection [any homomorphism
with trivial kernel is an injection]. We have therefore
established that there is an injective homomorphism
(namely $\phi$) from $\cotq$ to $\dotq$, which implies
that $\cotq$ is isomorphic to a subgroup of $\dotq$, namely
the subgroup $\phi (\cotq))$ [note, since $\cotq$, $\dotq$
are finite, it follows from this that $\# \cotq
= \# \phi (\cotq)) \leqslant \# \dotq$]. (We have just used
here the general fact that if $\theta$ is a homomorphism
from group~$G$ to group~$H$, then $G / \hbox{ker}\theta$
is isomorphic to $\hbox{im}\theta$, which is the same
as $\theta(G)$; when $\theta$ is injective, $\hbox{ker}\theta$
contains only the identity element and $G / \hbox{ker}\theta$
can be replaced by~$G$).
Applying the same argument to $\hat\phi : \dotq \rightarrow \cotq$
gives that $\dotq$ is isomorphic to a subgroup of $\cotq$,
namely $\hat\phi ( \dotq )$ [and consequently  $\# \dotq 
= \# \hat\phi ( \dotq ) \leqslant
\# \cotq$]. So, all of $\cotq, \dotq, \hat\phi ( \dotq ),
\hat\phi ( \dotq )$ must have the same number of elements.
Combining the fact that $\phi (\cotq))$ is a subgroup of
$\dotq$ and the fact that $\# \phi (\cotq))
= \# \dotq$ gives that $\phi (\cotq))$ must be equal
to $\dotq$. But $\cotq$ is isomorphic to $\phi (\cotq))$
which is equal to $\dotq$; hence
$\cotq$ is isomorphic to $\dotq$, as required.
\medskip\noindent {\bf 3.}
The preimages of~$(0,0)$ under $\hat\phi$
are given by the points of order~2 on $\d$ distinct from~$(0,0)$,
namely $Q_1 = ((-a_1 + \sqrt{a_1^2 - 4b_1})/2,0) = (a + 2\sqrt{b},0)$ and
$Q_2 = ((-a_1 - \sqrt{a_1^2 - 4b_1})/2,0) = (a - 2\sqrt{b},0)$.
Recall
the standard map from lectures $q : \d (\q) \rightarrow \qmods$
which takes ${\bf o} \rightarrow 1$, $(0,0) \rightarrow b_1$,
and otherwise takes $(u,v) \rightarrow u$. We know from lectures
that this map has kernel precisely $\phi ( \c (\Q ))$.
Now, the multiplication by 2 map on $\c (\Q)$ is $\hat\phi \circ \phi$,
and so $(0,0) \in 2\c (\Q)$ iff either $Q_1$ or $Q_2$
is a member of $\phi (\c (\Q) ) \iff
q(Q_1) = 1 \hbox{ or } q(Q_2) = 1 \iff
a+2\sqrt{b}  \hbox{ or } a-2\sqrt{b}= 1 \in \qmods \iff
a+2\sqrt{b} \hbox{ or } a-2\sqrt{b} \in \qss
\iff b = m^2 \hbox{ and } a+2m = n^2$, for some $m,n \in \Q$; but in fact
$m,n$ must be in $\Z$ since $a,b\in \Z$.
\medskip\noindent
{\bf 4.}
\par\noindent
%{\bf (a).}
%Let $\c : Y^2 = X(X^2 + aX + b) = X(X^2 + 3X + 5)$,
%where $a=3, b=5$,
%and isogenous curve $\d : Y^2 = X(X^2 + a_1X  + b_1 ) = X(X^2 - 6X -11)$,
%where $a_1 = -2a = -6, b_1= a^2 - 4b = -11$,
%with the usual isogeny $\phi : \c (\Q ) \rightarrow 
%\d (\Q) : (x,y) \mapsto (y^2/x^2 , y - 5y/x^2)$,
%and dual isogeny $\hat\phi : \d (\Q ) \rightarrow 
%\c (\Q) : (u,v) \mapsto ( {1\over 4} v^2/u^2 , {1\over 8}( v + 11v/u^2) )$. 
%\par
%The map $q : \d (\Q) / \phi (\c (\Q)) \mapsto \qmods : (u,v) \mapsto u$,
%for $(u,v) \not= (0,0)$, with $q : (0,0) \mapsto b_1$
%and $q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}q$
%contained in $\{ d : d\hbox{ is square free and } d | b_1\}
%= \{ \pm 1 , \pm 11 \}$. Also, ${\bf o} \mapsto 1$,
%$(0,0) \mapsto -11$ and the obvious point $(-1,2) \mapsto -1$, so that
%$1,-11,-1 \in \hbox{im} q$; but $\hbox{im} q$ is a group, so
%$11 \in \hbox{im} q$ also, and indeed we can just take:
%$(0,0) + (-1,2) = (11,22)$, which maps to $11$ under $q$.
%Hence,
%$\{ \pm 1,\pm 11 \} \subset \hbox{im} q \subset \{ \pm 1 , \pm 11\}$,
%that is $\hbox{im} q  = \{ \pm 1 , \pm 11\}$, and so
%$\d (\Q) / \phi (\c (\Q)) = \{ {\bf o}, (0,0), (-1,2), (11,22)\}$,
%that is, $\d (\Q) / \phi (\c (\Q))$ is generated by~$(0,0),(-1,2)$.
%\par
%The map $\hat q : \c (\Q ) / \hat\phi (\d (\Q))
%\mapsto \qmods : (u,v) \mapsto u$,
%for $(u,v) \not= (0,0)$, with $\hat q : (0,0) \mapsto a_1^2 - 4b_1 = b$
%and $\hat q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}\hat q$
%contained in $\{ d : d\hbox{ is square free and } d | b\}
%= \{ \pm 1 , \pm 5\}$. 
%Also, ${\bf o} \mapsto 1$ and
%$(0,0) \mapsto 5$, so that
%$\{ 1,5 \} \subset \hbox{im} \hat q \subset \{ \pm 1 , \pm 5\}$.
%\par There is only one coset to check, represented by $-1$, say.
%We know that $-1 \in \hbox{im} \hat q$ iff there are integers
%$\ell , m , n$,
%not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:
%$(-1)\cdot \ell^4 + a \ell^2m^2 + (b/(-1))\cdot m^4 = n^2$;
%that is: $-\ell^4 + 3\ell^2m^2 - 5 m^4 = n^2$.
%Multiply both sides by 4 and rewrite
%as: $ - (  2\ell^2 - 3 m^2 )^2 - 11 m^4 = 4 n^2$. We can see that
%the LHS is $\leqslant 0$ and the RHS is $\geqslant 0$,
%and the equation is satisfied iff $(  2\ell^2 - 3 m^2 ) = 11 m^4 = 
%4 n^2 = 0$. From this we see that $m=n=0$, which when combined
%with $2\ell^2 - 3 m^2 = 0$ gives that $\ell = 0$, also, which
%is a contradiction.
%Hence $-1 \not\in \hbox{im} \hat q$.
%\par  We conclude that $\hbox{im} \hat q  = \{ 1,5 \}$, and    
%so $\c (\Q) / \hat\phi (\d (\Q))$ is generated by~$(0,0)$.
%\par Finally, since multiplication by 2 in $\c (\Q)$
%is $\hat\phi \circ \phi$,
%we have that $\c (\Q) / 2\c (\Q)$ is generated by: generators for
%$\c (\Q) / \hat\phi (\d (\Q))$ [namely: $(0,0)$] together with
%the images under $\hat \phi$ of generators for $\d (\Q) / \phi (\c (\Q))$
%[namely, $\hat\phi \bigl( (0,0) \bigr) = {\bf o}$ and
%$\hat\phi \bigl( (-1,2) \bigr) = (1,3)$]. Conclusion:
%$\c (\Q ) / 2\c(\Q )$ is generated by $(0,0)$ and $(1,3)$
%and so is the group $C_2\times C_2$. 
%Now $\c (\q)/2\c (\q)$ is isomorphic to $\ctq/2\ctq \times C_2^{rank}$, and
%$\ctq /2\ctq$ is isomorphic to the $2$-torsion group of $\ctq$
%which is $C_2$ (consisting only of {\bf o} and $(0,0)$), so that
%$\ctq/2\ctq$ is isomorphic to $C_2$. Conclusion: rank $=1$.
%\par\noindent
%{\bf (a)} 
%Let $\c : Y^2 = X(X^2 + aX + b) = X(X^2 + 5X - 5)$,
%where $a=5, b=-5$,
%and isogenous curve
%$\d : Y^2 = X(X^2 + a_1X  + b_1 ) = X(X^2 - 10X + 45)$,
%where $a_1 = -10, b_1=45$,
%with the usual isogeny $\phi : \c (\Q ) \rightarrow
%\d (\Q) : (x,y) \mapsto (y^2/x^2 , y + 5y/x^2)$,
%and dual isogeny $\hat\phi : \d (\Q ) \rightarrow
%\c (\Q) : (u,v) \mapsto ( {1\over 4} v^2/u^2 ,
%{1\over 8}( v - 45 v/u^2) )$.
%%{\bf [2~marks]}
%\par
%The map $q : \d (\Q) / \phi (\c (\Q)) \rightarrow \qmods : (u,v) \mapsto u$,
%for $(u,v) \not= (0,0)$, with $q : (0,0) \mapsto b_1$
%and $q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}q$
%contained in $\{ d : d\hbox{ is square free and } d | b_1\} 
%= \{ \pm 1 , \pm 3, \pm 5, \pm 15 \}$. Also, ${\bf o} \mapsto 1$,
%$(0,0) \mapsto 45 = 5$.
%Hence,
%$\{ 1, 5 \} \subset \hbox{im} q \subset \{ \pm 1 , \pm 3, \pm 5, \pm 15 \}$.
%%{\bf [3 marks]}
%\par
%There are only three cosets to check, represented by $-1,3,-3$, say.
%We know that $-1 \in \hbox{im} q$ iff there are integers $\ell , m , n$,
%not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:
%$(-1)\cdot \ell^4 + a_1 \ell^2m^2 + (b_1/(-1))\cdot m^4 = n^2$
%that is: $-\ell^4 - 10 \ell^2m^2  - 45 m^4 = n^2$.
%We can see that
%the LHS is $\leqslant 0$ and the RHS is $\geqslant 0$,
%and there is equality iff $\ell =  m = n = 0$, a contradiction.
%Hence $-1 \not\in \hbox{im} q$. Similarly $-3 \not\in \hbox{im} q$.
%We know that $3 \in \hbox{im} q$ iff there are integers $\ell , m , n$,
%not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:    
%$3\cdot \ell^4 + a_1 \ell^2m^2 + (b_1/3)\cdot m^4 = n^2$
%that is: $3\ell^4 - 10 \ell^2m^2  + 15 m^4 = n^2$.
%Rewrite as: $(3\ell^2 - 5 m^2)^2 + 20 m^4 = 3 n^2$.
%Reducing modulo~5
%gives: $ ( 3 \ell^2 - 5 m^2 )^2 \equiv 3 n^2$ (modulo~5). If $n$ were
%coprime to~$5$, then this would give: $( 3 \ell^2 / n)^2 = 3$
%in $\F_5$, contradicting the fact that~$3$
%is not a quadratic residue modulo~5. So,
%$5 | n$ and so $5 | ( 3\ell^2 - 5 m^2 )$, also. Hence $5^2$ divides
%$( 3\ell^2 - 5 m^2 )^2$ and $3 n^2$ and so must divide $20 m^4$;
%but $20$ is only divisible by $5$ (not by~$5^2$) so that $5$ must divide
%$m^4$; hence $5$ divides $m$. Furthermore, the fact (already
%found) that
%$5 | ( 3 \ell^2 - 5 m^2 )$ gives that $5 | 3\ell^2$,
%and so $5 | \ell$ also. We've shown
%that $5$ divides both of $\ell,m$, which contradicts
%the fact that $\hbox{gcd}(\ell,m) = 1$.
%Hence $3 \not\in \hbox{im} \hat q$.
%%{\bf [8 marks]}
%\par We conclude that $\hbox{im} q = \{ 1,5 \}$ and that
%$\d (\Q) / \phi (\c (\Q)) = \{ {\bf o}, (0,0)\}$,
%and so $\d (\Q) / \phi (\c (\Q))$ is generated by $(0,0)$.
%%{\bf [1 mark]}
%\par
%The map $\hat q : \c (\Q ) / \hat\phi (\d (\Q))
%\rightarrow \qmods : (x,y) \mapsto x$,
%for $(x,y) \not= (0,0)$, with $\hat q : (0,0) \mapsto a_1^2 - 4b_1 = b$
%and $\hat q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}\hat q$
%contained in $\{ d : d\hbox{ is square free and } d | b\}
%= \{ \pm 1, \pm 5 \}$. 
%Also, ${\bf o} \mapsto 1$,
%$(0,0) \mapsto -5$, and the obvious point $(-1,3) \mapsto -1$,
%which imply that $(0,0)+(-1,3) = (5, 15) \mapsto 5$,
%so that
%$\{ \pm 1 , \pm 5\} \subset \hbox{im} \hat q \subset \{ \pm 1 , \pm 5\}$.
%%{\bf [5 marks]}
%\par We conclude that $\hbox{im} \hat q = \{ \pm 1 , \pm 5\}$ and
%$\c (\Q) / \hat\phi (\d (\Q)) = 
%\{ {\bf o}, (0,0), (-1,3), (5, 15)\}$, so that
%$\c (\Q) / \hat\phi (\d (\Q))$ is generated by~$(0,0), (-1,3)$.
%%{\bf [2 marks]}
%\par Finally, since multiplication by 2 in $\c (\Q)$
%is $\hat\phi \circ \phi$,
%we have that $\c (\Q) / 2\c (\Q)$ is generated by: generators for
%$\c (\Q) / \hat\phi (\d (\Q))$ [namely: $(0,0), (-1,3)$] together with
%the images under $\hat \phi$ of generators for $\d (\Q) / \phi (\c (\Q))$
%[namely, $\hat\phi \bigl( (0,0) \bigr) = {\bf o}$]. Conclusion:
%$\c (\Q ) / 2\c(\Q )$ is generated by $(0,0), (-1,3)$,
%and so is the group $C_2 \times C_2$.
%Now $\c (\q)/2\c (\q)$
%is isomorphic to $\ctq/2\ctq \times C_2^{rank}$, and
%$\ctq /2\ctq$ is isomorphic to the $2$-torsion group of $\ctq$
%which is $C_2$ (consisting only of {\bf o} and $(0,0)$, since
%$x^2 + 5x - 5$ has no $\Q$-rational roots),
%so that
%$\ctq/2\ctq$ is~$C_2$. Conclusion: rank $=1$.
\par\noindent{\bf (a).}
Let $\c : Y^2 = X(X^2 + aX + b) = X(X^2 + 2X + 3)$,
where $a=2, b=3$,
and isogenous curve $\d : Y^2 = X(X^2 + a_1X + b_1) = X(X^2 - 4X - 8)$,
where $a_1 = -4, b_1=-8$,
with the usual isogeny $\phi : \c (\Q ) \rightarrow 
\d (\Q) : (x,y) \mapsto (y^2/x^2 , y - 3y/x^2)$,
and dual isogeny $\hat\phi : \d (\Q ) \rightarrow 
\c (\Q) : (u,v) \mapsto ( {1\over 4} v^2/u^2 , {1\over 8}( v + 8v/u^2) )$. 
%{\bf [3~marks]}
\par
The map $q : \d (\Q) / \phi (\c (\Q)) \rightarrow \qmods : (u,v) \mapsto u$,
for $(u,v) \not= (0,0)$, with $q : (0,0) \mapsto b_1$
and $q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}q$
contained in $\{ d : d\hbox{ is square free and } d | b_1\}
= \{ \pm 1 , \pm 2 \}$. Also, ${\bf o} \mapsto 1$,
$(0,0) \mapsto -8 = -2$, so that
$\{ 1,-2 \} \subset \hbox{im} q \subset \{ \pm 1 , \pm 2\}$.
%{\bf [3 marks]}
\par
There is only one coset to check, represented by $-1$, say.
We know that $-1 \in \hbox{im} q$ iff there are integers $\ell , m , n$,
not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:
$(-1)\cdot \ell^4 + a_1 \ell^2m^2 + (b_1/(-1))\cdot m^4 = n^2$
that is: $-\ell^4 - 4 \ell^2m^2  + 8 m^4 = n^2$.
Rewrite as: $-(\ell^2 + 2m^2)^2 + 12 m^4 = n^2$. Reducing modulo~3
gives $ - (\ell^2 + 2m^2 )^2 \equiv n^2$ (modulo~3).
If $n$ were
coprime to~$3$, then this would give: $(( \ell^2 + 2 m^2 )/n)^2 = -1$
in $\F_3$, contradicting the fact that~$-1$
is not a quadratic residue modulo~3. So,  
$3 | n$ and so $3 | (\ell^2 + 2m^2 )$ also. This means that
$9 | (\ell^2 + 2m^2 )^2$ and $9 | n^2$, which can be combined
with $-(\ell^2 + 2m^2)^2 + 12 m^4 = n^2$ to give: $9 | 12 m^4$
and so $3 | m$. Combining $3 | m$ with $3 | (\ell^2 + 2m^2 )$
gives that $3 | \ell$. 
This
contradicts the fact that $\hbox{gcd}(\ell,m) = 1$. Hence
our equation is impossible in~$\Q_3$, and so impossible in~$\Q$.
Hence $-1 \not\in \hbox{im} q$.
%{\bf [6 marks]}
\par We conclude that $\hbox{im} q  = \{ 1,-2 \}$, and
so $\d (\Q) / \phi (\c (\Q))$ is generated by~$(0,0)$.
%{\bf [1 mark]}
\par
The map $\hat q : \c (\Q ) / \hat\phi (\d (\Q))
\rightarrow \qmods : (x,y) \mapsto x$,
for $(x,y) \not= (0,0)$, with $\hat q : (0,0) \mapsto b$
and $\hat q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}\hat q$
contained in $\{ d : d\hbox{ is square free and } d | b\}
= \{ \pm 1 , \pm 3 \}$.
Also, ${\bf o} \mapsto 1$ and
$(0,0) \mapsto 3$, so that
$\{ 1,3 \} \subset \hbox{im} \hat q \subset \{ \pm 1 , \pm 3\}$.
%{\bf [3 marks]}
\par There is only one coset to check, represented by $-1$, say.
We know that $-1 \in \hbox{im} \hat q$ iff there are integers
$\ell , m , n$,
not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:
$(-1)\cdot \ell^4 + a \ell^2m^2 + (b/(-1))\cdot m^4 = n^2$;
that is: $-\ell^4 + 2\ell^2m^2  - 3 m^4 = n^2$.
Rewrite
as: $ - ( \ell^2 - m^2 )^2 - 2 m^4 =  n^2$. This is impossible
in~$\R$ (the left hand side is $\leqslant 0$ and the
right hand side is $\geqslant 0$, and equality only occurs when
$\ell^2 - m^2 = m^4 = n^2 = 0$, implying $\ell = m = n = 0$, which is
not allowed).
Hence $-1 \not\in \hbox{im} \hat q$.
%{\bf [4 marks]}
\par  We conclude that $\hbox{im} \hat q  = \{ 1,3 \}$, and    
so $\c (\Q) / \hat\phi (\d (\Q))$ is generated by~$(0,0)$.
%{\bf [1 mark]}
\par Finally, since multiplication by 2 in $\c (\Q)$
is $\hat\phi \circ \phi$,
we have that $\c (\Q) / 2\c (\Q)$ is generated by: generators for
$\c (\Q) / \hat\phi (\d (\Q))$ [namely: $(0,0)$] together with
the images under $\hat \phi$ of generators for $\d (\Q) / \phi (\c (\Q))$
[namely, $\hat\phi \bigl( (0,0) \bigr) = {\bf o}$]. Conclusion:
$\c (\Q ) / 2\c(\Q )$ is generated by $(0,0)$, and so is isomorphic
to $C_2$. We also know that $\c (\Q ) / 2\c(\Q )$ is isomorphic to
$\ctq / 2\ctq \times C_2^r$,
which is isomorphic to $\c (\Q )[2] \times C_2^r$, where $\c (\Q )[2]$
is the $2$-torsion group and $r$ is the rank. The $2$-torsion points
on $\c : Y^2 = X(X^2 + 2X + 3)$ are {\bf o} together with the points
of the form $(x,0)$, where $x$ is a root of $X(X^2 + 2X + 3)$, that is:
$(0,0)$, $(-1 + \sqrt{-2}, 0)$ and $(-1 + \sqrt{-2}, 0)$, of which
only {\bf o} and $(0,0)$ are in $\c (\Q )[2]$, giving that
$\c (\Q )[2]$ is isomorphic to $C_2$. Combining this with the facts
(already found) that
$\c (\Q ) / 2\c(\Q )$ is isomorphic both to $C_2$ and to
$\c (\Q )[2] \times C_2^r$, give that
$\c (\Q)$ has rank~0.
\par\noindent
{\bf (b).} Let $\c : Y^2 = X(X^2 + aX + b) = X(X^2 + 14X + 1)$,
where $a=14, b=1$,
and isogenous curve $\d : Y^2 = X(X^2 + a_1X  + b_1 ) = X(X^2 - 28X +192)$,
where $a_1 = -28, b_1=192$,
with the usual isogeny $\phi : \c (\Q ) \rightarrow 
\d (\Q) : (x,y) \mapsto (y^2/x^2 , y - y/x^2)$,
and dual isogeny $\hat\phi : \d (\Q ) \rightarrow 
\c (\Q) : (u,v) \mapsto ( {1\over 4} v^2/u^2 , {1\over 8}( v - 192 v/u^2) )$. 
\par
The map $q : \d (\Q) / \phi (\c (\Q)) \mapsto \qmods : (u,v) \mapsto u$,
for $(u,v) \not= (0,0)$, with $q : (0,0) \mapsto b_1$
and $q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}q$
contained in $\{ d : d\hbox{ is square free and } d | b_1\}
= \{ \pm 1 , \pm 2, \pm 3, \pm 6 \}$. Also, ${\bf o} \mapsto 1$,
$(0,0) \mapsto 192 = 3$ and the obvious point $(8,16) \mapsto 2$
[N.B. when searching for a point in~$\d (\Q)$ which might
map to~$2$ under~$q$, one need only try points with $x$-coordinate
equal to~$2$ modulo squares, e.g.~2,8,1/2,18,etc, so one should
find the point $(8,16)$ quickly; also, its a good idea at the
outset just to look for ``obvious'' members of $\d (\q )$
with $x$ coordinates being integers in the range from $-10$ to $10$;
doing this at the outset would also reveal the point $(8,16)$.]
This means that
$1,3,2 \in \hbox{im} q$; but $\hbox{im} q$ is a group, so
$6 \in \hbox{im} q$ also, and indeed we can just take:
$(0,0) + (8,16) = (24,-48)$, which maps to $6$ under $q$.
Hence,
$\{ 1,2,3,6 \} \subset \hbox{im} q \subset \{ \pm 1 , \pm 2,\pm 3, \pm 6\}$.
\par
There is only one coset to check, represented by $-1$, say.
We know that $-1 \in \hbox{im} q$ iff there are integers $\ell , m , n$,
not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:
$(-1)\cdot \ell^4 + a_1 \ell^2m^2 + (b_1/(-1))\cdot m^4 = n^2$
that is: $-\ell^4 - 28 \ell^2m^2  - 192 m^4 = n^2$.
We can see that
the LHS is $\leqslant 0$ and the RHS is $\geqslant 0$,
and there is equality iff $\ell =  m = n = 0$, a contradiction.
Hence $-1 \not\in \hbox{im} q$. We conclude
that $\hbox{im} q = \{ 1,2,3,6 \}$ and that
$\d (\Q) / \phi (\c (\Q)) = \{ {\bf o}, (0,0), (8,16), (24,-48) \}$,
and so $\d (\Q) / \phi (\c (\Q))$ is generated by $(0,0)$ and $(8,16)$.
\par
The map $\hat q : \c (\Q ) / \hat\phi (\d (\Q))
\mapsto \qmods : (u,v) \mapsto u$,
for $(u,v) \not= (0,0)$, with $\hat q : (0,0) \mapsto a_1^2 - 4b_1 = b$
and $\hat q: {\bf o} \mapsto 1$, is an injection with $\hbox{im}\hat q$
contained in $\{ d : d\hbox{ is square free and } d | b\}
= \{ \pm 1 \}$. 
Also, ${\bf o} \mapsto 1$ and
$(0,0) \mapsto 1$, so that
$\{ 1 \} \subset \hbox{im} \hat q \subset \{ \pm 1 \}$.
\par There is only one coset to check, represented by $-1$, say.
We know that $-1 \in \hbox{im} \hat q$ iff there are integers
$\ell , m , n$,
not all~0, and with $\hbox{gcd}(\ell,m) = 1$, such that:
$(-1)\cdot \ell^4 + a \ell^2m^2 + (b/(-1))\cdot m^4 = n^2$;
that is: $-\ell^4 + 14\ell^2m^2 - m^4 = n^2$.
Rewrite
as: $ - (  \ell^2 - 7 m^2 )^2 + 48 m^4 = n^2$.
Reducing modulo~3
gives: $ - ( \ell^2 - 7 m^2 )^2 \equiv n^2$ (modulo~3). If $n$ were
coprime to~$3$, then this would give: $(( \ell^2 - 7 m^2 )/n)^2 = -1$
in $\F_3$, contradicting the fact that~$-1$
is not a quadratic residue modulo~3. So,
$3 | n$ and so $3 | ( \ell^2 - 7 m^2 )$, also. Hence $9$ divides
$(  \ell^2 - 7 m^2 )^2$ and $n^2$ and so must divide $48 m^4$;
but $48$ is only divisible by $3$ (not by~$9$) so that $3$ must divide
$m^4$; hence $3$ divides $m$. Combining this with the fact (already
found) that
$3 | ( \ell^2 - 7 m^2 )$ gives that $3 | \ell$ also. We've shown
that $3$ divides all of $\ell,m,n$, a contradiction.
Hence $-1 \not\in \hbox{im} \hat q$.
\par  We conclude that $\hbox{im} \hat q  = \{ 1 \}$, and    
so $\c (\Q) / \hat\phi (\d (\Q))$ contains only {\bf o}.
[N.B. $(0,0)$ should not also be included as a separate member
of $\c (\Q) / \hat\phi (\d (\Q))$ even
though it is a rational point; $(0,0)$ maps to~1 under~$\hat q$, and so
$(0,0) \in \hat\phi (\d (\Q))$; that is $(0,0) = {\bf o}$ in
$\c (\Q) / \hat\phi (\d (\Q))$; the same comment applies to
the obvious point $(1,4)$; in general, for each distinct member $r$ of
$\hbox{im} \hat q$, you should only include exactly one point in $\c (\Q)$
which maps to~$r$]. 
\par Finally, since multiplication by 2 in $\c (\Q)$
is $\hat\phi \circ \phi$,
we have that $\c (\Q) / 2\c (\Q)$ is generated by: generators for
$\c (\Q) / \hat\phi (\d (\Q))$ [namely: {\bf o}] together with
the images under $\hat \phi$ of generators for $\d (\Q) / \phi (\c (\Q))$
[namely, $\hat\phi \bigl( (0,0) \bigr) = {\bf o}$
and $\hat\phi \bigl( (8,16) \bigr) = (1,-4)$]. Conclusion:
$\c (\Q ) / 2\c(\Q )$ is generated by $(1,-4)$,
and so is the group $C_2$.
Now $\c (\q)/2\c (\q)$ is isomorphic to $\ctq/2\ctq \times C_2^{rank}$, and
$\ctq /2\ctq$ is isomorphic to the $2$-torsion group of $\ctq$
which is $C_2$ (consisting only of {\bf o} and $(0,0)$),
so that
$\ctq/2\ctq$ is isomorphic to~$C_2$. Conclusion: rank~$=0$. [If this
seems surprising, then note that $(1,4),(1,-4)$ are points of
order~$4$ in $\c (\q)$].
%\par\noindent {\bf (d).} $Y^2 = X(X^2 + 2X + 9)$.  
%\par\noindent {\bf (e).} $Y^2 = X(X^2 + 9X - 1)$.    
%\par\noindent {\bf (f).} $Y^2 = X(X-12)(X-36)$. 
\medskip\noindent {\bf 5.}
We are given that $A,+$ is an Abelian group,
and that $h : A \rightarrow \R_{\ge 0}$ satisfies:
\par\noindent \ \ \ \ (I) There exists a constant~$C$, 
independent of~$P,Q$, such that
\par \ \ \ \ $ | h(P+Q) + h(P-Q) - 2 h(P) - 2 h(Q) | \le C $, 
for all $P,Q \in A$,
\par\noindent \ \ \ \ (II) For any~$B\in\R$, 
the set $\{P\in A:h(P)\le B\}$ is finite.
\par From~(I) we obtain: $h(P+Q) + h(P-Q) - 2 h(P) - 2 h(Q) \le C $
and so (since $h(P-Q) \ge 0$): $h(P+Q) \le h(P+Q) + h(P-Q)
\le 2 h(P) + 2 h(Q) + C \le 2 h(P) + C_1(Q)$, where
$C_1(Q) = 2 h(Q) + C$. Hence Property~(1) in the definition
of height function is satisfied.
\par Letting $Q=P$ in~(I), we obtain:
\par \ \ \ \ $ | h(2P) + h(e) - 4 h(P) | \le C, \ \ \ \ (*) $
\par\noindent where~$e$ denotes the identity element of the
group~$A$. This gives: $h(2P) + h(e) - 4 h(P) \ge -C$,
and so: $h(2P) \ge 4 h(P) - C_2$, where $C_2 = C + h(e)$.
Hence Property~(2) in the definition
of height function is satisfied. Furthermore, (II) is the
same as Property~(3) in the definition of height function.
Hence all~3 required properties are satisfied, giving
that~$h$ is a height function, as required.
\par Replacing $P,Q$ in~(I) with $2P,P$, respectively, gives:
\par \ \ \ \ $ | h(3P) - 2 h(2P) - h(P) | \le C $.
\par\noindent Multiplying $(*)$ by~$2$ gives:
\par \ \ \ \ $ | 2 h(2P) + 2 h(e) - 8 h(P) | \le 2C$.
\par\noindent These last two equations then give:
\par $ | h(3P) - 9 h(P) | 
  = | h(3P) - 2 h(2P) - h(P) + 2 h(2P) + 2 h(e) - 8 h(P) - 2 h(e) |$
\par\ \ \ \ \ $\le | h(3P) - 2 h(2P) - h(P) | 
+ | 2 h(2P) + 2 h(e) - 8 h(P) | + 2 | h(e) | \le C_3,$
\par\noindent where $C_3 = 3C + 2 | h(e) |$ (which is independent
of~$P$).
\medskip\noindent {\bf 6.}
In all of the following, each step multiplies
numbers $\leqslant N$ (followed by a possible reduction
modulo~$N$), and so we are guaranteed that
everything can be done on an $9$-digit
calculator, since $N^2$ has only 9~digits.
\par\noindent {\bf (a).} First compute (modulo $N=10481$):
$2^1 \equiv 2$, $2^2 \equiv 4$, $2^4 \equiv 16$, $2^8 \equiv 256$,
$2^{16} \equiv 2650$, $2^{32} \equiv 230$
(where each of these
was obtained be squaring the previous one, and reducing modulo~$N$). 
Now, we write $46$ in base~2: $46 = 2 + 4 + 8 + 32$ and
so $2^{46} \equiv 2^2 2^4 2^8 2^{32} \equiv 
4\cdot 16 \cdot 256 \cdot 230 \equiv 64\cdot 6475
\equiv 5641$ modulo~$N$, 
so that $2^{46} - 1 \equiv 5640$ modulo~$N$.
\par
Now, compute $\hbox{gcd}(5640, N)$ by Euclid's Algorithm:
$10481 = 1 \cdot 5640 + 4841$; $5640 = 1\cdot 4841 + 799$;
$4841 = 6\cdot 799 + 47$, $799 = 17\cdot 47 + 0$.
So, $47$ is a factor of $N$.
Compute $10481/47 = 223$, giving the factorisation
$N = 10481 = 47 \cdot 223$. %{\bf [7~marks]} 
\par\noindent {\bf (b).} The line tangent to~$\e$ at $P=(5,11)$
has slope $y'$ given by $2yy' = 3x^2 - 1$, with $x=5,y=11$;
that is, the slope is $74/22 = 37/11$. This tangent line also goes
through $(5,11)$ and so has equation: $Y = (37/11)X - 64/11$.
The $x$-coordinate of $2P$ is therefore $(37/11)^2 - (5+5) = 159/121$.
[It will turn out not to be necessary to evaluate this
mod~$N$, although if this is done using EA, then it is~7364],
and the $y$-coordinate is: $-((37/11)\cdot (159/121) - (64/11))
= 1861/1331$ [again, although unnecessary in this example,
this can be computed by EA to be: 6679 mod~N], 
so that $Q = 2P = (159/121 , 1861/1331)$. We now wish
to compute $3P = P + Q$, and so again the first step
is to find the line joining $P$ and $Q$. This has
slope given by $(1861/1331 - 11)/(159/121 - 5) = 6930/2453$,
and so we need to compute $6930/2453$
(modulo~$N=10481$), for which the first step is to find the
inverse of $2453$ (modulo~$N=10481$).
Using Euclid's Algorithm: $10481 = 4\cdot 2453 + 669$;
$2453 = 3 \cdot 669 + 446$; $669 = 1\cdot 446 + 223$;
$446 = 2\cdot 223 + 0$. So, we cannot
find the inverse of $2453$ (modulo~$N=10481$), and this
step has given us a factor~$223$ of~$N$. As before,
compute $10481/223 = 47$, giving the factorisation
$N = 10481 = 47 \cdot 223$. %{\bf [10~marks]}
\par\noindent {\bf (c).}  Since $N = 47 \cdot 223$, we have
$\phi (N) = 46 \cdot 222 = 10212$. Compute the gcd of $d=4085$ and
$\phi(N)$, we see:
$10212 = 2\cdot 4085 + 2042$; $4085 = 2\cdot 2042 + 1$,
so that $\hbox{gcd}(10212,4085) = 1$. Reversing the steps:
$1 = 4085 - 2\cdot 2042 = 4085 - 2\cdot (10212 - 2\cdot 4085)
= 5\cdot 4085 - 2\cdot 10212$.
Hence, $5$ is the inverse of
$4085$ modulo~$10212$.
The decoding operation is therefore $X \mapsto X^{5} \hbox{ mod }N$.
Computing $6012^{5} = 
(6012^2)^2 \cdot 6012
\equiv 
5656^2\cdot 6012
\equiv
2324\cdot 6012
\equiv
715$.
(modulo~$N = 10481$). Also:
$3236^{5} =
(3236^2)^2 \cdot 3236
\equiv
1177^2 \cdot 3236
\equiv
1837 \cdot 3236
\equiv
1805$
(modulo~$N = 10481$). The decoded
message is therefore: $0715,\, 1805$; that is: GORE.
%In all of the following, each step multiplies
%numbers $\leqslant N$ (followed by a possible reduction
%modulo~$N$), and so everything can be done on an $8$-digit
%calculator.
%\par
%Write $k$ in base~$2$ as: $k = 2^6 + 2^8 + 2^{10} + 2^{13} + 2^{14}$.
%Now compute $2^rP$ for $r$ from $0$ to $14$.
%The line tangent to~$\e$ at $P=(1,1)$
%has slope $y'$ given by $2yy' = 3x^2 + 1$, with $x=1,y=1$;
%that is, the slope is $4/2 = 2$. This tangent line also goes
%through $(1,1)$ and so has equation: $Y = 2X - 1$.
%The $x$-coordinate of $2P$ is therefore $2^2 - (1+1) = 2$,
%and the $y$-coordinate is: $-(2\cdot 2 - 1) = -3\equiv 8774$,
%so that $Q = 2P \equiv (2 , 8774)$ (modulo~$N=8777$). We now wish
%to double the point $Q = 2P$, and so again the first step
%is to find the line tangent to~$\e$ at $Q$. This has
%slope $y'$ given by $2\cdot 8774 \cdot y' = 3\cdot 2^2 + 1$,
%and so we need to compute $(3\cdot 2^2 + 1) / (2\cdot 8774)
%\equiv 13 / 8771$
%(modulo~$N=8777$), for which the first step is to find the
%inverse of $8771$ (modulo~$N$).
%Using Euclid's Algorithm: $8777 = 8771 + 6$;
%$8771 = 1461 \cdot 6 + 5$; $6 = 5 + 1$;
%$5 = 5 + 0$. So, reversing these steps: $1 = 6 - 5
%= 6 - (8771 - 1461\cdot 6) = 1462\cdot 6 - 8771 = 1462\cdot (8777 - 8771)
%- 8771 = -1463 \cdot 8771 + 1462 \cdot 8777$.
%So, the inverse of $8771$ is $-1463$ mod~$N$,
%and so the slope of our line is~$13\cdot(-1463) \equiv 7312$ (mod~$N$).
%Since $(2 , 8774)$ lies on the line, we deduce that the
%equation of the line is: $Y= 7312 X - 5850$. The $x$-coordinate
%of $2Q = 4P$ is then $7312^2 - 2 - 2 \equiv 4633$ (mod~$N$),
%with $y$-coordinate $-(7312\cdot 4633 - 5850) \equiv 8574$.
%Hence, $2^2P = 4P \equiv (4633, 8574)$ mod~$N$. Proceeding
%in the way, we then get: $2^3 P \equiv (1610,740)$,
%$2^4P \equiv (613, 4759)$,
%$2^5P \equiv (2,265)$,
%$2^6P \equiv (4633, 6229)$,
%$2^7P \equiv (1610, 7775)$,
%$2^8P \equiv (613, 6769)$,
%$2^9P\equiv (2,8774) = 2^1P$,
%$2^{10}P \equiv (4633, 8574) = 2^2P$,
%$2^{11}P \equiv (1610,740) = 2^3P$,
%$2^{12}P \equiv (613, 4759)= 2^4P$,
%$2^{13}P \equiv (2,265) = 2^5P$,
%$2^{14}P \equiv (4633, 6229)= 2^6P$ (mod~$N$).
%Now, $k\cdot P = 2^6P + 2^8P + 2^{10}P +2^{13}P + 2^{14}P$,
%and so a natural next computation is $2^6P + 2^8P$ (mod~$N$),
%which is $(4633, 6229) + (613, 6769)$ (mod~$N$). This requires
%finding the slope of the line through $(4633, 6229)$ and
%$(613, 6769)$, that is: $(6229 - 6769)/(4633 - 613)$,
%for which the first step is to find the inverse of
%$4633-613 = 4020$ mod~$N$. Applying Euclid's Algorithm:
%$8777 = 2\cdot 4020 + 737$; $4020 = 5\cdot 737 + 335$;
%$737 = 2\cdot 335 + 67$; $335 = 5\cdot 67 + 0$.
%Hence, we cannot
%find the inverse of $4020$ (modulo~$N=8777$), and this
%step has given us a factor~$67$ of~$N$.
%Compute $8777/67 = 131$, giving the factorisation
%$N = 8777 = 67 \cdot 131$.
%\par
%Pollard's $p-1$ method will not work if you only
%multiply together prime powers for primes less than~$11$.
%A natural attempt which will work is, for example,
%$\ell=2^3\cdot 3^2\cdot 5\cdot 7\cdot 11 = 27720$
%[indeed, $2\cdot 3\cdot 11$ would work, but there's
%no way of knowing that in advance!].
%First compute (modulo $N=8777$):
%$2^{2^0} \equiv 2$, $2^{2^1} \equiv 4$, $2^{2^2} \equiv 16$,
%$2^{2^3} \equiv 256$,
%$2^{2^4} \equiv 4097$, $2^{2^5} \equiv 3785$,
%$2^{2^6} \equiv 2161$,
%$2^{2^7} \equiv 557$,
%$2^{2^8} \equiv 3054$,
%$2^{2^9} \equiv 5742$,
%$2^{2^{10}} \equiv 4152$,
%$2^{2^{11}} \equiv 1076$,
%$2^{2^{12}} \equiv 7989$,
%$2^{2^{13}} \equiv 6554$,
%$2^{2^{14}} \equiv 278$
%(where each of these
%was obtained be squaring the previous one, and reducing modulo~$N$;
%we stop at $2^{14}$, which is the highest power of $2$ equal
%or less than~$\ell$). 
%Now, we write $\ell$ in base~2:
%$\ell = 2^3 + 2^6 + 2^{10} + 2^{11} + 2^{13}
%+ 2^{14}$ and
%so $2^\ell \equiv 2^{2^3} 2^{2^6} 2^{2^{10}} 2^{2^{11}} 2^{2^{13}} 2^{2^{14}}
%\equiv ( 256 \cdot 2161 )\cdot (4152 \cdot 1076 )\cdot (6554 \cdot 278)
%\equiv 265 \cdot 59 \cdot 5173
%\equiv 6858 \cdot 5173
%\equiv 8577$ modulo~$N$, 
%so that $2^\ell - 1 \equiv 8576$ modulo~$N$.
%\par
%Now, compute $\hbox{gcd}(8576, N)$ by Euclid's Algorithm:
%$8777 = 8576 + 201$; $8576 = 42\cdot 201 + 134$;
%$201 = 134 + 67$, $134 = 2\cdot 67 + 0$.
%So, $67$ is a factor of $N$.
%Compute $8777/67 = 131$, again giving the factorisation
%$N = 8777 = 67 \cdot 131$.
%\par Since $N = 67 \cdot 131$, we have
%$\phi (N) =66 \cdot 130 = 8580$. Compute the gcd of $d=4903$ and
%$\phi(N)$, we see: $8580 = 1\cdot 4903 + 3677$;
%$4903 = 1\cdot 3677 + 1226$;
%$3677 = 2\cdot 1226 + 1225$, $1226 = 1\cdot 1225 + 1$, 
%so that $\hbox{gcd}(8580,4903) = 1$. Reversing the steps:
%$1 = 1226 - 1225 = 1226 - (3677 - 2\cdot 1226)
%= 3\cdot 1226 - 3677 = 3\cdot (4903 - 3677) - 3677
%= 3\cdot 4903 - 4\cdot 3677 = 3\cdot 4903 - 4\cdot (8580 - 4903)
%= 7\cdot 4903 - 4\cdot 8580$.
%Hence, $7$ is the inverse of
%$4903$ modulo~$8580$.
%The decoding operation is therefore $X \mapsto X^{7} \hbox{ mod }N$.
%\par
%Computing $4195^7 = (4195^2)^2\cdot (4195^2 \cdot 4195)\equiv 
%140^2 \cdot (140 \cdot 4195) \equiv 2046 \cdot 8018 \equiv 615$
%(modulo~$N = 8777$). Similarly computing $7645^7, 1876^7, \ldots$
%(mod~$N$), we find that the complete decoded message is:
%\par
%$0615\vert 1520\vert 0201\vert 1212\vert 0009\vert 2001\vert 1209\vert 0100$,
%%\par\noindent
%\ \ \ \ \ which reads: Football Italia.
% Possible qn 6 for the future: y^2 = x*(x^2 + x + 7)?
\medskip\noindent
{\bf 7.} First let us suppose that our elliptic curve 
$Y^2 = X^3 + A X + B$
has a point $(x_0,y_0)$ of order~$4$.
Performing the birational transformation $(X,Y) \mapsto (X-x_0,Y-y_0)$
[which corresponds to replacing the variables $X,Y$ by
$X + x_0, Y + y_0$] maps $(x_0,y_0)$ to $(0,0)$ on
the birationally equivalent curve if the form:
$Y^2 + 2 y_0 Y + y_0^2 =$ (monic cubic in~$X$), and so is of the form:
$Y^2 + 2 y_0 Y = X^3 + f_2 X^2 + f_1 X$ [after absorbing $-y_0^2$
into the cubic in~$X$]. The fact that there is no constant term~$f_0$
is a consequence of the fact that our new curve contains
the point~$(0,0)$. We perform the further birational
transformation $(X,Y) \mapsto (X,Y - f_1 X/(2 y_0))$
[which corresponds to replacing the variable $Y$ by $Y + f_1 X/(2 y_0)$]
which maps to the new birationally equivalent
curve $Y^2 + b XY + a Y = X^3 + c X^2$, where
$b = f_1/y_0, a = 2 y_0, c = f_2 - (f_1/(2 y_0))^2$].
Note that, for any $r$, the birational transformation
$(X,Y) \mapsto ( r^2 X, r^3 Y )$
[which corresponds to replacing the variables $X,Y$
by $X/r^2, Y/r^3$] maps to the birationally equivalent
curve: $Y^2 + b r XY + a r^3 Y = X^3 + c r^2 X^2$. 
Choosing $r = c/a$ forces the coefficients of
$Y$ and $X^2$ both to be $c^3/a^2$. So, let $r = c/a,
v = c^3 / a^2$ and $w = br = b^2/c$. 
Note that $y_0 \not= 0$, since $(x_0,y_0)$ is not of order~2,
and so $a = 2 y_0 \not= 0$. Also, $c\not= 0$ (since
if $c=0$ then $Y=0$ would meet the curve $Y^2 + b XY + a Y = X^3 + c X^2$
3 times at~$(0,0)$ making $(0,0)$ of order~3, and so $(x_0,y_0)$
of order~3 on the original curve, a contradiction).
Hence, it was legitimate to have divided by~$a$ and~$c$.
%Note that $a=0 \iff (x_0,y_0)$ is of order~2, and $c=0 \iff (x_0,y_0)$
%is of order~3 on the original curve.
Our curve is now
of the form:
$$ \e : Y^2 + w XY + v Y = X^3 + v X^2,$$
and $(0,0)$ is our point of order~$4$. So far, we have only
used the fact that our original curve contained a rational
point $(x_0,y_0)$ [not of order~2 or~3], 
which we have mapped to $(0,0)$. We now
use the fact that $(0,0)$ is of order~$4$ on $\e$
to see what condition this gives on $v,w$.
First perform the addition $(0,0) + (0,0)$.
The line tangent to $\e$ at $(0,0)$ is $Y=0$.
Substituting this into $\e$ gives: $X^3 + v X^2$, which
has roots $0,0,-v$, and so $(0,0),(0,0),(-v,0)$ are the
three points of intersection of $Y=0$ and $\e$,
so that $(0,0) + (0,0) + (-v,0) = {\bf o}$,
giving: $2(0,0) = -(-v,0)$.
Now, since {\bf o} is the point at infinity,
the negative of $(-v,0)$ is the other point on~$\e$
with $X$-coordinate~$-v$. Substituting $X=-v$ into~$\e$
gives: $Y^2 - v w Y + v Y = 0$
and so: $Y ( Y - v(w-1) )$, which has roots $0, v(w-1)$.
So, the negative of $(-v,w)$ is $(-v,v(w-1))$,
giving: $2(0,0) = (-v,v(w-1))$. Now, $(0,0)$ is of order~$4$
iff $2(0,0)$ is of order~$2$ iff $2(0,0)$ equals its own
inverse (since it is not the identity).
But $(-v,v(w-1))$ is the inverse of $(-v,0)$
and so equals its own inverse iff $v(w-1) = 0$.
Now, we cannot have $v = 0$, since then $\e$ would
be singular and so would not be an elliptic curve.
So, $(0,0)$ having order~$4$ on~$\e$ is equivalent
to $w = 1$. Substututing $w=1$ into $\e$ gives
the required form.
\bigskip
\bigskip
\hrule
%\centerline{\bf A Few Pieces of Computational Advice}
% %\par
% %I have the impression that some of you are making
% %cryptography questions unduly time-consuming, due to
% %very slow calculator methods for performing some of the
% %basic steps. 
%\medskip
%\sevrm
%\baselineskip = 3.4 true mm
%If you want to perform something like: 2046 $\cdot$ 8018 mod~8777
%on a pocket calculator, then the fast way is as follows. 
%First, 2046 $\cdot$ 8018 = 16404828. Now divide by 8777
%to get the decimal~1869.070069; now subtract off the integer
%part 1869 to get .070069; now multiply by 8777 to
%get the decimal 614.99561; this is guaranteed to be almost
%exactly an integer, and the nearest integer (namely: 615) will 
%be 16404828 mod~8777. If you want to check it 
%be 100\% sure, then you can verify it by:
%(2046 $\cdot$ 8018 - 615)/8777 and seeing that the result is
%an exact integer. [N.B. This is much faster than, for example,
%repeatedly subtracting 8777 from 16404828 until getting
%a number less than 8777; in this case that approach would
%require 1869 subtractions!].
%This same idea can also make quicker steps
%of Euclid's Algorithm. 
%\par
%If you want to write a number, such as k=25920,
%in base~2, then a fast way is as follows. Type 25920
%into the calculator. At each step, we reduce the size of our
%current number either by the step [divide-by-2]
%(if our current number is even) or  
%by the step [subtract-1-and-then-divide-by-2]
%(if our current number is odd). This
%allows us to write down the base~2 digits from right to left, where
%we write down a~0 if we've done the first of the above,
%and a~1 if we've done the second. For example,
%with k=25920, we first perform [divide-by-2] and write
%down~0 as our rightmost digit (and the calculator display
%now reads 12960). After doing the [divide-by-2] 5 more
%times, we have now written a total of 000000 as the
%six rightmost digits, and the calculator reads: 405.
%Now, perform [subtract-1-and-then-divide-by-2], and write
%down a~1 on the left, so that your piece of paper
%currently reads: 1000000, and your calculator
%display reads: 202. Now perform [divide-by-2], so that
%you piece of paper reads: 01000000 and your calculator
%reads: 101. Continuing until your calculator reads 0
%will make your final piece of paper read:
%110010101000000; that is:
%k = $\hbox{2}^{\hbox{\fiverm 6}}$ +
%$\hbox{2}^{\hbox{\fiverm 8}}$ +
%$\hbox{2}^{\hbox{\fiverm 10}}$ +
%$\hbox{2}^{\hbox{\fiverm 13}}$ +
%$\hbox{2}^{\hbox{\fiverm 14}}$ [take care to remember
%that the last digit in 110010101000000 is the coefficient
%of~$\hbox{2}^{\hbox{\fiverm 0}}$.]
\vfil\eject\end