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}}
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.
17You may not talk to anybody about these problems.  You are allowed
18to 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$
25such that $y^2 = x^3 + x$ has exactly $p+1$ points
26modulo $p$.
27You do not have to prove your conjecture.
28You 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}
54Find three other solutions as follows:
55\begin{enumerate}
56\item Multiply both sides of the equation by $9$
57and let $X=3x$, $Y=3y$ to obtain an equation
58of 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
63to the point $(1,1)$ on (\ref{eqn:0}).
64\item Use the group operation on (\ref{eqn:1}), e.g., via
65SAGE, 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
73Multiply both sides by $3^2$ and let $X=3x$, $Y=3y$ to obtain
74a standard elliptic curve equation:
75$$76 Y^2 + 6Y= X^3 + X^2 + 6X - 27. 77$$
78The point $(1,1)$ above corresponds to the point
79$(3,3)$ on this curve.
80Use the group law to find four other points, then divide
81each coordinate by $3$ to get solutions to the original equation.
82\begin{verbatim}
83sage: E = EllipticCurve([0,1,6,6,-27])
84sage: P = E([3,3])
85sage: P
86_13 = (3, 3)
87sage: 2*P
88_14 = (57/16, -693/64)
89sage: 3*P
90_15 = (5371/9, 393877/27)
91sage: -P
92_19 = (3, -9)
93sage: -2*P
94_20 = (57/16, 309/64)
95\end{verbatim}
96For example, dividing the entries of $2P$ by $3$ gives
97the solution $x=19/16, y=-231/64$.
98
99\begin{verbatim}
100sage: x = 19/16; y=-231/64
101sage: 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
107lengths $a=24/5$, $b=35/12$, $c=337/60$ has area $7$.
108Find another right triangle with rational side lengths
109and area $7$ as follows (note that none of the sides
110lengths of this second triangle are allowed to be the same
111as the side lengths of the above triangle):
112
113\begin{enumerate}
114\item  Find the point $P$ on $y^2 = x^3 - 49x$ corresponding
115to the triangle $(24/5, 35/12, 337/60)$ under the bijection
116from 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
121the bijection from class.
122
123\end{enumerate}
124
126The  area is $7 = (1/2)ab = (1/2) \cdot 24/5 \cdot 35/12.$
127Using the  bijections from class we see that this triangle
128corresponds to the point $P=(-63/16, 735/64)$ on the
129elliptic curve $y^2 = x^3 - 49x$.
130We then compute $Q = P + P = (113569/14400, -17631503/1728000)$,
131which 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