% MARKS ALLOCATED AS FOLLOWS:
% 1: 10. 2: 20. 3: 20. 4: 20. 5: 10. 6: 20. Total: 100.
% Add question about G_{2-torsion} and G/2G for G given as
% product of various cyclic groups.
% Also, perhaps a check that $C_2 \times C_3$ is isomorphic to $C_6$, etc.
% Also, cut each of the 4 sheets in half to make 8 smaller sheets,
% and add marking scheme to solns!
\input amssym.def 
\input amssym.tex
%\def\Bbb{\bf}
\def\notdiv{{\not\hskip-.5pt |\ }}
\def\ge{\geqslant}
\def\le{\leqslant}
\def\ctq{{\cal C}_{\lower 1pt\hbox{\eightsl tors}}({\Bbb Q})}
\nopagenumbers
\magnification=\magstep1
%\hoffset=1truecm
%\voffset=2truecm
\baselineskip = 5.2 true mm
\font\eightsl=cmsl8
\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\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\bbQ{\Bbb Q}
\def\bbZ{\Bbb Z}
\def\bbR{\Bbb R}
\def\bbC{\Bbb C}
%
\chaptitle
\noindent
\centerline{Elliptic Curves. Sheet 0.}
\rm
\bigskip
{\it This sheet is not intended to be handed in. It is merely
for you to use (as you please) to reinforce the preliminary
reading in Section~0 ``Background Material in Algebra,
Number Theory and Geometry''.}
\bigskip
\bigskip
\noindent {\bf 1.} Determine whether the following are groups.
\par\noindent {\bf (a).} The set of all $2\times 2$ matrices
under matrix multiplication. 
\smallskip
\par\noindent {\bf (b).} The set of all $2\times 2$ matrices
under matrix addition. 
\medskip
\noindent {\bf 2.} For each of the following, decide whether
$\phi$ is a homomorphism. When $\phi$ is a homomorphism,
decide whether~$\phi$ is injective, surjective, bijective, and
find the kernel of~$\phi$.
\par\noindent {\bf (a).} $\phi : \bbZ , + \rightarrow \qs , \times
: x \mapsto x^2+1$.
\smallskip
\par\noindent {\bf (b).} $\phi : \bbQ , + \rightarrow \bbR , +
: w \mapsto \sqrt{2}\, w$.
\smallskip
\par\noindent {\bf (c).} $\phi : \bbZ  , +  \rightarrow
\bbZ / 3\bbZ , + : x \mapsto 2x$.
\medskip
\noindent {\bf 3.} 
\par\noindent {\bf (a).} In $\qmods$, decide whether
the following are
true or false: $3=1/27$, $-4=4$, $3=5/6$.
\smallskip
\par\noindent {\bf (b).} In $\qmods$, write each of the following as
a square free integer: $-2/27$, $16$, $12$, $1/3$.
\smallskip
\par\noindent {\bf (c).} Perform each of the following in $\qmods$,
writing your answer as a square free integer:
$6\times 10$, $10 / 21$, $15^{101}$, $3^{-1}$.
\smallskip
\par\noindent {\bf (d).} How many elements are in each of
the groups: $\qmods$,
${\Bbb R}^*/({\Bbb R}^*)^2$,
${\Bbb C}^*/({\Bbb C}^*)^2$?
\medskip
\noindent {\bf 4.}
\par\noindent {\bf (a).} Find all singular points on the curve
$$ \c : f(X,Y) = X^4 + Y^3 - 3 X^2 Y = 0. $$
\noindent Find all tangents to $\c$ at the point $(0,0)$.
\smallskip
\par\noindent {\bf (b).} Find all singular points on the curve
$$ \c : f(X,Y) = Y^2 - X(X^2-1)^2 = 0.$$
\noindent Find all tangents to $\c$ at the points $(0,0)$ and $(1,0)$.
\medskip \noindent {\bf 5.} Show that $\c : Y^2 = X^3 + AX + B$ is smooth
if $4A^3 + 27B^2 \not= 0$.
\medskip\noindent {\bf 6.} For each of the following curves,
find the irreducible components over~$\bbQ$ and the irreducible
components over~$\bbC$.
\par\noindent {\bf (a).} $\c : Y^2 = X^5$.
\smallskip
\par\noindent {\bf (b).} $\c : Y^3 = X^3$.
\smallskip
\par\noindent {\bf (c).} $\c : Y^2 = X^3 + 1$.
\medskip\noindent{\bf 7.}
\par\noindent {\bf (a).} Find a birational transformation over~$\bbQ$
between the curves $2X^2 - Y^2 = 1$ and $X^2 + Y^2 - 6XY = 1$.
\smallskip
\par\noindent {\bf (b).} Find a birational transformation over~$\bbQ$
between the curves $Y^2=(X+2)^6(X^3+1)$ and $Y^2 = X^3 + 1$.
\smallskip
\par\noindent {\bf (c).} Find a birational transformation over~$\bbC$
between the curves~$Y^2=2X^2$ and~$Y^2=X^2$. Is there a birational
transformation over~$\bbQ$?
\medskip
\noindent {\bf 8.}
\par\noindent {\bf (a).} Find the discriminant of~$X^4-2$.
\smallskip
\par\noindent {\bf (b).} Find the resultant of $X^3 - a$ and $X^2 - b$,
where $a,b$ are constants.
\medskip\noindent {\bf 9.} Find all intersection points
(with multiplicities) over~$\Bbb C$ of the curves:
$X^3 + Y^3 = Z^3$ and $X^2 + Y^2 = Z^2$.
\medskip
\noindent {\bf 10.}
\par\noindent {\bf (a).}
Decide whether each of 
$2,3,5,10,15$
are quadratic residues modulo~1009 (if you use quadratic reciprocity,
this should not involve any lengthy computations).
\smallskip
\par\noindent {\bf (b).} Describe all primes~$p$ such that $3$
is a quadratic residue modulo~$p$.   
Describe all primes~$p$ such that $5$
is a quadratic residue modulo~$p$. 
Describe all primes~$p$ such that $10$
is a quadratic residue modulo~$p$. 
\medskip
\noindent {\bf 11.} Are there integers $a,b,c$, not all~$0$,
such that $2a^2 + 5b^2 = c^2$?
\medskip
\noindent {\bf 12.} For any $n\in{\Bbb N}$ define, as usual, Euler's
$\phi$-function by: 
$$ \phi(n) = \# \{ x :
1 \leqslant x \leqslant n \hbox{ and gcd} (x,n) = 1 \}.
$$
For any prime~$p$, what is $\phi(p^r)$?
For any distinct primes $p_1,p_2$, what is $\phi(p_1 p_2)$?
\par
For each of the following examples of
the type $a^b \ (\hbox{mod }n)$, reduce $a^b \ (\hbox{mod }n)$ to a member
of $\{ 0, \ldots , n-1 \}$.
\par\noindent
$2^{12} \ (\hbox{mod }13)$,
$3^{12} \ (\hbox{mod }13)$,
$3^{24} \ (\hbox{mod }13)$,
$3^{12000} \ (\hbox{mod }13)$,
$3^{12002} \ (\hbox{mod }13)$,
\hfill\par\noindent
$4^{24} \ (\hbox{mod }35)$,
$4^{48} \ (\hbox{mod }35)$,
%$4^{48000} \ (\hbox{mod }35)$,
$4^{48000001} \ (\hbox{mod }35)$,
\hfill\par\noindent
$7^{24} \ (\hbox{mod }35)$,
$7^{48} \ (\hbox{mod }35)$,
%$7^{48000} \ (\hbox{mod }35)$,
$7^{48000001} \ (\hbox{mod }35)$.
\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\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\notdiv{{\not\hskip-.5pt |\ }}
%
\chaptitle
\noindent
\centerline{Elliptic Curves. Sheet 1. To be handed in during 2nd Week.}
\rm
\bigskip
\noindent
\noindent {\bf 1.} For each of the following elliptic curves,
find all the points (including, as always,
the point at infinity) over ~$\bbF_5$.
Draw a complete
group table in each case and describe each group as a product of
cyclic groups.
\par\noindent
{\bf (a).} $Y^2 = X^3 + 2 X$.
\smallskip
\par\noindent
{\bf (b).} $Y^2 = X^3 + 1$.
\medskip
\noindent {\bf 2.} Show that the point~$(2,4)$ is of order~4
on $Y^2 = X^3 + 4X$, defined over~$\bbQ$.
\medskip
\par\noindent {\bf 3.}
\par\noindent {\bf (a).} Let $m\in \bbZ$ be odd or $f_m\in \qss$ (or both).
Show that the curve
\par
\centerline{$Y^2 = f_mX^m + f_{m-1}X^{m-1} + \ldots + f_0$, where
all $f_i\in \bbQ$ and $f_m\not= 0$,}
\par\noindent
can be birationally transformed over~$\bbQ$ to 
a curve of the form
\par
\centerline{$Y^2 = X^m + g_{m-1}X^{m-1} + \ldots+ g_0$, with
all $g_i\in \bbZ$.}
\smallskip
\par\noindent {\bf (b).} Birationally
transform over $\bbQ$ the curve $Y^2 = {1\over 5}X^3 + 3 X^2
+ 1$ to a curve of the form~$Y^2 = X^3 + AX + B$, where $A,B\in \bbZ$.
\medskip
\par\noindent {\bf 4.}
\par\noindent {\bf (a).} Let $p \equiv 2$~(mod~$3$) be prime
and let $A \in \bbF_p^*$.
Show that the number of points (including the point
at infinity) on the curve $Y^2 = X^3 + A$ over $\bbF_p$
is exactly $p+1$.
\smallskip
\par\noindent {\bf (b).} Let $p \equiv 3$~(mod~$4$) be prime
and let $B \in \bbF_p^*$.
Show that the number of points (including the point
at infinity) on the curve $Y^2 = X(X^2 + B)$ over $\bbF_p$
is exactly $p+1$.
\bigskip
\hrule
\medskip
{\it The following question is compulsory for students taking
the MSc in MFoCS (Mathematics and the Foundations of Computer
Science). For everyone else, it is optional.}
\medskip
\par\noindent {\bf 5.}
\par\noindent {\bf (a).} Let $\c : Y^2 = Q(X) = X^4 + f_3X^3
+ f_2X^2 + f_1X + f_0$, where all $f_i\in \bbQ$. Show that
the curve $\c$ can be birationally transformed over $\bbQ$
to a curve of the form $Y^2 = X^3 + AX + B$, where $A,B\in \bbZ$.
[Begin by finding $G(X)$ and $H(X)$ such that $Q(X) = G(X)^2 + H(X)$,
with $G$ quadratic and $H$ linear, and let $T=Y+G(X)$,
$S=X\bigl(Y+G(X)\bigr)$.]
\smallskip
\par\noindent {\bf (b).} Birationally
transform over $\bbQ$ the curve $\c_1: Y^2 = 2X^4 + 9$
to the standard form $Y^2 = X^3 + AX + B$,
with $A,B\in \bbZ$. Show that $\c_2: Y^2 = 2X^4 + 7$ can
also be birationally
transformed over $\bbQ$ to the same form.
[Hint: In each case, first transform to the
form $Y^2 = Q(X)$ of part (a).]
\smallskip
\par\noindent {\bf (c).} Birationally transform over $\bbQ (i)$ the
curve $Y^2 = -X^4 - 1$ to the standard form $Y^2 = X^3 + AX + B$,
with $A,B\in \bbZ$. Is this possible over $\bbR$? Is this
possible over $\bbQ (\sqrt{-2})$?
\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\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. Sheet 2. To be handed in during 3rd Week.}
\rm
\bigskip
\noindent {\bf 1.}
\par\noindent {\bf (a).} Show that the point $(2,0)$ is of
order 2 on $Y^2 = (X-2)(X^2 + X + 1)$.
\par\noindent {\bf (b).} Find all $\bbQ$-rational points of order~2
and all $\bbC$-rational points of order~2
on each of the following elliptic curves: $Y^2 = X(X^2-3)$,
$Y^2 = X^3 - 7$ and $Y^2 = X(X-1)(X-7)$. In each case, find the
group structure (expressed as a product of cyclic groups)
of the $\bbQ$-rational 2-torsion group (that is, the group
of all $\bbQ$-rational points~$P$ such that $2P = {\bf o}$).
\medskip
\par\noindent {\bf 2.} Show that the point $(0,2)$ is of
order 3 on $Y^2 = X^3 + 4$. 
\medskip
\noindent
{\bf 3.}
\par\noindent {\bf (a).} Let $Y^2 = (X-\alpha)(X^2 + aX + b)$
be an elliptic curve with $a,b,\alpha\in K$ (characteristic $\not= 2$),
and  ${\bf o} =$ point at infinity, as usual. Show that $(\alpha , 0)$
is a point of order~2. Let $x',y'$ be defined by: $(x',y')
= (x,y) + (\alpha , 0)$, and define $T: K\rightarrow K : x\mapsto x'$.
Find $t_{11},t_{12},t_{21},t_{22}$ in terms of $a,b,\alpha$ such that:
$x' = \mu(x) = (t_{11} x + t_{12})/(t_{21} x + t_{22})$.
Check that $\mu^2 : x\mapsto x$.
\smallskip
\par\noindent {\bf (b).} Consider~$Y^2 = (X-\alpha_1)(X-\alpha_2)
(X-\alpha_3)$, with $\alpha_1,\alpha_2,\alpha_3$ distinct,
and let $T_1,T_2,T_3$ be as in (a), but with $\alpha$ replaced
by $\alpha_1,\alpha_2,\alpha_3$, respectively. 
Express each $T_i$ in terms of $x,\alpha_1,\alpha_2,\alpha_3$.
Show, directly from expressions, that $T_1,T_2,T_3$
commute (i.e.\ $T_1 T_2 = T_2 T_1$, $T_1 T_2 = T_2 T_1$ and
$T_2 T_3 = T_3 T_2$), and that $T_1 T_2 T_3 : x\mapsto x$.
Find the fixed points of $T_1$
and show that they are permuted by $T_2$.
\medskip
\noindent {\bf 4.}
Let $K$ be any field with $\hbox{Char }K \not= 2,3$,
and let ${\cal E}: F(X_0,X_1,X_2)
= X_1^2 X_2 - (X_0^3 + A X_0 X_2^2 + B X_2^3)$, with $A,B \in K$,
be an elliptic curve (N.B. This is just the standard projective form,
but with $X,Y,Z$ replaced by $X_0,X_1,X_2$). Let~$P$ be a
point on~$\cal E$.
\smallskip
\par\noindent {\bf (a).} Show that $3P = {\bf o}$ iff.\ the tangent line
to $\cal E$ at~$P$ intersects $\cal E$ only at~$P$.
\smallskip
\par\noindent {\bf (b).} Show that $3P={\bf o}$ iff.\ the $3\times 3$
matrix
$\bigl( \partial^2 F / \partial X_i \partial X_j (P) \bigr)$
has determinant~$0$. [This matrix is called the Hessian matrix].
\smallskip
\par\noindent {\bf (c).} Show that there are exactly nine
$3$-torsion points over $\overline K$, the algebraic
closure of~$K$.
\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. Sheet 3. To be handed in during 4th Week.}
\rm
\bigskip
\noindent
{\bf 1.} Let $K$ be a field with
non-Archimedean valuation $|\ |$.
\smallskip
\par\noindent {\bf (a).} For any $x,y\in K$ show that, if $|x| \not= |y|$
then $|x \pm y | = \hbox{max}( |x|, |y| )$.
\par\noindent {\bf (b).}
If $x_1, \ldots , x_n \in K$ and
if there exists $\ell$ such that
$|x_\ell| > |x_i|$ for all $i\not= \ell$,
then show that $|x_1 + \ldots + x_n| = |x_\ell|$.
\smallskip
\par\noindent {\bf (c).} Suppose that $s_n \rightarrow s$
in $K,|\ |$. Show that $|s_n| \rightarrow |s|$
in $\bbR, |\ |_\infty$. 
%Suppose
%that $s_n \rightarrow s \not= 0$ in~$\bbQ_p$; show
%that there exists $N$ such that, for all $n > N$, $|s_n|_p = |s|_p$.
When $s \not= 0$, show
that there exists $N$ such that, for all $n > N$, $|s_n| = |s|$.
\smallskip
\par\noindent {\bf (d).}
Show that if $\sum_{n=1}^\infty x_n$
converges to $x \in K, |\ |$, then
the set $\{ | x_i | : i \geqslant 1\} \subset \bbR$ 
has a maximum element, and $|x| \leqslant \hbox{max}_i |x_i|$.
Show that, if there exists $\ell$ such that
$|x_\ell| > |x_i|$ for all $i\not= \ell$,
then $\sum_{n=1}^\infty x_n$ does not converge to~$0$.
\medskip
\noindent {\bf 2.} 
\par\noindent {\bf (a).} Find: $| 3/50 |_5$, $| 3/50 |_3$, $|3/50 |_7$,
$d_5(2/3 , 1/5)$, $d_7(2/3 , 1/5)$, $d_{11}(2/3, 1/5)$.
\smallskip
\par\noindent {\bf (b).} Describe $| 3/7 |_p$ for all~$p$. What
is the product $\prod | 3/7 |_i$, taken over $i=p$, for all primes $p$,
and $i=\infty$? Given any $x\in\Q$, what is $\prod | x |_i$?
\medskip
\noindent {\bf 3.} Which of the following are convergent in $\Q_5$?
\par\ \ \ \ \ \ \
$ a_n = 1/5^n,\ \ a_n = n,\ \ a_n = n!,\ \ a_n = 3 + 10^n.$
\medskip
\noindent {\bf 4.} Which of the following are convergent in $\Q_5$?
$\sum 10^n , \ \ \sum 7^n.$
\medskip
\noindent {\bf 5.} For each $p,m,r$, either find an $x\in \Z$ such that
$|x-r|_p \leqslant p^{-m}$ or show that no such~$x$ exists.
\smallskip
\par\noindent
{\bf (a).} $p=257, r=1/ 2, m=1$.\ \
{\bf (b).} $p=3, r=7/ 9, m=7$.\ \
{\bf (c).} $p=5, r=1/ 4, m=4$.
\medskip
\noindent {\bf 6.} For each $p,m,r$, either find an $x\in \Z$ such that
$|x^2-r|_p \leqslant p^{-m}$ or show that no such~$x$ exists. 
\smallskip
\par\noindent
{\bf (a).} $p=5, r=-1, m=4$.\ \
{\bf (b).} $p=3, r=7/8, m=7$.\ \
{\bf (c).} $p=5, r=5/4, m=4$.\ \
\medskip 
\noindent {\bf 7.} Find the $7$-adic expansion of each of: $200$ and $3/14$.
\medskip 
\noindent {\bf 8.} What member of~$\Q$ is expressed by each of
the following two $5$-adic expansions? $23,4$ and $2,\overline{34}$.
\medskip\noindent {\bf 9.} Let $x\in \Q$. Show that
$x\in \Z \iff \bigl( x\in \Z_p \hbox{ for all }p\bigr)$. 
\bigskip
\hrule
\medskip
{\it The following question is compulsory for students taking
the MSc in MFoCS (Mathematics and the Foundations of Computer
Science). For everyone else, it is optional.}
\medskip
\noindent {\bf 10.}
Show that $|n!|_p = p^{-M}$ where $M = \sum_{i=1}^\infty 
\bigl[ {n\over p^i} \bigr]$ (where $[ x ]$ denotes the
greatest integer $\leqslant x$).
Let $K$ be a field containing $\Q_p$,
and let $|\ |$ be a non-Archimedean valuation on~$K$ which extends
$|\ |_p$. For any $x\in K$, show that 
$\hbox{exp}_p(x) = \sum_{n=0}^\infty {x^n\over n!}$
converges if and only if
$|x| < p^{-{1\over p-1}}$. 
When $K = \Q_p$ ($p\not= 2$), show that $\hbox{exp}_p(x)$ converges
if any only if $|x|_p < 1$. When $K = \Q_2$, show that
$\hbox{exp}_2(x)$ converges
if any only if $|x|_2 < {1\over 2}$.
\vfil \eject %\end
% MARKS ALLOCATED AS FOLLOWS:
% 1: 10. 2: 10. 3: 10. 4: 10. 5: 10. 6: 20. 7: 30. Total: 100.
% In more detail:
% 1: 10. 2: 10. 3: 10. 4: 10. 5: 10. 6: each part 5. 7: each part 5.
\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\c{{\cal C}}
\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. Sheet 4. To be handed in during 5th Week.}
\rm
\bigskip
\noindent {\bf 1.} Decide whether there exists $x\in \Q_p$ such that
$x^2 = -28$ for each of: $p=2,3,5,7,11$.
\medskip\noindent {\bf 2.} Show that, for all~$p$, there
exist~$x,y\in \Z_p$ such that
$y^2 = x^3 + x - 3$.
\medskip\noindent {\bf 3.} Show that $(X^2 - 2)(X^2-17)(X^2-34)$
has a root in $\R$ and in every $\Q_p$, but not in $\Q$.  
\medskip\noindent {\bf 4.} Is~$4$ a cube in~$\Q_3$? Is~$28$ a cube
in~$\Q_3$? Is~$13$ a cube in~$\Q_7$?
\medskip\noindent {\bf 5.} Show that the curve $2 Y^2 = X^4 - 17$
has points in $\R$ and every $\Q_p$, but not in~$\Q$. [Hint: First
show that, if there were points in~$\Q$, then there would exist
$r,s,t\in \Z$ with $\hbox{gcd}(r,t) = 1$ such
that $2 s^2 = t^4 - 17 r^4$, and then show that any prime dividing
$s$ is a quadratic residue modulo~$17$].
\medskip\noindent {\bf 6.} Let $p\equiv 2$ mod~$3$. For any
$a\in \Z$ such that $p\notdiv a$, show that there exists
$x\in \Z_p$ with $x^3 = a$.
\medskip\noindent {\bf 7.} Let $K$ be any field with a
non-Archimedean valuation $|\ |$, and
let $ R = \{ x\in K : |x| \leqslant 1\}$.
Let $f(X) \in R[x]$ have discriminant~$D$, and let
$a_0 \in R$ satisfy $|f(a_0)| < |D|^2$. Show that $f(X)$
has a root $a\in R$.
\bigskip
\hrule
\medskip
{\it The following question is compulsory for students taking
the MSc in MFoCS (Mathematics and the Foundations of Computer
Science). For everyone else, it is optional.}
\medskip
\medskip\noindent {\bf 8.} Show that $f(X) = 5 X^3 - 7 X^2 + 3 X + 6$
has a root $\alpha \in \Z_7$ with $|\alpha - 1|_7 < 1$.
Find $a\in\Z$ such that $|\alpha - a|_7 \leqslant 7^{-4}$.
\vfil\eject
\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\c{{\cal C}}
\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. Sheet 5. To be handed in during 6th Week.}
\rm
\medskip\noindent {\bf 1.} Prove that, if $d\in\Z_p$
is non-square, then 
$$ | a + b\sqrt{d} |_p = | a^2 - b^2 d |_p^{1/2}, 
\hbox{ for any } a,b \in \Q_p, $$
defines a non-Archimedean valuation on $\Q_p(\sqrt{d})$ which extends
the usual $|\ |_p$ on $\Q_p$. 
\smallskip\par\noindent [Hint: First show that, for
any $\alpha \in \Q_p(\sqrt{d})$, $|\alpha|_p \leqslant 1
\Rightarrow |\alpha + 1 |_p \leqslant 1$].
\medskip\noindent {\bf 2.} Let $\e : Y^2 = X^3 + 17$, defined
over~$\Q$, and $\widetilde \e : Y^2 = X^3 + 2$, defined over
$\F_5$. What does $(-64/25 , 59/125) \in \e (\Q)$ map to
under the reduction map modulo~$5$?
\medskip\noindent {\bf 3.} Let $\e : Y^2  = X^3 + p$, defined
over~$\Q_p$, and $\widetilde \e : Y^2 = X^3$, defined over~$\F_p$,
where~$p\not= 2$. Show that~$(0,0)$ on~$\widetilde \e$ does not
lift to a point in~$\e (\Q_p)$.
\medskip\noindent {\bf 4.} Give examples of elliptic curves
defined over~$\Z_p$ ($p\not= 2$) such that $\widetilde \e$,
defined over~$\F_p$, has:
\par \noindent {\bf (a).} A cusp which lifts to a point
in~$\e (\Q_p)$.
\par \noindent {\bf (b).} A cusp which does not lift to a point
in~$\e (\Q_p)$.
\par \noindent {\bf (c).} A node which lifts to a point
in~$\e (\Q_p)$.
\par \noindent {\bf (d).} A node which does not lift to a point
in~$\e (\Q_p)$.
\medskip\noindent {\bf 5.} A {\it non-commutative formal group}
over a ring~$R$ is a power series $F(X,Y) \in R[[X,Y]]$
which satisfies:
\par $F(X,Y) = X + Y +$ terms of degree~$\geqslant 2$,
\par and 
\par $F(X, F(Y,Z)) = F(F(X,Y),Z)$ [associativity],
\par\noindent but not $F(X,Y) = F(Y,X)$ [commutativity].
Let $R = \F_p[t]/I$, where $I = t^2 \F_p[t]$.
Find a non-commutative formal group over~$R$.
%of the form $F(X,Y) = X + Y + c X^i Y^j$, where $c$ is a constant.
\bigskip
\hrule
\medskip
{\it The following question is compulsory for students taking
the MSc in MFoCS (Mathematics and the Foundations of Computer
Science). For everyone else, it is optional.}
\medskip
\medskip\noindent {\bf 6.} Let $\e : Y^2 = X^3 + AX$, where
$A \in \Z$ and $A \not= 0$. Let $F(X,Y)$ be the formal group
associated to~$\e$ [as in lectures] and let $F(X,Y) = \sum F_n(X,Y)$,
where each $F_n(X,Y)$ is homogeneous of degree~$n$.
Show that $F_n(X,Y) = 0$ unless $n\equiv 1$~(mod~$4$).
What is the similar result when the elliptic curve
is of the form $\e : Y^2 = X^3 + B$?
\vfil\eject
\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\sevrm=cmr7
\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\c{{\cal C}}
\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. Sheet 6. To be handed in during 7th Week.}
\rm
\bigskip
\medskip\noindent {\bf 1.} Find the torsion group over~$\Q$
for each of:
\par\noindent {\bf (a).} $Y^2 = X^3 + 1$.
\par\noindent {\bf (b).} $Y^2 = X^3 - 219X + 1654$.
%\par\noindent {\bf (c).} $Y^2 = X(X+1)(X+4)$.
\par\noindent {\bf (c).} $Y^2 = X(X+81)(X+256)$.
\par\noindent {\bf (d).} $Y^2 = X(X-1)(X-2)$.
\par\noindent {\bf (e).} $Y^2 = X^3 + 1/3^6$.
\par\noindent {\bf (f).} $Y^2 + Y = X^3 - X + 13$.
%\par\noindent {\bf (g).} $Y^2 = X^3 - X^2 + 1/4$.
\par\noindent Note: (b) and (c) require significant computation
(you should do an initial search for points with $x$-coordinate
in the range $|x| \leqslant 30$, with $x\in \Z$)
and are of course much more time consuming than anything which
would be asked in a timed exam. They are mainly intended to demonstrate
that interesting torsion groups can occur.
\medskip\noindent {\bf 2.} Let, as usual, $\c : Y^2 = X(X^2 + aX + b)$
and $\d : Y^2 = X(X^2 + a_1X + b_1)$, where $a,b\in\Z$, $a_1 = -2a,
b_1 = a^2 - 4b$ and $b(a^2-4b)\not= 0$. Show that the odd torsion
subgroups of $\c(\Q)$ and $\d(\Q)$ are isomorphic.
\medskip\noindent {\bf 3.} Let $\c$ and $\d$ be as in question~2.
Let the homomorphism~$\phi, \hat\phi$ be defined as usual by 
$$\phi : \c (\Q ) \rightarrow \d (\Q) : (x,y)
\mapsto \Bigl( \bigl( {y\over x}\bigr)^2 , 
y - {by\over x^2} \Bigr),$$
$$
\hat\phi : \d (\Q) \rightarrow \c (\Q) : (u,v)
\mapsto \Bigl( {1\over 4} \bigl( {v\over u} \bigr)^2,
{1\over 8} \bigl( v - {b_1 v\over u^2}\bigr) \Bigr).
$$
What are the preimages of $(0,0)$ under $\hat\phi$?
Show that $(0,0) \in 2\c (\Q)$ if and only if there
exist~$m,n\in \Z$ such that $b = m^2$ and $a+2m = n^2$. 
\bigskip
\hrule
\medskip
{\it The following question is compulsory for students taking
the MSc in MFoCS (Mathematics and the Foundations of Computer
Science). For everyone else, it is optional.}
\medskip\medskip\noindent
{\bf 4.} Show that any elliptic curve over $\Q$ with
a rational point of order~$4$ is birationally equivalent to:
$$ Y^2 + XY + v Y = X^3 + v X^2,$$
for some $v\in \Q$.
\vfil \eject %\end
% MARKS ALLOCATED AS FOLLOWS:
% 1: 20. 2: 20. 3: 30. 4: 30. Total: 100.
% In more detail:
% 1: 20. 2: 20. 3: each part 10. 4: 30.
% By the way, delete 3(c) (and soln). Refer them also to exams qn. 6.
% Also, refer them after 4 to exams qn. 7.
% Possible qn 6 for the future: y^2 = x*(x^2 + x + 7)?
\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\sevrm=cmr7
\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\c{{\cal C}}
\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. Sheet 7. To be handed in during 8th Week.}
\rm
\bigskip
\noindent
{\bf 1.} Find the ranks of the
following elliptic curves.
%\par\noindent {\bf (a).} $Y^2 = X(X^2 + 3X + 5)$.
\par\noindent {\bf (a).} $Y^2 = X(X^2 + 5X - 5)$.
\par\noindent {\bf (b).} $Y^2 = X(X^2 + 14X + 1)$.
\par\noindent {\bf (c).} $Y^2 = X(X^2 + 2X + 3)$.
%\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 2.}
A four-letter word $L_1L_2L_3L_4$ has been divided
into two pairs: $L_1L_2$ and $L_3L_4$.
Each of these pairs has been converted
into an integer (of at most 4 digits)
via the standard map: $A \mapsto 01 , B \mapsto 02, \ldots ,
Z \mapsto 26$. These integers have been encoded by taking each to the
power of $d=4085$, modulo $N=10481$. The encoded message reads:
$$ 6012,\, 3236.$$ 
\noindent You may assume that $N$ is the product of two primes. 
You should show, in your calculations, how you are only using
numbers of length at most~$9$ digits.
\par\noindent
{\bf (a)} Find a proper factor of~$N$ (that is, a factor~$d$
of~$N$ satisfying~$1 < d < N$) by 
applying Pollard's ``$p-1$'' method,
using base~$2$ and exponent~$46$.
\par\noindent
{\bf (b)} Factorise $N$ by applying the Elliptic Curve Method,
using the curve $\e : Y^2 = X^3 - X + 1$ and~$3P$, where~$P=(5,11)$.
\par\noindent
{\bf (c)} Use the factorisation of~$N$ to decode the message
(which is the name of the town famous for being the country
music capital of New Zealand).
%\medskip\noindent {\bf 4.} A 16-letter message (including any spaces)
%has been split into 8 pairs
%of letters. Each pair of letters has been encoded into 4 digits,
%using the usual map $A\rightarrow 01,\ldots ,Z\rightarrow 26$
%and $\hbox{space}\rightarrow 00$. Each of these 4-digit blocks
%has been further encoded using the map $X \rightarrow X^d$~(mod~$N$),
%where $d=4903$, $N=8777$, resulting in:
%\par
%$4195\vert 7645\vert 1876\vert 3549\vert 7864\vert 3057\vert 72\vert 3654$.
%\par\noindent Working mod~$N$, find the multiple $k\cdot P$
%on ${\cal E}:Y^2=X^3 + X - 1$, where $P=(1,1)$ and
%$k=2^6\cdot 3^4 \cdot 5$ (explain the way
%that you have efficiently computed $k\cdot P$). Use this to factor~$N$
%(you may assume that $N$ is the product of two primes). Also, factor
%$N$ using Pollard's $p-1$ method, using base~$2$.
%Use the factorisation of~$N$ to deduce the decoding exponent~$e$
%such that $X \rightarrow X^e$~(mod~$N$) reverses the map
%$X\rightarrow X^d$~(mod~$N$). Hence decode the message. You should
%show in your working how you have done all of the above
%computations using only an eight-digit calculator.
\medskip
\hrule
\bigskip
\bigskip
\bigskip
\bigskip
\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
% MARKS ALLOCATED AS FOLLOWS:
% 1: 20. 2: 20. 3: 30. 4: 30. Total: 100.
% In more detail:
% 1: 20. 2: 20. 3: each part 10. 4: 30.
% By the way, delete 3(c) (and soln). Refer them also to exams qn. 6.
% Also, refer them after 4 to exams qn. 7.
% Possible qn 6 for the future: y^2 = x*(x^2 + x + 7)?
\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\sevrm=cmr7
\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\le{\leqslant}
\def\ge{\geqslant}
\def\etq{{\cal E}_{\lower 1pt\hbox{\eightrm tors}}({\Bbb Q})}
\def\c{{\cal C}}
\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. Sheet 8 (Mock Exam and 2006 Exam).}
\rm
\bigskip
\bigskip
The following Mock Exam need not be handed in for classes; it is
intended primarily to help you with your revision in
Trinity Term. It gives an idea of the general style
of the actual exam (of course, there are no guarantees
about whether specific topics in the Mock Exam will
be asked in the actual exam).
Note that parts (a),(b),$\ldots$
of a question may or may not be related to each other.
Note that, in the Mock exam, two of the four
questions have portions that are `bookwork' (reproducing proofs
from lectures). It will also be true of the actual exam
that two of the four questions will include some bookwork.
You will probably also find it helpful to have a caluculator
in the exam; please see the examination regulations for
a description of the types of calculators allowed.
\bigskip
\hrule
\bigskip
\bigskip
\chaptitle
\centerline{Elliptic Curves. Mock Examination.}
\rm
\bigskip
\bigskip
\noindent
\bigskip\noindent {\bf Question 1.}
\medskip\par\noindent{\bf (i)} Find an $x\in\Z$ such that
$| x^2 + 3 |_7 < 7^{-1}$.
\medskip\par\noindent{\bf (ii)} For what prime~$p$ does $-{9\over 8}$ have
$p$-adic expansion $1,\overline{2} = 1 + 2p + 2p^2 + 2p^3 + \ldots$?
%For what~$p$ does $-{1\over 110}$ have $p$-adic expansion
%$11,\overline{1} = p^{-1} + 1 + p + p^2 + p^3 + \ldots$?
\medskip\par\noindent{\bf (iii)} Let~$p \equiv 1$~(mod~$3$) be prime.
Show that~$-3$ is a quadratic residue mod~$p$
[{\it Hint: consider separately the cases $p\equiv 1$~$($mod~$4)$
and $p\equiv 3$~$($mod~$4)$}].
Use Hensel's Lemma to
deduce that~$-3$ is a square in~$\Q_p^*$.
%\par\noindent{\bf (iv)} Let~$p \equiv 2$~(mod~$3$) be a prime.
%Show that $\phi : \F_p \rightarrow \F_p$,
%defined by $\phi (x) = x^3$, is an injection and therefore a bijection.
%Let~$d \in \Z$ be not divisible by~3.
%Show that~$d$ is a cube in~$\Q_p^*$.
\medskip\par\noindent{\bf (iv)} Let $q\equiv 1$~(mod~27) be prime.
Show that $(X^2 + 3)(X^3 - q) = 0$
has solutions in $\R$ and every $\Q_p$.
\bigskip\noindent{\bf Question 2.}
\medskip\par\noindent{\bf (i)} Find the torsion group over~$\Q$
of the elliptic curve $Y^2 = X^3 + 3$.
\medskip\par\noindent{\bf (ii)}
Find the torsion group over~$\Q$ of the elliptic curve
$Y^2 = X^3 + 4 X$.
\medskip\par\noindent{\bf (iii)} Let $n\in \Z$ satisfy~$n \not= 0,\pm 1$.
Show that~$\bigl( n , \pm n(n+1) \bigr)$, 
$\bigl( -n , \pm n(n-1) \bigr)$ are points of
order~$4$ on the elliptic curve~$Y^2 = X(X+1)(X+n^2)$.
Find the torsion group over~$\Q$ when~$n \equiv 2$~(modulo~$5$).
\medskip\par\noindent{\bf (iv)} Let $k \in \Z$, $k \not= 0$, 
let $\e$ be the elliptic curve
$Y^2 = X^3 - k^2 X + k^3$, and let $(x,y)$ be a point of finite
order in ~$\e (\Q)$. Show that $ | y | \le 5 |k|^3$
and $| x | \le 3 |k|^2$.
\bigskip\noindent{\bf Question 3.}
Let $\c : Y^2 = X(X^2 + aX + b)$
and $\d : Y^2 = X(X^2 + a_1 X + b_1)$,
where $a,b\in \Z$ with $b(a^2-4b)\not= 0$ and $a_1 = -2a$,
$b_1 = a^2 - 4b$. Let the map~$\phi$ [which you may assume to
be a homomorphism] be defined as usual by 
$$ \phi : \c (\Q ) \rightarrow \d (\Q) : (x,y)
\mapsto ( {y^2 \over x^2} , y - {by\over x^2} ) .$$
\noindent Let~$q$ be defined as usual by
$$ q : \d (\Q ) \rightarrow \Q^* / (\Q^*)^2 : (u,v) \mapsto u
\hbox{ when }u\not= 0,$$
$$ q : (0,0) \mapsto b_1,\,\,\, q: {\bf o} \mapsto 1, $$
where {\bf o} denotes the point at infinity on~$\d$.
\medskip\par\noindent{\bf (i)} Show that the image of~$q$ is a subset
of the finite set 
$$
\{ r : r \hbox{ is a square free integer and } r | b_1 \}.
$$
\medskip\par\noindent{\bf (ii)} Find the rank of the elliptic 
curve $Y^2 = X(X^2 + 2X + 3)$.
\bigskip\noindent{\bf Question 4.}
A four-letter word $L_1L_2L_3L_4$ has been divided
into two pairs: $L_1L_2$ and $L_3L_4$.
Each of these pairs has been converted into an integer (of at most 4 digits)
via the standard map: $A \mapsto 01 , B \mapsto 02, \ldots ,
Z \mapsto 26$. These integers have been encoded by taking each to the
power of $d=4451$, modulo $N=10001$. The encoded message reads:
$$ 6847,\, 2577.$$ 
\noindent You may assume that $N$ is the product of two primes. 
%You should show, in your calculations, how you are only using
%numbers of length at most~$9$ digits.
\medskip\par\noindent{\bf (i)}
Factorise $N$ by applying Pollard's ``$p-1$'' method,
using base~$2$ and exponent~$68$.
\medskip\par\noindent{\bf (ii)} 
Use the factorisation of~$N$ to decode the message
(which is the name of the animal used as the mascot for the sports
teams at the University of California at Santa Cruz).
\medskip\par\noindent{\bf (iii)} Let~$A$ be an Abelian group with
group operation~$+$, and let
$h : A \longrightarrow \R$ satisfy:
\par
(1) For any $Q\in A$, there exists $C_1 = C_1(Q)$
such that $h(P+Q) \le 2h(P) + C_1$ for all
\par\ \ \ \ \ $P\in A$.
\par
(2) There exists $C_2$, independent of~$P$, such that
$h(2P) \ge 4h(P) - C_2$ for all $P\in A$.
\par
(3) For any~$C_3$, the set $\{ P\in A : h(P) \le C_3\}$ is finite.
\par\noindent
Suppose also that $A/2A$ is finite. Prove that $A$ is
finitely generated.
\medskip\par\noindent{\bf (iv)} Let $A$ and~$h$ be as in~(c).
Suppose that $P$ is a torsion element of~$A$
[that is: there exists an integer $N > 0$ such that
$NP$ is the identity element of~$A$]. Show that
$h(P) \le {1\over 3}{C_2}$.
\bigskip
\bigskip
\hrule
\vfil \eject 
\chaptitle
\noindent
\centerline{Elliptic Curves Questions from the 2006 Examination.}
\rm
\bigskip
\bigskip
\noindent
\bigskip\noindent {\bf Question 1.}
\medskip\par\noindent{\bf (i)}
Let~$K$ be a field, complete with respect to a non-Archimedean
valuation~$|\ \, |$, with valuation ring~$R = \{ x\in K : |x| \leqslant 1\}$.
Prove Hensel's Lemma, that if $f(x) \in R[x]$ and $a_0\in R$ satisfies
$| f(a_0) | < | f'(a_0) |^2$, then there exists a unique $a\in R$ such that
$f(a) = 0$ and $| a - a_0 | \leqslant | f(a_0) |/ | f'(a_0) |$.
%\hfill {\bf [10~marks]}
\medskip\par\noindent{\bf (ii)}
For which primes~$p$ do there exist
$x,y\in \Z_p$ such that $3y^2 = 4 x^3 - 10$?
%\hfill {\bf [7~marks]}
\medskip\par\noindent{\bf (iii)}
For prime $p\not= 2$, determine how many elements there are
in the set ${\bbQ}_p^* / \bigl( {\bbQ}_p^* \bigr)^2$.
Determine how many elements there are
in the set ${\bbQ}_2^* / \bigl( {\bbQ}_2^* \bigr)^2$.
%\hfill {\bf [8~marks]} 
\bigskip\noindent {\bf Question 2.}
Let~$R$ be any ring (commutative, with~1), and let~$F,G$ be
formal groups over~$R$.
\medskip\par\noindent{\bf (i)}
Show that there exists a unique
normalised invariant differential for~$F$, which is given by
$\omega = F_X(0, T)^{-1}\hbox{d} T \in R[[T]] \hbox{d} T$,
and that every invariant differential for~$F$ is of the form $a\omega$
for some $a\in R$.
%\hfill {\bf [8~marks]}
\medskip\par\noindent{\bf (ii)}
Let~$f$ be a homomorphism over~$R$ from~$F$
to~$G$. Let~$\omega_F, \omega_G$ be
the normalised invariant differentials on~$F,G$, respectively.
Show that $\omega_G \circ f = f'(0)\ \omega_F$.
Deduce that, for any prime~$p$, there
exist $f,g\in R[[T]]$
such that $[p](T) = p f(T) + g(T^p)$ [where~$[p]$ represents
the multiplication-by-$p$ map on~$F$].
%\hfill {\bf [9~marks]}
\medskip\par\noindent{\bf (iii)}
Let $m,n\in \Z$, with $n\not= 0$.
Show that the curve $Y^2 = X^3 - (m^2+1)^2 X + 9 n^2$ has infinitely
many $\Q$-rational points.
%\hfill {\bf [8~marks]}
\bigskip\noindent {\bf Question 3.}
\medskip\par\noindent{\bf (i)}
Find a proper factor of $N=1517$ 
%[that is, $d | N$ and $1 < d < N$]
by applying the Elliptic Curve Method,
using the curve $Y^2 = X^3 + 7 X - 7$ and~$4P$, where~$P=(1,1)$.
%\hfill {\bf [8~marks]}
\medskip\par\noindent{\bf (ii)}
Find the torsion group over~$\Q$
of the elliptic curve $Y^2 = X^3 - 2X$.
%\hfill {\bf [7~marks]}
\medskip\par\noindent{\bf (iii)}
Let~${\cal E}_k$ be the elliptic curve~$Y^2 = X^3 + k$,
where~$k\in\Q$ and~$k\not= 0$. 
%Show that, for any point~$(x,y) \not= {\bf o}$
%on~${\cal E}_k$, 
%$$
%3(x,y) = {\bf o} \iff \frac{x(x^3 - 8k)}{4(x^3 + k)} = x.
%$$
Show that there is always a point of order~$3$ 
in~${\cal E}_k({\bbC})$
which is not in~${\cal E}_k(\Q)$.
%\hfill {\bf [10~marks]} % I might consider including the hint.
\bigskip\noindent {\bf Question 4.}
\medskip\par\noindent{\bf (i)}
Find the rank of the elliptic curve $Y^2 = X(X^2 + 3X + 5)$.
%\hfill {\bf [13~marks]} 
\medskip\par\noindent{\bf (ii)}
For any prime $p \equiv 5$~(mod~$8$), show that
the elliptic curve $Y^2 = X^3 + p^2 X$ has rank~$0$.
%\hfill {\bf [12~marks]}
\bigskip
\bigskip
\hrule
\vfil \eject\end 
