\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\eightsl=cmsl8
\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\geqslant{\ge}
\def\Bbb{\bf}
\def\c{{\cal C}}
\def \qtmods {{\Bbb Q}_3^*/({\Bbb Q}_3^*)^2}
\def \qts {({\Bbb Q}_3^*)^2}
\def \q{{\Bbb Q}}
\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\ctq{{\cal C}_{\lower 1pt\hbox{\eightsl tors}}({\Bbb Q})}
\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 \cq{{\cal C}(\Q)}
\def \d{{\cal D}}
\def \e{{\cal E}}
\def \te{{\widetilde {\cal E}}}
%
\chaptitle
\noindent
\centerline{Solutions to 1999 Examination. MATH444.}
\rm
\bigskip
\noindent
\noindent {\bf 1.}
{\it
All parts~(a),(b),(c)
are variations of three easy-to-medium-level-difficulty 
questions on the exercise sheets, but are not similar to any examples in  
lectures.} 
\par\noindent {\bf (a).} First consider the case where $Z=0$.
Then the equations become $X^3 = 0$ and $Y^2 = X^2$, so that
$X=Y=0$, which does not give rise to any point, since $(0,0,0)$
is not allowed in projective space. So, we can assume that
$Z\not= 0$ and use $x=X/Z, y=Y/Z$ with associated affine curves:
$y^2 = x^3 + 1$ and $y^2 = x^2 + 1$. The $x$-coordinate of
any common point will therefore satisfy $x^3 + 1  = x^2 + 1$,
and so $x^2(x-1) = 0$, giving $x=0,1$. The only possible points
of intersection are therefore $(0,\pm 1)$ and $(1,\pm \sqrt{2})$,
all of which clearly do lie on both curves. The slope of $y^2 = x^3 + 1$
at $(0,1)$
can be found by substituting
$x=0,y=1$ into $2y \hbox{d}y/\hbox{d}x = 3x^2$, giving
$\hbox{d}y/\hbox{d}x = 0$ at~$(0,1)$.
The slope of $y^2 = x^2 + 1$ at $(0,1)$
can be found by substituting
$x=0,y=1$ into $2y \hbox{d}y/\hbox{d}x = 2 x$, again giving
$\hbox{d}y/\hbox{d}x = 0$ at~$(0,1)$.
Since $\hbox{d}y/\hbox{d}x$ is the same at~$(0,1)$
for both curves, the multiplicity of
intersection at $(0,1)$ must be at least~2; similarly the
multiplicity of
intersection at $(0,-1)$ must be at least~2.
By B\'ezout's Theorem, the total number of
intersections (with multiplicities) is~$2\times 3 = 6$, so that
the only possibility is: multiplicity~2 for each of~$(0,\pm 1)$,
and multiplicity~1 for each of~$(1,\pm \sqrt{2})$.
Returning to projective coordinates~$(X,Y,Z)$ on the original
projective curves, we have as intersection points:
multiplicity~2 for each of~$(0,\pm 1, 1)$,
and multiplicity~1 for each of~$(1,\pm \sqrt{2},1)$.
{\bf [10~marks]} 
\par\noindent{\bf (b).} The map
$(X,Y) \mapsto (2X, 2Y)$ [with inverse $(X,Y) \mapsto (X/2, Y/2)$]
gives a birational transformation from $Y^2 = 2X^3 + 3X^2 + 1$
to $(Y/2)^2 = 2(X/2)^3 + 3(X/2)^2 + 1$, which is the same as
$Y^2 = X^3 + 3X^2 + 4$. The map
$(X,Y) \mapsto (X+1, Y)$ [with inverse $(X,Y) \mapsto (X-1, Y)$] 
gives a birational transformation from $Y^2 = X^3 + 3X^2 + 4$ 
to $Y^2 = (X-1)^3 + 3(X-1)^2 + 4$, which is the same as 
$Y^2 = X^3 - 3X + 6$, which is in the required form.
{\bf [7~marks]}
\par\noindent{\bf (c).} The map  $(X,Y) \mapsto (X,-iY)$
[with inverse $(X,Y) \mapsto (X,iY)$]
gives a birational transformation from $Y^2 = -X^4 - 5$  
to $(iY)^2 = -X^4 - 5$, which is the same as $Y^2 = X^4 + 5$.
The map  $(X,Y) \mapsto (1/X,Y/X^2)$ 
[self inverse] 
gives a birational transformation from $Y^2 = X^4 + 5$ 
to $(Y/X^2)^2 = (1/X)^4 + 5$, which is the same as $Y^2 = 5 X^4 + 1$,
as required. A birational transformation is not possible over~$\Q$,
since such a transformation would also be defined over~$\R$,
contradicting the fact that
$Y^2 = -X^4 - 5$ has no $\R$-rational points, whereas
$Y^2 = 5 X^4 + 1$ has infinitely many.~{\bf [8~marks]}
\medskip
\noindent {\bf 2.} {\it Parts (a),(b) are variations of
average-level-difficulty questions on the exercise sheets. Part~(c)
is not a variation of an exercise sheet question (nor a lectured
example), and the last part of~(c),
in particular, is quite hard and requires some
insight.}
\par\noindent {\bf (a).} Note that $|1/2|_3 = 1$, so the
$3$-adic expansion is of the form: $1/2 = a_0,a_1 a_2\ldots
= a_0 + 3a_1 + 3^2a_2 + \ldots$. So, $1 = 2(a_0 + 3a_1 + 3^2a_2 + \ldots)$.
This gives $1 \equiv 2a_0$ (mod~$3$), so that $a_0=2$. Hence,
$1 \equiv 2\cdot 2 + 2\cdot 3 a_1$ (mod~$9$), which
implies $-3 \equiv 2\cdot 3 a_1$ (mod~$9$), and so $-1 \equiv 2 a_1$ (mod~$3$),
giving $a_1 = 1$. Similarly, $a_2 = 1$ and $a_3=1$.
At this point, we suspect that $1/2 = 2,\overline{1}$. We can
confirm this by letting $x=2,\overline{1}$. Then $x-2 = 0,\overline{1}$
and so $3(x-2) = (x-2) - 3$,
so that $2x = 1$; that is: $x = 1/2$, as required.
Finally, $3/2 = 3\cdot(1/2)$, so that the $3$-adic expansion
of $3/2$ is the same as that of $1/2$, but moved one place to
the right; that is: $3/2 = 0,2\overline{1}$.
For~$x\in \Z$ such that $| x - {1\over 2} |_3 < 3^{-4}$, we can
take $x$ to be the $3$-adic exansion of $1/2$ up to and
including the $3^4$ term: $x=2,111 = 2 + 3^1 + 3^2 + 3^3 + 3^4
= 122$. Check: $| 122 - {1\over 2} |_3 = |243/2|_3 | =
| 3^5/2 |_3 = 3^{-5}$.~{\bf [10~marks]}
\par\noindent {\bf (b).} Let
$x_0 = a_0 = 3$. Then $| x_0^2 - 2 |_7 = 7^{-1}$.
Look for $x_1 = a_0 + 7a_1$ such that $| x_1^2 - 2 |_7 \leqslant 7^{-2}$.
This is satisfied if: $(3 + 7a_1)^2 \equiv 2$ (mod $7^2$)
$\iff 2\cdot 3\cdot 7 a_1 \equiv 2 - 3^2\ (\hbox{mod } 7^2)
\iff 6 a_1 \equiv -1\ (\hbox{mod } 7) \iff a_1 \equiv 1\ (\hbox{mod } 7)$.
So, now define: $a_1 = 1$ and $x_1 = a_0 + 7a_1 = 10$. Check
that indeed $|x_1^2 - 2 |_7 =|98|_7 = 7^{-2}$. {\bf [3~marks]}
\par\noindent
Now, look for $x_2 = a_0 + 7a_1 + 7^2a_2$
such that $| x_2^2 - 2 |_7 \leqslant 7^{-3}$.
This is satisfied if: $(10 + 7^2a_2)^2 \equiv 2$ (mod $7^3$)
$\iff 2\cdot 10\cdot 7^2a_2 \equiv 2-100 \equiv -98\ (\hbox{mod } 7^3)
\iff 20 a_2 \equiv -2\ (\hbox{mod } 7)
\iff a_2 \equiv 2\ (\hbox{mod } 7)$.
So, now define: $a_2 = 2$ and $x_2 = 10 + 7^2a_1 = 108$. Check
that indeed $|x_2^2 - 2 |_7 =|11662|_7 = |7^3\cdot 34|_7 = 7^{-3}$.
{\bf [3~marks]}
%Previous version:
%Suppose there were such an~$x\in \Z$, and let
%$|x|_3 = 3^r$, for some $r\in \Z$.
%Then $|x^2|_3 = 3^{2r}$. Note that $|-3|_3 = |3|_3 = 3^{-1}$,
%so that $|x^2|_3 \not= |3|_3$, which means [from the general property
%for any $p$-adic valuation that, if $|a|_p \not= |b|_p$ then
%$| a + b |_p = \hbox{max}( |a|_p , |b|_p )$] that
%$ | x^2 - 3 |_3 = \hbox{max}( 3^{2r} , 3^{-1} )$. If $r<0$ then
%$3^{2r} < 3^{-1}$ and so this maximum will be~$3^{-1}$; if $r \geqslant 0$
%then $3^{2r} > 3^{-1}$ and so this maximum will be~$3^{2r}$. In either
%case, we must always have $ | x^2 - 3 |_3 \geqslant 3^{-1}$, and
%so it never happens that $ | x^2 - 3 |_3 < 3^{-2}$.~{\bf [6~marks]} 
\par\noindent {\bf (c).} We may apply the general rule from
lectures (which follows easily from Hensel's Lemma) that, if
$p\not= 2$ and $|a|_p = 1$, then $a$ is a  square in $\Q_p^*$
iff $a$ is a quadratic residue in $\F_p$. Here $p=3$. For
$a = 7$, we see that $a \equiv 1$ (mod~$3$) is a quadratic residue,
hence $7$ is a square in $\Q_3^*$. For $a=2$, we see that
$2$ is a non-residue (mod~$3$) and so $2$ is not a square
in $\Q_3^*$. For $a = 3$, imagine that $x^2 = a = 3$ for some $x\in\Q_3$;
let $ | x |_3 = 3^r$, for some $r\in\Z$. Then $ | x^2 |_3 = | 3 |_3$,
giving $3^{2r} = 3^{-1}$, a contradiction. Hence,
$3$ is not a square in $\Q_3^*$. Exactly the same argument shows
that $6$  is not a square in $\Q_3^*$. For the first equality,
$6 = 2\cdot 3$ and we have already seen that $3\not\in (\Q_3^*)^2$,
so that $ 6 \not= 2$ in $\Q_3^*/(\Q_3^*)^2$. For the second equality,
$21 = 3\cdot 7$ and we have already seen that $7 \in (\Q_3^*)^2$, 
so that $ 21 = 3$ in $\Q_3^*/(\Q_3^*)^2$. Finally, $2 = 1\cdot 2$
and we have already seen that $2\not\in (\Q_3^*)^2$, 
so that $ 2 \not= 1$ in $\Q_3^*/(\Q_3^*)^2$.~{\bf [5~marks]} 
\par
An element $\alpha \in \qts$ iff (both $| \alpha |_3 = 3^r$ for
$r$ even and the leading digit of $\alpha$ is a quadratic
residue mod~$3$) [N.B. if $| \alpha |_3 = 3^r$ for $r$ odd, then
$\alpha \not= \beta^2$ for any $\beta$, by the same argument
as used above for $3$]. Let $H_1$ be the subset of $\qts$,
consisting of such $\alpha$ (i.e. $H_1 = \{ \alpha \in \q_3^*:
| \alpha |_3 = 3^r$ for $r$ even,
and the leading digit of $\alpha$ is a quadratic
residue mod~$3\}$). Then $H_1 = \qts$ and so everything in
$H_1$ is equal to~$1$ in $\qtmods$. Let $H_2 = \{ \alpha \in \q_3^*:
| \alpha |_3 = 3^r$ for $r$ even,
and the leading digit of $\alpha$ is not a quadratic
residue mod~$3\}$; let $H_3 = \{ \alpha \in \q_3^*: 
| \alpha |_3 = 3^r$ for $r$ odd, 
and the leading digit of $\alpha$ is a quadratic 
residue mod~$3\}$; let $H_4 = \{ \alpha \in \q_3^*:  
| \alpha |_3 = 3^r$ for $r$ odd,
and the leading digit of $\alpha$ is not a quadratic  
residue mod~$3\}$. Clearly, the quotient of any two elements
in $H_2$ is in $H_1$, and so all the elements of~$H_2$
are equal to each other in $\qtmods$. The same comment
applies to $H_3$ and $H_4$. Hence there are precisely
4 distinct elements in $\qtmods$.~{\bf [4~marks]}
\medskip 
\noindent {\bf 3.} {\it Question 3 (a)
requires regurgitation of one of the easier
proofs from lectures (middle of the course).
Question~3~(b) is a variation of an example from the example sheets.
Question~3~(c) is unseen.}
\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).} Either of the following two Methods are
acceptable (Method 1 is easier). 
\par\noindent {\it Method 1.} The
discriminant of $X^3 + 9$ is~$27\cdot 9^2
= 3^7$, and so $\widetilde \e : Y^2 = X^3 + 9$ is an elliptic curve
for all $p\not= 2,3$. The elements of
$\widetilde \e (\F_5 )$ are: ${\bf o}, (0,\pm 2), (1,0), (3,\pm 1)$,
and
so $\widetilde \e (\F_5 )$ has order~6.
The elements of
$\widetilde \e (\F_7 )$ are: ${\bf o}, (0,\pm 3), (3,\pm 3), (5,\pm 1),
(6,\pm 1)$,
and
so $\widetilde \e (\F_5 )$ has order~9.
Since the torsion subgroup
of $\e (\Q)$ injects into both of these groups, its order
must divide $\hbox{gcd}(6,9) = 3$. But, there is a point of
order~3 in $\e (\Q)$, namely~$(0,3)$. Hence the torsion subgroup 
of $\e (\Q)$ is precisely~$\{ {\bf o} , (0,\pm 3) \}$.
\par\noindent {\it Method 2.} The
discriminant of $X^3 + 9$ is~$27\cdot 9^2
= 3^7$ and so, by the Nagell-Lutz Theorem, any torsion point
$(x,y)$ must satisfy $x,y\in\Z$ and $y=0$ or $y^2 | 3^7$, so the only
possibilities for $y$ are $y=0, \pm 1, \pm 3, \pm 9, \pm 27$. 
Substitution these into $y^2 = x^3 + 9$ gives, respectively,
the equations: $0 = x^3 + 9$, $1 = x^3 + 9$, $3^2 = x^3 + 9$,
$3^4 = x^3 + 9$ and $3^6 = x^3 + 9$; that is:
$x^3 = -9$, $x^3 = -8$, $x^3 = 0$, $x^3 = 72$, $x^3 = 720$.
Of these, $-9,72,720$ do not have integer cube roots, but
$-8,0$ do have integer cube roots, namely $-2,0$;
hence ${\bf o}, (0,\pm 1), (-2,\pm 1)$ are the only potential torsion
points in $\e (\Q)$. Clearly, $(0,1) + (0,1) = (0,-1)$, so that
$3(0,1) = {\bf o}$, and so ${\bf o}, (0,1), (0,-1)$ are all
torsion points. It only remains to check whether $(-2,\pm 1)$
are torsion points. To compute $(-2,1) + (-2,1)$, find the
line tangent to $\e$ at $(-2,1)$, namely: $Y = 6X + 13$, so
that the $x$-coordinate of the third point of intersection
is: $6^2 - (-2) - (-2) = 40$, with $y$-coorsinate $6\cdot 40 + 13 = 253$,
giving: $(-2,1) + (-2,1) = (20,-253)$. But $(-253)^2$ is not
a factor of $\Delta = 3^7$, and so $(20,-253) = 2(-2,1)$ cannot be a torsion
point. which means that $(-2,1)$ also cannot be a torsion point.
It follows that $(-2,-1) = -(-2,1)$ also cannot be a torsion point.
We are then left with ${\bf o}, (0,\pm 1)$ as the only torsion points.
%\par
%\hfill
{\bf [10 marks]}
\par\noindent {\bf (c).} We know that the points of order~$2$ in $\e (\Q )$,
where $\e : Y^2 = X^3 + AX + B$,
are precisely the points $(x,y) \not= {\bf o}$
such that $(x,y) = -(x,y)$, that is: $(x,y) = (x,-y)$ so that~$y=0$.
Therefore, the $x$-coordinate must be a $\Q$-rational root of the cubic
$X^3 + AX + B$, and there are at most $3$ distinct such roots.
Hence, there are at most~$3$ points of order~$2$. {\bf [5~marks]}
% Previously, this was part of the solutions:
% \par Suppose that~$P\in \e (\Q)$ is of order~$4$; then $Q = 2P$ must
% have order~$2$ [since $2Q = 4P = {\bf o}$]. Further, the kernel
% of the multiplication-by-two map consists of the $2$-torsion elements
% of which there are at most~$4$ [namely, {\bf o} and at
% most~$3$ points of order~$2$] and so the multiplication-by-two map
% is at most a $4$-to-$1$ map; therefore
% each point
% of order~$2$ can have at most~$4$ distinct points of order~$4$ which
% map to it under the multiplication-by-two map. We have
% already seen that there are at most $3$ points of order~$2$, and so
% finally there must be at most $4\cdot 3 = 12$ points of order~$4$.
% {\bf [4~marks]}
\medskip
\noindent {\bf 4.} {\it Question 4 (a),(b)
requires regurgitation of one of the harder proofs from lectures
(towards the end
of the course).
Question~4~(c) is hard,
and 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 [8 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 [8 marks]}
\par\noindent {\bf (c).} Define $\hat\phi : \d (\Q) \rightarrow \c (\Q):
(u,v) \mapsto ( {1\over 4} {v^2\over u^2} ,
{1\over 8}( v - {b_1v\over u^2}) )$. Also, define
$\hat q : \cq \rightarrow \qmods : (x,y) \mapsto x$, when $x\not= 0$
and $(0,0) \mapsto b$, ${\bf o}\mapsto 1$, which has kernel
$\hat\phi(\d (\Q))$, by the same argument as in~(b).
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$.
Suppose that $(0,0) \in 2\c (\Q)$. Then $(0,0) = 2R = \hat\phi(\phi (R))$,
for some $R\in \c (\Q)$. Hence $(0,0) \in \hat\phi ( \d (\Q))$,
so that $(0,0)$ must be in the image of~$\hat\phi$. This
means that $\hat q ((0,0)) = 1$; but $\hat q ((0,0)) = b$,
by definition, so that $b=1 \in \qmods$, which is the same
thing as saying $b\in \qss$,
as required.
% Previous version of solutions contained:
% $b=c^2$, say, where $c\in\Q$. Further, 
% since $(0,0) = \hat\phi(\phi (R))$ and $Q_1,Q_2$ are the two
% preimages of~$(0,0)$ under $\hat\phi$, we must have
% that $Q_1 = \phi (R)$ or $Q_2 = \phi (R)$; hence
% $Q_1 = (a + 2\sqrt{b},0) \in \phi (\c (\Q) )$ or 
% $Q_2 = (a - 2\sqrt{b},0) \in \phi (\c (\Q) )$;
% hence $q((a + 2\sqrt{b},0))=1$ or $q((a - 2\sqrt{b},0))=1$
% in $\qmods$, so that $a+2\sqrt{b}  \hbox{ or } a-2\sqrt{b}= 1 \in \qmods$;
% that is: $a+2c \hbox{ or } a-2c \in \qss$.
% In summary, $b=c^2$ and either $a+2c = s^2$ or $a-2c = s^2$,
% for some $c,s\in\Q$. If the former, then take $r=c$; if the latter,
% then take $r=-c$.
{\bf [9 marks]}
\medskip
\noindent {\bf 5.} {\it Parts~(a),(b) are variations of
exercise sheet questions.
Part~(c) is unseen, although
they have seen the idea of the injectivity of $v\mapsto v^3$
in another context.}
% Previously, this comment was included:
% Part~(c) is similar in spirit to part~(a),
% except that for the last bit they have to spot the trick (not seen
% before)
% of rewriting $x^2 - 2x + 6$ as $(x-1)^2 + 5$, as well as
% understanding what ``$(x,y)$~mod~5~$=(1,0)$'' implies about
% $|x|_5$, $|x-1|_5$ and $|y|_5$.
\par\noindent {\bf (a).} Reducing mod~$5$, the equation for
$\te$ is: $Y^2 = X^3+X^2$ over~$\F_5$; that is: $f(X,Y) = Y^2 - X^3 - X^2= 0$.
A point $(x,y)$ is a singularity iff it satisfies all of
$f(x,y) = 0$, $\partial f/\partial X(x,y) = 0$
and $\partial f/\partial Y(x,y) = 0$; that is:
$y^2 - x^3 - x^2 = 0$, $2y = 0$, $-3x^2 - 2x= 0$, which only
occurs when $(x,y)=(0,0)$. Therefore, $(0,0)$ is the only singularity.
The smallest-degree part of $f(X+0,Y+0)$ is $Y^2 - X^2$, which factors
as $(Y+X)\cdot (Y-X)$, so that there are two tangents
at~$(0,0)$, namely: $Y+X = 0$ (which is the same as $Y=-X$)
and $Y-X = 0$ (which is the same as $Y=X$), each
with multiplicity~1. Since the tangents are distinct, the point~$(0,0)$
is a node.
\par Imagine that $(0,0)\in \te (\F_5)$ lifts to a point
$(x,y)\in \e (\Q_5)$, so that $(x,y)$ reduces to $(0,0)$
under reduction mod~$5$. Then $x \equiv 0$ (mod~$5$)
and $y\equiv 0$ (mod~$5$), which is the same as
$|x|_5 < 1$ and $|y|_5 < 1$;
indeed $|x|_5, |y|_5 \leqslant 5^{-1}$ (since any $5$-adic
value is one of: $\ldots ..., 5^{-2}, 5^{-1}, 1, 5^1, 5^2, \ldots$,
so that if a $5$-adic value is $< 1$ then it must be $\leqslant 5^{-1}$),
so that $|x^3|_5 = |x|_5^3 \leqslant 5^{-3}$ and
$|x^2|_5 = |x|_5^2 \leqslant 5^{-2}$,
giving $|x^3 + x^2|_5 \leqslant \hbox{max}(5^{-3},5^{-2}) = 5^{-2}$.
But $|5|_5 = 5^{-1}$ and
so $|x^3 + x^2|_5 \not= |5|_5$ which means that $|x^3 + 5|_5 =
\hbox{max}(|x^3 + x^2|_5 , |5|_5) = 5^{-1}$ [from the general property
for any $p$-adic valuation that, if $|a|_p \not= |b|_p$ then
$| a + b |_p = \hbox{max}( |a|_p , |b|_p )$].
Since $x,y$ satisfy 
$y^2 = x^3 + x^2 + 5$, we must therefore have: $|y|_5^2 = 5^{-1}$,
which contradicts the fact that $|y|_5^2 = 5^{2r}$ for some
integer~$r$. Hence $(0,0)\in \te (\F_5)$ does not lift to a point
$(x,y)\in \e (\Q_5)$.~{\bf [8~marks]}
\par\noindent {\bf (b).} Reducing mod~$5$, the equation for
$\te$ is: $Y^2 = X^3$ over~$\F_5$; that is: $f(X,Y) = Y^2 - X^3 = 0$.
A point $(x,y)$ is a singularity iff it satisfies all of
$f(x,y) = 0$, $\partial f/\partial X(x,y) = 0$
and $\partial f/\partial Y(x,y) = 0$; that is:
$y^2 - x^3 = 0$, $2y = 0$, $-3x^2 = 0$, which only
occurs when $(x,y)=(0,0)$. Therefore, $(0,0)$ is the only singularity.
The smallest-degree part of $f(X+0,Y+0)$ is $Y^2$, which factors
as $Y\cdot Y$, so that there are two tangents
at~$(0,0)$, namely: $Y-0 = 0$ (which is the same as $Y=0$)
with multiplicity~2. Since the tangent is repeated, the point~$(0,0)$
is a cusp.
\par Imagine that $(0,0)\in \te (\F_5)$ lifts to a point
$(x,y)\in \e (\Q_5)$, so that $(x,y)$ reduces to $(0,0)$
under reduction mod~$5$. Then $x \equiv 0$ (mod~$5$)
and $y\equiv 0$ (mod~$5$), which is the same as
$|x|_5 < 1$ and $|y|_5 < 1$;
indeed $|x|_5, |y|_5 \leqslant 5^{-1}$ (since any $5$-adic
value is one of: $\ldots ..., 5^{-2}, 5^{-1}, 1, 5^1, 5^2, \ldots$,
so that if a $5$-adic value is $< 1$ then it must be $\leqslant 5^{-1}$),
so that $|x^3|_5 = |x|_5^3 \leqslant 5^{-3}$. But $|5|_5 = 5^{-1}$ and
so $|x^3|_5 \not= |5|_5$ which means that $|x^3 + 5|_5 =
\hbox{max}(|x^3|_5 , |5|_5) = 5^{-1}$ [from the general property
for any $p$-adic valuation that, if $|a|_p \not= |b|_p$ then
$| a + b |_p = \hbox{max}( |a|_p , |b|_p )$].
Since $x,y$ satisfy
$y^2 = x^3 + 5$, we must therefore have: $|y|_5^2 = 5^{-1}$,
which contradicts the fact that $|y|_5^2 = 5^{2r}$ for some
integer~$r$. Hence $(0,0)\in \te (\F_5)$ does not lift to a point
$(x,y)\in \e (\Q_5)$.~{\bf [8~marks]}
\par\noindent {\bf (c).} We are given that $p\equiv 2$~(mod~$3$)
and $p>5$.
Here $\te : Y^2 = X^3 + 5$, and the
discriminant of $X^3 + 5$ is $\Delta = 27\cdot 5^2$ which is not
divisible by $p$; that is: $\Delta \not= 0$ in $\F_p$ and $p\not=2$, which
means that $\te$ is non-singular. 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 (and hence bijective),
from $\F_p^*$ to $\F_p^*$. Since also $0\mapsto 0^3$, the
map $v \mapsto v^3$ must also be a bijection from $\F_p$ to $\F_p$.
Let $y$ be any member of $\F_p$; since $v \mapsto v^3$
is a bijection, there must exist exactly one $x\in\F_p$ such
that $x^3 = y^2 - 5$. Hence there are exactly $p$ affine points
$(x,y)\in \te (\F_p)$, which become $p+1$ points when
the point at infinity is included.~{\bf [9~marks]}
% \par\noindent {\bf (c).} Here $\te : Y^2 = X(X^2  - 2X + 1)
% = X(X-1)^2$; that is $f(X,Y) = Y^2 - X(X-1)^2 = 0$.
% As in (a), a point $(x,y)$ is a singularity iff
% it satisfies all of
% $f(x,y) = 0$, $\partial f/\partial X(x,y) = 0$
% and $\partial f/\partial Y(x,y) = 0$; that is:
% $y^2 - x(x-1)^2 = 0$, $2y = 0$, $(x-1)(3x-1) = 0$, which only
% occurs when $(x,y)=(1,0)$. Therefore, $(1,0)$ is the only singularity.
% The smallest-degree part of $f(X+1,Y+0)$ is $Y^2 - X^2$, which factors
% as $(Y - X)(Y + X)$, so that there are two tangents
% at~$(1,0)$, namely: $(Y-0)-(X-1) = 0$ (which is the same as $Y=X-1$)
% and $(Y-0)+(X-1) = 0$ (which is the same as $Y=-X+1$), each
% with multiplicity~1. Since the two tangents are distinct, the point~$(1,0)$
% is a node. Imagine that  $(1,0)$ lifts to a point $(x,y)\in \e(\Q_5)$,
% so that $(x,y)$ reduces (mod~$5$) to $(1,0)$. Then
% $ x \equiv 1$ (mod~$5$) and $y \equiv 0$ (mod~$5$), so that
% $| x |_5 = 1$, $| x - 1 |_5 < 1$ and $ | y |_5 < 1$;
% indeed $|x - 1|_5, |y|_5 \leqslant 5^{-1}$ (since any $5$-adic
% value is one of: $\ldots ..., 5^{-2}, 5^{-1}, 1, 5^1, 5^2, \ldots$,
% so that if a $5$-adic value is $< 1$ then it must be $\leqslant 5^{-1}$),
% so that $|(x - 1)^2|_5 \leqslant 5^{-2}$. But $|5|_5 = 5^{-1}$ and
% so $|(x-1)^2|_5 \not= |5|_5$ which means that $|(x-1)^2 + 5|_5 =
% \hbox{max}(|(x-1)^2|_5 , |5|_5) = 5^{-1}$ [from the general property
% for any $p$-adic valuation that, if $|a|_p \not= |b|_p$ then
% $| a + b |_p = \hbox{max}( |a|_p , |b|_p )$].
% Since $x,y$ satisfy
% $y^2 = x(x^2 - 2x + 6) = x((x-1)^2 + 5)$,
% we must therefore have: $|y|_5^2 = |x|_5 |(x-1)^2 + 5|_5 = 5^{-1}$,
% which contradicts the fact that $|y|_5^2 = 5^{2r}$ for some
% integer~$r$.~{\bf [8~marks]}
\medskip
%\eject
\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 + 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.
{\bf [4 marks]}
\medskip
\noindent {\bf 7.} {\it Parts (a),(b),(c) are easy variations
of a question on one of the examples sheets; this is intended
to be an easy question accessible to the weaker students, although
it is not quick to answer, since there are quite a few computations.} 
\par\noindent
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.
%In fact, by luck, every one of the following calculations
%actually requires only $8$ digits.
\par\noindent {\bf (a).} First compute (modulo $N=13333$):
$2^1 \equiv 2$, $2^2 \equiv 4$, $2^4 \equiv 16$, $2^8 \equiv 256$,
$2^{16} \equiv 12204$, $2^{32} \equiv 8006$,
$2^{64} \equiv 4305$ (where each of these
was obtained be squaring the previous one, and reducing modulo~$N$). 
Now, we write $66$ in base~2: $66 = 2 + 64$ and
so $2^{66} \equiv 2^2 2^{64} \equiv 
4\cdot 4305 \equiv
3887$ modulo~$N$, 
so that $2^{66} - 1 \equiv 3886$ modulo~$N$.
\par
Now, compute $\hbox{gcd}(3886, N)$ by Euclid's Algorithm:
$13333 = 3 \cdot 3886 + 1675$; $3886 = 2\cdot 1675 + 536$;
$1675 = 3\cdot 536 + 67$, $536 = 8\cdot 67 + 0$.
So, $67$ is a factor of $N$.
Compute $13333/67 = 199$, giving the factorisation
$N = 13333 = 67 \cdot 199$. {\bf [8~marks]} 
\par\noindent {\bf (b).} The line tangent to~$\e$ at $P=(1,1)$
has slope $y'$ given by $2yy' = 3x^2 + 9$, with $x=1,y=1$;
that is, the slope is $12/2 = 6$. This tangent line also goes
through $(1,1)$ and so has equation: $Y = 6X - 5$.
The $x$-coordinate of $2P$ is therefore $6^2 - (1+1) = 34$,
and the $y$-coordinate is: $-(6\cdot 34 - 5) = -199\equiv 13134$,
so that $Q = 2P \equiv (34 , 13134)$ (modulo~$N=13333$). 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 13134 \cdot y' = 3\cdot 34^2 + 9$,
and so we need to compute $(3\cdot 34^2 + 9) / (2\cdot 13134)$
(modulo~$N=13333$), for which the first step is to find the
inverse of $2\cdot 13134 \equiv 12935$ (modulo~$N=13333$).
Using Euclid's Algorithm: $13333 = 1\cdot 12935 + 398$;
$12935 = 32 \cdot 398 + 199$; $398 = 2\cdot 199 + 0$. So, we cannot
find the inverse of $12935$ (modulo~$N=13333$), and this
step has given us a factor~$199$ of~$N$. As before,
compute $13333/199 = 67$, giving the factorisation
$N = 13333 = 67 \cdot 199$. {\bf [9~marks]}
\par\noindent {\bf (c).}  Since $N = 67 \cdot 199$, we have
$\phi (N) = 66 \cdot 198 = 13068$. Compute the gcd of $d=5381$ and
$\phi(N)$, we see:
$13068 = 2\cdot 5381 + 2306$; $5381 = 2\cdot 2306 + 769$,
$2306 = 2\cdot 769 + 768$, $769 = 1\cdot 768 + 1$, 
so that $\hbox{gcd}(13068,5381) = 1$. Reversing the steps:
$1 = 769 - 768 = 769 - (2306 - 2\cdot 769)
= 3\cdot 769 - 2306 = 3\cdot (5381 - 2\cdot 2306) - 2306
= 3\cdot 5381 - 7\cdot 2306 = 3\cdot 5381 - 7\cdot (13068 - 2\cdot 5381)
= 17\cdot 5381 - 7\cdot 13068$.
Hence, $17$ is the inverse of
$5381$ modulo~$13068$.
The decoding operation is therefore $X \mapsto X^{17} \hbox{ mod }N$.
Computing $5894^{17} = 
(((5894^2)^2)^2)^2 \cdot 5894
\equiv 
((6771^2)^2)^2\cdot 5894
\equiv
(7587^2)^2\cdot 5894
\equiv
4008^2\cdot 5894
\equiv
11132\cdot 5894
\equiv
315$.
(modulo~$N = 13333$). Also:
$7802^{17} =
(((7802^2)^2)^2)^2 \cdot 7802
\equiv
((6059^2)^2)^2 \cdot 7802
\equiv
(5732^2)^2 \cdot 7802
\equiv
3312^2 \cdot 7802
\equiv
9618 \cdot 7802
\equiv
1512$
(modulo~$N = 13333$). The decoded
message is therefore: $0315,\, 1512$; that is: COOL. {\bf [8~marks]}
\bigskip
\hrule
\vfil\eject\end
%\bigskip
%\bigskip
%\centerline{\bf A Few General Comments
%About This Year's Exam (May 2001)} 
%\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 May 2001 exam)
%that Question~6 will be of the same type as for the 1997 and 1999 exams,
%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].
%In the 1999 exam the bookwork portions were
%Question~3(a)~[10~marks] and Question~4(a),(b)~[16~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).
%\vfil\eject\end
