Sharedwww / 168 / midterm / solutions.texOpen in CoCalc
Author: William A. Stein
1
\documentclass[11pt]{article}
2
\voffset=-0.1\textheight
3
\textheight=1.2\textheight
4
\input{macros}
5
%\newcommand{\zmod}[1]{\Z/#1\Z}
6
\newcommand{\zmod}[1]{\F_{#1}}
7
\newcommand{\answer}[1]{{Answer: \em #1}}
8
9
\title{Math 168A: MIDTERM}
10
\author{William Stein}
11
\date{\bf Due: Wednesday, Oct 26, 2005}
12
\begin{document}
13
\maketitle
14
15
\noindent{\em The problems have equal point value, and multi-part
16
problems are of the same value.
17
You may not talk to anybody about these problems. You are allowed
18
to use your notes, computer software, books, and web pages.
19
}
20
21
\section{Problems}
22
23
\begin{enumerate}
24
\item Make a conjecture about the set of primes $p$
25
such that $y^2 = x^3 + x$ has exactly $p+1$ points
26
modulo $p$.
27
You do not have to prove your conjecture.
28
You might find the following table helpful:
29
%
30
% E = EllipticCurve([1,0])
31
% t = [(p, E.Np(p)) for p in primes(100)]
32
% sage: ' & '.join([str(a) for a, _ in t])
33
% _7 = '2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 & 97'
34
%sage: ' & '.join([str(b) for _, b in t])
35
% _9 = '3 & 4 & 4 & 8 & 12 & 20 & 16 & 20 & 24 & 20 & 32 & 36 & 32 & 44 & 48 & 68 & 60 & 52 & 68 & 72 & 80 & 80 & 84 & 80 & 80'
36
%sage: '|'.join(['c' for _, b in t])
37
%_10 = 'c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c'
38
\begin{center}
39
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
40
$p$ & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 \\\hline
41
$N_p$ & 3 & 4 & 4 & 8 & 12 & 20 & 16 & 20 & 24 & 20 & 32 & 36 & 32 \\\hline
42
\end{tabular}
43
44
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
45
$p$ & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 & 97 \\\hline
46
$N_p$ &44 & 48 & 68 & 60 & 52 & 68 & 72 & 80 & 80 & 84 & 80 & 80\\\hline
47
\end{tabular}
48
\end{center}
49
50
\item The point $(1,1)$ is a solution to the equation
51
\begin{equation}\label{eqn:0}
52
3 + 2y + y^2 = x^2 + 2x + 3x^3.
53
\end{equation}
54
Find three other solutions as follows:
55
\begin{enumerate}
56
\item Multiply both sides of the equation by $9$
57
and let $X=3x$, $Y=3y$ to obtain an equation
58
of the form
59
\begin{equation}\label{eqn:1}
60
Y^2 + a_1 XY + a_3 Y = X^3 + a_2X^2 + a_4 X + a_6.
61
\end{equation}
62
\item Find the point $P$ on (\ref{eqn:1}) corresponding
63
to the point $(1,1)$ on (\ref{eqn:0}).
64
\item Use the group operation on (\ref{eqn:1}), e.g., via
65
SAGE, to compute several multiples of $P$.
66
67
\item Use the multiples of $P$ to recover points on (\ref{eqn:0}).
68
69
\end{enumerate}
70
71
72
{\em
73
Multiply both sides by $3^2$ and let $X=3x$, $Y=3y$ to obtain
74
a standard elliptic curve equation:
75
$$
76
Y^2 + 6Y= X^3 + X^2 + 6X - 27.
77
$$
78
The point $(1,1)$ above corresponds to the point
79
$(3,3)$ on this curve.
80
Use the group law to find four other points, then divide
81
each coordinate by $3$ to get solutions to the original equation.
82
\begin{verbatim}
83
sage: E = EllipticCurve([0,1,6,6,-27])
84
sage: P = E([3,3])
85
sage: P
86
_13 = (3, 3)
87
sage: 2*P
88
_14 = (57/16, -693/64)
89
sage: 3*P
90
_15 = (5371/9, 393877/27)
91
sage: -P
92
_19 = (3, -9)
93
sage: -2*P
94
_20 = (57/16, 309/64)
95
\end{verbatim}
96
For example, dividing the entries of $2P$ by $3$ gives
97
the solution $x=19/16, y=-231/64$.
98
99
\begin{verbatim}
100
sage: x = 19/16; y=-231/64
101
sage: 3 + 2*y + y^2 == x^2 + 2*x + 3*x^3
102
_26 = True
103
\end{verbatim}
104
}
105
106
\item The right triangle with rational side
107
lengths $a=24/5$, $b=35/12$, $c=337/60$ has area $7$.
108
Find another right triangle with rational side lengths
109
and area $7$ as follows (note that none of the sides
110
lengths of this second triangle are allowed to be the same
111
as the side lengths of the above triangle):
112
113
\begin{enumerate}
114
\item Find the point $P$ on $y^2 = x^3 - 49x$ corresponding
115
to the triangle $(24/5, 35/12, 337/60)$ under the bijection
116
from class (see notes from 2005-10-17).
117
118
\item Compute $Q = P+P$ using the elliptic curve group law.
119
120
\item Find the triangle corresponding to $Q$ under
121
the bijection from class.
122
123
\end{enumerate}
124
125
{\em Answer:
126
The area is $7 = (1/2)ab = (1/2) \cdot 24/5 \cdot 35/12.$
127
Using the bijections from class we see that this triangle
128
corresponds to the point $P=(-63/16, 735/64)$ on the
129
elliptic curve $y^2 = x^3 - 49x$.
130
We then compute $Q = P + P = (113569/14400, -17631503/1728000)$,
131
which corresponds to the triangle with sides
132
$(52319/40440, 566160/52319, -23058557761/2115780360)$.
133
}
134
135
136
\end{enumerate}
137
\end{document}
138
%%% Local Variables:
139
%%% mode: latex
140
%%% TeX-master: t
141
%%% End:
142