\input amssym.def 
\input amssym.tex
%\nopagenumbers
%\magnification=\magstep1
%\hoffset=1truecm
%\voffset=2truecm
%\baselineskip = 5 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\Bbb{\bf}
\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\qss{{({\Bbb Q}^*)^2}}
\def\rss{{({\Bbb R}^*)^2}}
\def\css{{({\Bbb C}^*)^2}}
\def \qmods {{\Bbb Q}^*/({\Bbb Q}^*)^2}
\def \rmods {{\Bbb R}^*/({\Bbb R}^*)^2}
\def \cmods {{\Bbb C}^*/({\Bbb C}^*)^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}
\def \R{{\bf R}}
\def \C{{\bf C}}
\def \Q{{\bf Q}}
\def \Z{{\bf Z}}
\def \F{{\bf F}}
\def \ol{\overline}
\def \pa{{\bf a}}
\def \pb{{\bf b}}
\def \pc{{\bf c}}
\def \pd{{\bf d}}
\def \pe{{\bf e}}
\def \pf{{\bf f}}
\def \pg{{\bf g}}
\def \pk{{\bf k}}
\def \pu{{\bf u}}
\def \pv{{\bf v}}
\def \pw{{\bf w}}
\def \po{{\bf o}}

\def \c{{\cal C}}
\def \d{{\cal D}}
\def \e{{\cal E}}
%
\chaptitle
\noindent
\centerline{Solutions to 1997 Examination. MATH444.}
\rm
\bigskip
\noindent
\noindent {\bf 1.}
{\it Question 1 (a) is a variation of one of the easier
questions on the exercise sheets. Question 1 (b)
is a variation of one of the harder
questions on the exercise sheets, but is not similar to any example in  
lectures.} 
\par\noindent {\bf (a).} The point $(x,y)$ on
$f(X,Y) = Y^2 - X(X-1)^5(X-2) = 0$ is singular if $f(x,y) = 0$,
$(\partial f/ \partial X )(x,y) = (x-1)^4(7x^2-14x+2) = 0$ and
$(\partial f/ \partial Y )(x,y) = 2y = 0$. It follows that~$x$
satisfies both~$x(x-1)^5(x-2)=0$ and $(x-1)^4(7x^2-14x+2) = 0$,
for which the only common solution is~$x=1$, giving~$y=0$.
Hence, $(1,0)$ is the only singular point. {\bf [5~marks]}
\par
$f(X+1,Y+0) = Y^2 +$ terms of higher degree, and so there are
two tangents at~$(1,0)$, namely $Y=0$ with multiplicity two. {\bf [2~marks]} 
\par
The map $(X,Y) \mapsto (X,Y/(X-1)^2)$ gives a birational transformation
from $Y^2 = X(X-1)^5(X-2)$ to $Y^2 = X(X-1)(X-2)$, with inverse
map $(X,Y) \mapsto (X,Y(X-1)^2)$. {\bf [4~marks]}
\par\noindent {\bf (b).} Let $\c_1 : Y^2 = -2X^4 - 2$. Then $(X,Y)
\mapsto (X,Y/\sqrt{-2})$ gives a birational transformation
from $\c_1$ to $\c_2 : Y^2 = X^4 + 1$, with inverse map
$(X,Y) \mapsto (X,Y\sqrt{-2})$. {\bf [4~marks]}
\par
Rearrange $\c_2$ as
$\c_2 : (Y+X^2)\bigl( (Y+X^2) - 2((X(Y+X^2))/(Y+X^2))^2 \bigr) = 1$,
from which it is clear that $(X,Y) \mapsto (Y+X^2, X(Y+X^2))$
gives a birational transformation from $\c_2$ to
$\c_3: X( X - 2(Y/X)^2 ) = 1$, with inverse map
$(X,Y) \mapsto ( Y/X , X - (Y/X)^2 )$. {\bf [4~marks]}
\par
Rearrange~$\c_3$ as $\c_3 : 2Y^2 = X^3 - X$. Finally, the map
$(X,Y) \mapsto (-X, Y\sqrt{-2})$ gives a birational transformation
from $\c_3$ to $\c_4 : Y^2 = X^3 - X$, with inverse
$(X,Y) \mapsto (-X , Y/ \sqrt{-2})$. {\bf [3~marks]}
\par
There is no birational transformation over $\R$, since $Y^2 = -2X^4 - 2$
has no $\R$-rational points, whereas $Y^2 = X^3 + AX + B$, for $A,B\in \Z$,
has infinitely many (for $X$ sufficiently large). This implies
that there is no birational transformation over $\Q$, either. {\bf [3~marks]}
\medskip
\noindent {\bf 2.} {\it Question 2 (a)
requires regurgitation of a proof from lectures (early in the course).
Question~2~(b) requires a bit of ingenuity, and is not a simple
variation of any question on the exercise sheets, although the trick
``$X\mapsto X^3$ injective'' has been seen in another context.} 
\par\noindent {\bf (a).} The following is from lectures [Note that some
of the following text can be quickly summarised by easy diagrams].
For any points $\pa , \pb$ on $\c$, we always let $\ell _{\pa , \pb }$
denote the line through $\pa , \pb$ when $\pa \not= \pb$,
and the line tangent to~$\c$
at $\pa$ when $\pa = \pb$. Note that, by B\'ezout's Theorem,
each line intersects~$\c$ at 3~points.
The line $\ell_{\pa , \pb }$ intersects
$\c$ at one further point, which we denote~$\pd$. The line
$\ell_{\pd , \po}$ intersects~$\c$ at one further point~$\pe$.
We define: $\pa + \pb$ to be $\pe$.
\par First check that $\po$ is the identity. The line $\ell_{\pa , \po}$
intersects~$\c$ at one further point~$\pd$, say. Then $\ell _{\pd , \po}$
must intersect~$\c$ at one further point, which must be~$\pa$,
since $\ell_{\pa , \po}$ is the same line as $\ell _{\pd , \po}$.
Hence, from the definition: $\pa + \po = \pa$.
\par Given $\pa$, one constructs the inverse as follows. The line
$\ell _{\po , \po}$ intersects~$\c$ at one further point: $\pk$, say.
The line $\ell _{\pa , \pk}$ intersects~$\c$ at one further point:
$\bar\pa$, say. Then, we claim that $\bar\pa$ is the inverse of~$\pa$.
Check: $\ell _{\pa , \bar\pa}$ intersects~$\c$ at one further point,
which must be
$\pk$ (since $\ell _{\pa , \bar\pa} = \ell _{\pa , \pk}$),
and $\ell _{\pk , \po}$ intersects~$\c$ at one further point,
which must be 
$\po$ (since $\ell _{\pk , \po} = \ell _{\po , \po}$). So,
$\pa + \bar\pa = \po$, as required.
\par
Finally, let $\pa , \pb , \pc$ be points on~$\c$. Let
$l = \ell_{\pa,\pb}$, which intersects $\c$ at one
further point: $\pd$, say. Let $t = \ell_{\pd , \po}$,
which intersects $\c$ at one
further point: $\pe$, say.
Let $m = \ell_{\pc , \pe}$, which intersects $\c$ at one
further point: $\pf$, say.
Let $s = \ell_{\pb , \pc}$, which intersects $\c$ at one
further point: $\pu$, say.
Let $n = \ell_{\po , \pu}$, which intersects $\c$ at one
further point: $\pv$, say.
Let $r = \ell_{\pa , \pv}$, which intersects $\c$ at one
further point: $\pw$, say.
From the definition of the group law, $\pa + \pb = \pe$,
and $(\pa + \pb) + \pc$ is given by third point of
intersection of $\ell_{\po , \pf}$ with $\c$.
Also, $\pb + \pc = \pv$, and $\pa + (\pb + \pc)$ is given by third point of
intersection of $\ell_{\po , \pw}$ with $\c$.
Hence $(\pa + \pb) + \pc = \pa + (\pb + \pc) \iff \pf = \pw$.
But, the 3 cubics: $l  m  n$
and $rst$ and $\c$ all go through the~8 points: $\pa , \pb , \pc , \pd , \pe ,
\pu , \pv , \po$. From a standard theorem in geometry (from lectures),
given these~8 points, there is a unique ninth point $P_9$ such that
any two cubics through these~8 points has $P_9$ as the ninth
point of intersection. Hence~$\pf$ (which lies on $l m n $ and $\c$)
is the same point as \pw (which lies on $rst$ and $\c$), as required.
{\bf [14~marks]}
\par\noindent {\bf (b).} Discriminant of the
cubic $X^3 - a$ is~$4\cdot 0^3 + 27\cdot (-a)^2
= 27 a^2$, which is nonzero in $\F_p$; hence $Y^2 = X^3 - a$
over $\F_p$ is nonsingular and is an elliptic curve. {\bf [4~marks]}
\par
Note that $3$ is coprime to
$p-1$, and so there exist $\lambda , \mu \in \Z$ such
that $(p-1) \lambda  + 3 \mu  = 1$. Now, suppose that $v^3 = w^3$ in
$\F_p^*$.
Then $v^{3 \mu} = w^{3 \mu}$. Also $(p-1) \lambda$ is a multiple of
the order of the group $\F_p^*$ and so $v^{(p-1) \lambda}
= w^{(p-1) \lambda}$ (since both are equal to~1). Multiplying these
last two equations gives: $v^{(p-1) \lambda  + 3 \mu} = 
w^{(p-1) \lambda  + 3 \mu}$, and so $v = w$. We have shown that
$v^3 = w^3$ implies $v=w$, and so the map $v \mapsto v^3$ is
injective, and hence surjective, from $\F_p^*$ to $\F_p^*$. It follows
that there exists an $x_o \in \F_p^*$ such that $x_0^3 = a$.
The point $(x_0,0)$ is then a point of order~2 in $\e (\F_p)$. {\bf [7~marks]}
\medskip
\noindent {\bf 3.}
\noindent{\it Question 3 (a),(b)
are easy variations of examples from both lectures and the examples sheets. 
Question~3~(c),(d) require some ingenuity, and are not
variations of any question on the exercise sheets.}
\par\noindent {\bf (a).} Let
$x_0 = a_0 = 2$. Then $| x_0^2 + 1 |_5 = 5^{-1}$.
Look for $x_1 = a_0 + 5a_1$ such that $| x_1^2 + 1 |_5 = 5^{-2}$.
This is satisfied if: $(2 + 5a_1)^2 \equiv -1$ (mod $5^2$)
$\iff 2\cdot 2\cdot 5 a_1 \equiv -1 - 2^2 (\hbox{mod } 5^2)
\iff 4 a_1 \equiv -1 (\hbox{mod } 5) \iff a_1 \equiv 1 (\hbox{mod } 5)$.
So, now define: $a_1 = 1$ and $x_1 = a_0 + 5a_1 = 7$. Check
that indeed $|x_1^2 + 1 |_5 =|50|_5 = 5^{-2}$. {\bf [4~marks]}
\par  
Now, look for $x_2 = a_0 + 5a_1 + 5^2a_2$
such that $| x_2^2 + 1 |_5 = 5^{-3}$.
This is satisfied if: $(7 + 5^2a_2)^2 \equiv -1$ (mod $5^3$)
$\iff 2\cdot 7\cdot 5^2a_2 \equiv -1 - 7^2 (\hbox{mod } 5^3)
\iff 14 a_2 \equiv -2 (\hbox{mod } 5) \iff a_2 \equiv 2 (\hbox{mod } 5)$.
So, now define: $a_2 = 2$ and $x_2 = 7 + 5^2a_1 = 57$. Check
that indeed $|x_2^2 + 1 |_5 =|3250|_5 = 5^{-3}$. {\bf [4~marks]}
\par\noindent {\bf (b).} Let $\beta = \alpha - 11/5 = 0,\overline{34}$.
Then $5^2 \beta = 0,00\overline{34} = \beta - (3\cdot 5^1 + 4\cdot 5^2)$;
that is: $24\beta = -115$ and so $\beta = -115/24$.
This gives: $\alpha = \beta + 11/5 = -311/120$. {\bf [4~marks]}
\par\noindent {\bf (c).} The map $x\mapsto x^2$ on $F_p$ takes $0 \mapsto 0$,
and is a 2-to-1 map on $\F_p^*$. It follows that the both of
the given sets have size~$(p-1)/2 + 1 = (p+1)/2$. {\bf [3~marks]}
\par
Since $\F_p$ has only~$p$ elements, and the sum of the sizes of the
given sets is~$p+1$, there must be an element common to both
sets. That is, there must exist $x,y\in\F_p$ such that
$x^2 = a-y^2$, and so $x^2 + y^2 = a$. {\bf [3~marks]}
\par\noindent {\bf (d).} Let $a\in \F_p$ be the reduction
of $b$ modulo~$p$. Then $a\in \F_p^*$, since $|b|_p=1$.
From (c), there exist $x_0,y_0\in \F_p$ such that
$x_0^2 + y_0^2 = a$ in $\F_p$. Since $a\not=0$, at least
one of $x_0,y_0$ is nonzero; say that $x_0 \not= 0$. Let
$y\in \Z$ be any choice of $y\equiv y_0$ modulo~$p$.
Then $b-y^2\in \Z$, satisfies $|b-y^2|_p = 1$ and there
exists an $x_0$ such that $| x_0^2 - (b-y^2) |_p < 1$.
Applying Hensel's Lemma to the polynomial $F(T) = T^2 - (b-y^2)$
gives that there must exist an $x\in \Z_p$ such that
$F(x) = 0$, as required. {\bf [7~marks]}
\medskip
\noindent {\bf 4.} {\it Question 4 (a) is similar to a question
from the example sheet, but requires some hard work. For Question~4~(b)
the special case $Y^2 =  (X^2 - 2)(X^2 - 17)(X^2 - 34)$ has been seen,
which Question~4~(b) is asking them to generalise.}
\par\noindent {\bf (a).}
The discriminant of $f(X) = X^3 + 2X + 2$
is $4\cdot 2^3 + 27\cdot 2^2 = 140 = 2^2\cdot 5\cdot 7$, so the
curve $\widetilde \e : Y^2 = X^3 + 2X + 2$ is an elliptic curve over all $\F_p$
except $p=2,5,7$. {\bf [2~marks]}
\par For $p\geqslant 11$, the number of points
in $\e (\F_p)$ is at least $p+1 - 2\sqrt{p} > 4$. Excluding
{\bf o} and points of the form~$(x,0)$ (of which there are at
most~3), there must be at least one point $(x_0,y_0)\in \e (\F_p)$
such that $y_0\not= 0$. Let $\alpha = x_0^3 + 2x_0 + 2$; then
$| \alpha |_p = 1$ and there exists $y_0$ such that
$| y_0^2 - \alpha |_p < 1$. So, applying Hensel's Lemma
to $G(T) = T^2 - \alpha$, there
exists $y\in \Z_p$ such that $y^2 = x_0^3 + 2x_0 + 2$. {\bf [3 marks]}
\par
For $p=2$, working modulo~8, we see that, for $X=0,1,\ldots 7$,
we have $f(X)$ congruent to $2,5,6,3,2,1,6,7$. Taking~$x=5$ then
gives $f(x) = 137 \equiv 1$ (mod~8), and so by a standard instance
of Hensel's Lemma from lectures
[namely that, when $|a|_2=1$,
$a$ is a square in $\Z_2$
if and only if $a\equiv 1$ mod~8], there exists $y\in \Z_2$ such
that $y^2 = 137$, giving $(5,y) \in \e (\Z_2 )$. {\bf [3 marks]}
\par
For $p=3$, working modulo~3, we see that for $X=0,1,2$, we have $f(X)$
congruent to $2,2,2$ modulo~3; but $2$ is not a square mod~3.
[So there can't be any $(x,y) \in \e (\Z_p)$ since, if there were,
the reduction of the point modulo~3 would give a solution
to $y^2 = x^3 + 2x + 2$ in $\F_3$].
\par
For $p=5$, working modulo~5, we see that for $X=0,1,2,3,4$, we have $f(X)$ 
congruent to $2,0,4,0,4$ modulo~5. Taking, for example, $x=2$, then gives
$f(x) = 14 \equiv 4$ (mod~5), which is a square in $\F_5$,
and so by a standard instance
of Hensel's Lemma from lectures
[namely that, when $|a|_p=1$, $p\not= 2$,
$a$ is a square in $\Z_p$
if and only if $a$ is a square in~$\F_p$], there exists $y\in \Z_5$ such
that $y^2 = 14$, giving $(2,y) \in \e (\Z_5 )$.
\par
For $p=7$, working modulo~7, we immediately notice that, taking
$x=0$ gives $f(0) = 2$, which is a square in $\F_7$,
and so by the same standard instance
of Hensel's Lemma from lectures as above, there exists $y\in \Z_7$ such
that $y^2 = 2$, giving $(0,y) \in \e (\Z_7 )$. {\bf [6 marks]}
\par Conclusion: there exist $x,y\in \Z_p$ such that
$y^2 = x^3 + 2x + 2$, for all~$p$ except~$p=3$. Finally, there
do not exist such $x,y\in \Z$, since $\Z \subset \Z_3$. {\bf [2 marks]}
\par\noindent {\bf (b).} In $\R$ there is, for example, the root $\sqrt{2}$. 
{\bf [1 mark]}
\par
In~$\Q_2$, $q\equiv 1$ modulo~$8$, so by the standard instance
of Hensel's Lemma from lectures [namely that, when $|a|_2=1$,
$a$ is a square in $\Z_2$
if and only if $a\equiv 1$ mod~8], we have a root of $X^2 - q$.
{\bf [2 marks]}
\par
We know that $2$ is a quadratic residue modulo~$q$ [from the standard
result that $2$ is a quadratic modulo~$q$ iff $q\equiv \pm 1$~(mod~8)].
Hence~$2$ is a square in~$\F_q$ by the standard instance
of Hensel's Lemma from lectures  [namely that, when $|a|_q=1$, $q\not= 2$, 
$a$ is a square in $\Z_q$  
if and only if $a$ is a square in~$\F_q$], and so there is
a root of $(X^2 - 2)$ in $\Z_q$. {\bf [3 marks]}
\par For all other primes $p$, with $p\not= 2,q$, note that the
Legendre symbols satisfy:
$\bigl( {2\over p} \bigr)\bigl({q\over p}\bigr)
= \bigl( {2q \over p}\bigr)$,
and so at least one of:
$\bigl( {2\over p} \bigr), \bigl({q\over p}\bigr) , \bigl( {2q \over p}\bigr)$
must have value~1. Now, the same standard instance
of Hensel's Lemma from lectures as above implies that at least
one of $2,q,2q$ must be a square in $\Z_p$, also. {\bf [3 marks]}
\medskip
\noindent {\bf 5.} {\it Question 5 (a)
requires regurgitation of a proof from lectures (middle of the course).
Question~5~(b) is a variation of an example from the example sheets.
Question~5~(c) requires some ingenuity, and is not a simple
variation of any question on the exercise sheets.}
\par\noindent {\bf (a).} The Nagell-Lutz Theorem
states that, if~$(x,y)$ is a $\Q$-rational torsion point 
on $\e : Y^2 = X^3 + AX + B$, where $A,B\in \Z$, then
$x,y\in\Z$ and $y = 0$ or $y^2 | \Delta$, where $\Delta = 4A^3 + 27B^2$. 
\par\noindent {\bf Proof (from lectures).} We are given the result that
$x,y\in \Z$. If $y = 0$ then the result is satisfied; otherwise,
$(x,y)$ is not $2$-torsion and we can consider $(x_2,y_2) = 2(x,y)$,
with $(x_2,y_2) \not= \po$, and so $x_2,y_2\in \Q$. But~$(x_2,y_2)$
is also a torsion point, so $x_2 , y_2 \in \Z$. Now, the line
tangent to~$\e$ at~$(x,y)$ has slope $(3x^2+A)/(2y)$, from
which we immediately get: $x_2 = \bigl( (3x^2+A)/(2y) \bigr)^2 - 2x$.
Now, we know $x_2, x\in \Z$ and so $\bigl( (3x^2+A)/(2y) \bigr)^2\in \Z$.
It follows that $4y^2 | (3x^2+A)^2$ and so $y^2 | (3x^2+A)^2 = \psi_1(x)$.
Also, $y^2 = x^3 + Ax + B = \psi_2(x)$. Using the identity given
on the exam paper, $y^2 | (\phi_1(x)\psi_1(x) + \phi_2(x)\psi_2(x))
= \Delta$, as required.
{\bf [10 marks]}
\par\noindent {\bf (b).} The discriminant of $X^3 - 2X$ is~$4\cdot (-2)^3
= -32$, and so $\widetilde \e : Y^2 = X^3 - 2X$ is an elliptic curve
for all $p\not= 2$. The elements of
$\widetilde \e (\F_3 )$ are: ${\bf o}, (0,0), (2,\pm 2)$, and
so $\widetilde \e (\F_3 )$ has order~4. The elements of
$\widetilde \e (\F_5 )$ are: ${\bf o}, (0,0), (1,\pm 2),
(2,\pm 2), (3,\pm 1), (4,\pm 1)$, so that
$\widetilde \e (\F_5 )$ has order~10. Since the torsion subgroup
of $\e (\Q)$ injects into both of these groups, its order
must divide $\hbox{gcd}(4,10) = 2$. But, there is a point of
order~2 in $\e (\Q)$, namely~$(0,0)$. Hence the torsion subgroup 
of $\e (\Q)$ is precisely~$\{ {\bf o} , (0,0) \}$. {\bf [8 marks]}
\par\noindent {\bf (c).} There is a point~$(n,m) \in \e (\Q )$.
We now double this point to find: $(x,y) = 2(n,m)$. The line through
$(n,m)$ tangent to~$\e$ has slope $(3X^2)/(2Y)$, evaluated at
$X=n$, $Y=m$, that is: $(3n^2)/(2m)$. Then,
$x = \bigl( (3n^2)/(2m) \bigr)^2
- 2n$. But $(3n^2)/(2m)$ is not an integer, since $m,n> 3$ and
$\hbox{gcd}(m,n) = 1$, so that $x$ is not an integer. Hence
$(x,y)$ is not a torsion point, and so must be a point of
infinite order in~$\e (\Q)$.  {\bf [7~marks]}
\medskip
\noindent {\bf 6.} {\it Examples like this have appeared on the
exercise sheets, but these descents via isogeny are probably
the hardest thing in the course, since they require
bringing together most of the techniques learnt throughout the
course. I thought it was sufficient, therefore, to give a standard
descent-via-isogeny as an entire question.} 
\par\noindent
Let $\c : Y^2 = X(X^2 + aX + b) = X(X^2 + X - 2)$,
where $a=1, b=-2$,
and isogenous curve $\d : Y^2 = X(X^2 + a_1X + b_1) = X(X^2 - 2X + 9)$,
where $a_1 = -2, b_1=9$,
with the usual isogeny $\phi : \c (\Q ) \rightarrow 
\d (\Q) : (x,y) \mapsto (y^2/x^2 , y + 2y/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 - 9v/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 3 \}$. Also, ${\bf o} \mapsto 1$,
$(0,0) \mapsto 9 = 1$ and $(3,6) \mapsto 3$, so that
$\{ 1,3 \} \subset \hbox{im} 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} 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 - 2 \ell^2m^2  - 9 m^4 = n^2$. This is impossible in~$\R$,
and so impossible in~$\Q$. Hence $-1 \not\in \hbox{im} q$.
{\bf [4 marks]}
\par We conclude that $\hbox{im} q  = \{ 1,3 \}$, and
so $\d (\Q) / \phi (\c (\Q))$ is generated by~$(3,6)$.
{\bf [1 mark]}
\par
The map $\hat q : \c (\Q ) / \hat\phi (\d (\Q))
\rightarrow \qmods : (x,y) \mapsto u$,
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 2 \}$. 
Also, ${\bf o} \mapsto 1$ and
$(0,0) \mapsto -2$, so that
$\{ 1,-2 \} \subset \hbox{im} \hat 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} \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 + \ell^2m^2  + 2 m^4 = n^2$. Multiply both sides
by~4 and rewrite
as: $ - ( 2 \ell^2 - m^2 )^2 + 9 m^4 = 4 n^2$. Reducing modulo~3
gives: $ - ( 2 \ell^2 - m^2 )^2 \equiv n^2$ (modulo~3). If $n$ were
coprime to~$3$, then this would give: $(( 2 \ell^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 | ( 2 \ell^2 - m^2 )$, also. Then $2\ell^2 \equiv m^2$
and so by the same reasoning (since~$2$ is not a
quadratic residue modulo~3) we have that $3 | \ell$ and $3 | m$. 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} \hat q$.
{\bf [6 marks]}
\par  We conclude that $\hbox{im} \hat q  = \{ 1,-2 \}$, 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( (3,6) \bigr) = (1,0)$]. Conclusion:
$\c (\Q ) / 2\c(\Q )$ is generated by $(0,0)$ and $(1,0)$,
both of which are points of finite order (order~2, in fact).
Conclusion: $\c (\Q)$ has rank~0.
{\bf [4 marks]}
%\medskip
%\noindent {\bf 7.} {\it Question 7 (a),(b)
%requires regurgitation of a proof from lectures (towards the end
%of the course).
%Question~7~(c) is hard; it is not a simple
%variation of any question on the exercise sheets; the actual answer
%to Question~7~(c) is not too long, but requires genuine insight
%as to what is going on.}
%\par\noindent {\bf (a).} (From lectures). Let~$(u_1,v_1),
%(u_2,v_2),(u_3,v_3)$ be~3 points on~$\d(\Q)$ which sum to~$\po$,
%so that $(u_1,v_1) + 
%(u_2,v_2)= (u_3,-v_3)$.
%Then there are the~3 points of intersection between~$\d$
%and some line defined over~$\Q$: 
%$Y = \ell X + m$, say. Substituting~$Y = \ell X + m$
%into $\d$ gives: $X(X^2 + a_1X + b_1) - (\ell X + m)^2$,
%whose 3~roots must be~$u_1,u_2,u_3$.  
%That is: $X(X^2 + a_1X + b_1) - (\ell X + m)^2
%= (X-u_1)(X-u_2)(X-u_3)$. Equating constant terms gives:
%$u_1 u_2 u_3 = m^2 = 1$ in $\qmods$, and so $u_1 u_2 = 1/u_3 = u_3$
%in $\qmods$.
%Therefore, by the definition of~$q$ we have:
%$q\bigl( (u_1,v_1) \bigr) q\bigl( (u_2,v_2) \bigr)
%= q\bigl( (u_3,v_3) \bigr)$, as required. {\bf [6 marks]}
%\par\noindent {\bf (b).} (From lectures). Given~$(u,v)\in \d(\Q)$,
%we can see that $(x,y)$ (not necessarily $\Q$-rational) on $\c$, a preimage
%of~$(u,v)$ under~$\phi$,
%satisfies: $y/x = \pm \sqrt{u}$ [since $u = y^2/x^2$]. Combining this with:
%$(x/y)v = x-b/x$ and $u = x + b/x + a$ [since
%$u = y^2/x^2 = x(x^2+ax+b)/x^2$] gives: $x = ( u \pm v/\sqrt{u} -a)/2$,
%and so $y = (y/x)x = \pm\sqrt{u}( u \pm v/\sqrt{u} -a)/2$. Clearly,
%$(u,v) \in \phi (\c (\Q) ) \iff $
%\par\noindent
%$\bigl( (u + v/\sqrt{u} -a)/2,
%\sqrt{u}( u + v/\sqrt{u} -a)/2 \bigr)
%\hbox{ or }\bigl( ( u - v/\sqrt{u} -a)/2,
%-\sqrt{u}( u - v/\sqrt{u} -a)/2\bigr)$ is in $\c (\Q)$\par\noindent
%$\iff \sqrt{u} \in \Q \iff q\bigl((u,v)\bigr) = 1$, as required.
%{\bf [6 marks]}
%\par\noindent {\bf (c).} 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)$.
%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
%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$. {\bf [8 marks]}
\medskip
\noindent {\bf 7.} {\it Question 7 (a),(b),(c) are variations
of a question on one of the examples sheets, but the computations
take some time; those who use the proper ``speeding up'' tricks should
have no problem doing this question within 30 minutes, but those
who use inefficient methods might not.} 
\par\noindent
In all of the following, each step multiplies
numbers of at most~4 digits in length (followed by a possible reduction
modulo~$N$), and so everything can be done on an $8$-digit
calculator. 
\par\noindent {\bf (a).} First compute (modulo $N=10123$):
$2^1 \equiv 2$, $2^2 \equiv 4$, $2^4 \equiv 16$, $2^8 \equiv 256$,
$2^{16} \equiv 4798$, $2^{32} \equiv 1102$ (where each of these
was obtained be squaring the previous one, and reducing modulo~$N$). 
Now, we write $52$ in base~2: $52 = 4 + 16 + 32$ and
so $2^{52} \equiv 2^4 2^{16} 2^{32} \equiv 
16\cdot 4798 \cdot 1102 \equiv 5907 \cdot 1102 \equiv
425$ modulo~$N$, 
so that $2^{52} - 1 \equiv 424$ modulo~$N$.
\par
Now, compute $\hbox{gcd}(424, N)$ by Euclid's Algorithm:
$10123 = 23 \cdot 424 + 371$; $424 = 1\cdot 371 + 53$;
$371 = 7\cdot 53 + 0$. So, $53$ is a factor of $N$.
Compute $10123/53 = 191$, giving the factorisation
$N = 10123 = 53 \cdot 191$. {\bf [8~marks]} 
\par\noindent {\bf (b).} The line tangent to~$\e$ at $P=(1,1)$
has slope $y'$ given by $2yy' = 3x^2 + 5$, with $x=1,y=1$;
that is, the slope is $8/2 = 4$. This tangent line also goes
through $(1,1)$ and so has equation: $Y = 4X - 3$.
The $x$-coordinate of $2P$ is therefore $4^2 - (1+1) = 14$,
and the $y$-coordinate is: $-(4\cdot 14 - 3) = -53\equiv 10070$,
so that $Q = 2P = (14 , 10070)$ (modulo~$N=10123$). 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 10070 \cdot y' = 3\cdot 14^2 + 5$,
and so we need to compute $(3\cdot 14^2 + 5) / (2\cdot 10070)$
(modulo~$N=10123$), for which the first step is to find the
inverse of $2\cdot 10070 \equiv 10017$ (modulo~$N=10123$).
Using Euclid's Algorithm: $10123 = 1\cdot 10017 + 106$;
$10017 = 94 \cdot 106 + 53$; $106 = 2\cdot 53 + 0$. So, we cannot
find the inverse of $10017$ (modulo~$N=10123$), and this
step has given us our factor~$53$ of~$N$. As before,
compute $10123/53 = 191$, giving the factorisation
$N = 10123 = 53 \cdot 191$. {\bf [9~marks]}
\par\noindent {\bf (c).}  Since $N = 53 \cdot 191$, we have
$\phi (N) =52 \cdot 190 = 9880$. Compute the gcd of $d=6587$ and
$\phi(N)$, we see: $9880 = 1\cdot 6587 + 3293$; $6587 = 2\cdot 3293 + 1$,
so that $\hbox{gcd}(9880,241) = 1$. Reversing the steps:
$1 = 6587 - 2\cdot 3293 = 6587 - 2\cdot (9880 - 1\cdot 6587) =
3\cdot 6587 - 2\cdot 9880$. Hence, $3$ is the inverse of
$6587$ modulo~$9880$.
The decoding operation is therefore $X \mapsto X^{3} \hbox{ mod }N$.
Computing $4268^3 = 4268^2\cdot 4268 \equiv 4547 \cdot 4268\equiv
805$ (modulo~$N = 10123$). Also: $5744^3 = 5744^2 \cdot 5744
\equiv 2679 \cdot 5744 \equiv 1216$ (modulo~$N = 10123$). The decoded
message is therefore: $0805,\, 1216$; that is: HELP. {\bf [8~marks]}
\medskip
\hrule
\vfil \eject \end
%\bigskip
%\bigskip
%\centerline{\bf A Few General Comments
%About This Year's Exam (January 1999)} 
%\medskip
%The exam will be for $2{1\over 2}$ hours, and will have 7 questions
%(each worth 25 marks)
%of which you should answer~4. You are welcome to answer more
%than~4, in which case I shall mark all of them, but only
%your best~4 marks will count.
%\par
%You are guaranteed (for the January 1999 exam)
%that Question~6 will be of the same type as for the 1997 exam
%above, i.e.\ you will be asked to find the
%rank of an elliptic curve of the form $Y^2 = X(X^2 + aX + b)$,
%where $a,b\in \bbZ$. You are also guaranteed that Question~7
%will be a cryptography question, that the computations will
%be possible on a $9$-digit calculator, that~$N$
%will be the product of two distinct primes, that I shall
%give you the exponent to use in Pollard's $p-1$
%method, that I shall give you the
%multiple of~$P$ to take in the Elliptic Curve Method
%(you won't have to search for
%and try out different exponents/multiples
%until you find one that works), and
%that if you are asked to find a mutiple $mP$ in the
%Elliptic Curve Method then $m \leqslant 5$. 
%\par
%In Questions $1,\ldots , 5$ there will be approximately 25~marks
%of `bookwork'; that is to say, where you are required to
%reproduce proofs from lectures. Only proofs which I have
%actually done on the blackboard are examinable (if I give
%you a theorem and proof only on a handout, then you need to know
%the statement of the theorem and how to apply it to problem
%solving, but you need not know the proof). The bookwork
%will be divided between 2~questions; for example, you can
%see in the 1997 exam that the bookwork portions
%were Question~2(a)~[14~marks] and Question~5(a)~[10~marks]. 
%\par
%Otherwise, questions are based on skills you have used in
%doing the exercise sheets, sometimes an easy variation
%of an exercise sheet question (normally as the first
%part of the exam question), sometimes requiring a bit 
%more thought (normally as the last part of the exam question).