# Math 124: Virtual Office Hours

This is a list of questions that students have asked me, along with my responses. If you have a question, send email to [email protected].

• Question: Will you be hanging out in your office all day tomorrow? Where should I hand this in, if I come by in the early afternoon?
Answer: Yes, but with "all day" replaced by "all afternoon". Just stop by my office and give it to me. If I'm temporarily out of my office, you could also put it in my mail box on the third floor. I would suggest slipping it under my door, but I just discovered that this is nearly impossible to do without destroying the object being slipped in the process.

• Question: another question: should problem 1 read "for every *positive* integer n"? (i.e. do we have to prove it for negative n?)
Answer: Replace "integer" by "natural number".

• Question: 1. There are some things on the text version of the final that do not show up in the PDF version. For example, in question one of the text version, there is a question, "Show that $p$, $p+2$, and $p+4$ can not all be prime except when $p=3$." This does not appear in the PDF version. Do you intend for it to be part of the question? Please clarify.
Answer: Ignore that. The % at the beginning of the line means that that line is commented out. I considered making that a problem and rejected it. I should have simply deleted it from the text file.

• Question: if we wish to use pari code we wrote for a homework problem on the final, do we have to do anything special about citing or documenting it, or is it ok just to include a printout?
Answer: Include a printout, and make clear to what problem the printout pertains.

• Question: I'm having a bit of difficulty with 9(ii) and on the website you said: No special tools, beyond a clever elementary trick and possibly a little quadratic reciprocity. Might you be able to give us a clue as to what sort of "clever elementary trick" this is?
Answer: Unfortunately I can't, e.g., because some people have already turned in the exam. I wish you the very best of luck.

• Question: Can I name a Lemma after myself?
Answer: Sure, but it is "bad form", in the sense of Captain Hook.

• Question: Do we need any special tool for Problem 9 (ii)? We did a similar one in a problem set for the case x^3+1, but this one looks much harder.
Answer: No special tools, beyond a clever elementary trick and possibly a little quadratic reciprocity.

• Question: you mention on the exam that we should use PARI for particular problems, but can we also use PARI for problems you don't specifically mention. I'm thinking of using the "ellap" function on 8 and 9; can I do this, or must I calculate the points manually?
Answer: Yes, you can use ellap to compute the number of points in problems 8 and 9. You don't have to do the computation manually.

• Question: For #8(iii), the question, I feel, is a little vague. Exactly what are we supposed to say about what the value should be? Should it follow a regular pattern? Should it be even or odd? Could you give us a hint like you did for 3(iii)?
Answer: Sorry, but you will have to come up with the best answer you can based on the question I asked.

• Question: Is there a reason we are ignoring p = 11?
Answer: 11 divides the discriminant, and I was unclear about the definition of "the number of points" when p divides the discriminant.

• Question: Do we need to prove the formula in 2(ii)?
Answer: YES!

• Question: Do we need to prove our conjecture in 8(iii)?
Answer: Definitely not.

• Question: For #8, part ii on the Math 124 final, would you like us to write an explicit formula for N_n, or just to calculate the 29 values from n=1 to n=29?
Answer: Just calculate the 29 values from n = 1 to n = 29.

• Question: For #3 (iii), are we supposed to decrypt into a word or sentence, or just into a number?
Answer: Just into a number.

• Question: I just wanted to make sure I understand correctly the requirements for problem #2, part ii). Basically, we need to determine when f(n) is +1 and -1 based on the number of prime factors of n, correct? We don't need to determine a formula for f(n) as an integer in Z, right?
Answer: Correct. You need to determine when f(n) is +1 or -1 based only on the number of prime factors of n. You definitely do not need to find a formula for f(n) as an integer in Z. It's really only an integer modulo n.

• Question: I downloaded the forms, and tried to open it in PARI (on my Mac). When I type: \r forms.gp, it says:
***unexpected chracter: ...,return(b)=0));return(1);}{reduce(f)=local(D,


Answer: The program is fine; however, the file forms.gp is a UNIX text file, and UNIX text files use a different character to denote newlines than Macs. Also, your Mac browser is saving the file directly as a binary file, hence not doing the conversions necessary if it were a text file. One solution is to open the file in your browser, then copy the text of the file to a local file in, e.g., MS Word, which you should then save as a text file (with carriage returns). Now load that text file into PARI.

• Question: And in #10 could you perhaps clarify what you mean by "Demonstrate" ? I mean, I could certainly just run the ECM algorithm on that number and get an answer, but I'm sure you would want something more then that, an explanation of how it works perhaps?
Answer: Go through all of the steps necessary to *completely* factor that number, doing the nontrivial factorizations at each step using ECM. Explain what you are doing and what is going on. You don't have to prove anything here, just demonstrate that you really understand how this specific application of ECM works. You do not have to write an essay on the ECM.

• Question: In 8(i) when I tried to initialize the curve Mod 13 it didn't work:
? E13=ellinit([0,0,0,-4,16]*Mod(1,13))
***   singular curve in ellinit.

I was just wondering if that is part of what we are supposed to do for the problem, or if it is a mistake.

Answer: You are making a mistake here (that's all I can say).

• Question: Help! I can't paste programs into PARI on my Mac.
Answer: I finally had access to a Mac tonight. I tried pasting a single number into Mac PARI and this worked fine. Then I tried pasting a few pages into PARI, and this froze PARI, which should probably be considered a bug in PARI. A better way to insert pages of code into PARI is to use the "\r filename.gp" command. I just downloaded a file, e.g., forms.gp to the Mac, and copied the PARI executable to the same place as the file forms.gp. I then ran that PARI and typed "\r forms.gp" to load the forms.gp code.

• Question: In part (ii) of number 5 you ask us to determine the infinite continued fraction for a number. My question is, does "determine" mean that I can use PARI and get the obvious pattern (which I can then prove works), or do I have to show how to derive it myself?
Answer: The easier of the two, i.e., determine means that you can use PARI and get the obvious pattern, and then prove it works.

• Question: The instructions refer to specific problems on which you recommend we use PARI. Is it okay to use PARI on other problems?
Answer: Yes, certainly.

• Question: Quick question...what is a "square-free" number? A number whose prime factorization does not consist of any squares?
Answer: A number n is square free if there is no prime p such that p^2 divides n. Thus a square-free number is a product of distinct primes, e.g., 30=2*3*5 is square free, but 40=2^3*5 is not square free.

• Question: Also, out of curiosity, will you compute the homework score as (sum of numerators)/(sum of denominators) or as an average of ten numbers between zero and one?
Answer: I will view the fractional grades as numbers between 0 and 1, drop the two lowest, and average the result.

• Question: When's the take-home final?!
Answer: It turns out that it is "illegal" for me to give a take-home final that is due after January 13. Thus I will make the final available on the web on January 8th and email all of you letting you know that it is available. The final will be due by 5pm on January 13th. I won't give an extra review session in January because I get back on January 8, but feel free to ask me questions via email, etc., up until January 8th.

• Question: I also had a general question about elliptic curves: In most fields of modern mathematics it seems that we are interested not only in the objects but also in the maps between objects. (I.e. Sets and Maps, Groups and Homomorphisms, Topological Spaces and Continuous Functions, etc.) My question is, is there any sense in the idea of trying to create "maps" between two different elliptic curves. I know that elliptic curves are functions in their own right, but I was just wondering if such a thing had been thought of, or if it is of any interest.
Answer: Good question. I omitted several very basic ideas when discussing elliptic curves because of lack of time, and because I wanted to talk about the BSD conjecture. Let E and F be elliptic curves. A homomorphism from E to F is a map phi defined by polynomial functions that respects the group law (i.e., induces a homomorphism from E(C) to F(C)). One has a notion of isomorphism, kernel, etc. It turns out that a homomorphism from E to F is either the 0 map or is surjective. When phi : E-->F is nonzero, it is called an ISOGENY. An example is E=F and phi = multiplication by 2. The two deepest theorems I know about isogenies are as follows. First, Mazur proved that if E is an elliptic curve over Q and phi : E --> F is an isogeny of Q with kernel of prime order p, then p <= 163. Second, Faltings proved that if two elliptic curves E and F over Q have the same L-series, L(E,s) = L(F,s), then there exists an isogeny phi : E--> F, i.e., "E and F are isogenous". Also, the conjectural algorithms for computing the group of points on E make essential use of certain isogenies.

• Question: I had a rather random thought the other day, and thought I'd ask you about it. Has it been established that there are a finite or infinite number of numbers which are the sum of their factors ("Perfect Numbers" like 6 and 28). It's probably not important to mathematics at all, but I was wondering if anyone had taken the time to find out.
Answer: My understanding is that one can show that every even perfect number is of the form 2^(n-1)*(2^n - 1), where 2^n - 1 is a (Mersenne) prime, and, conversely, if 2^n - 1 is a (Mersenne) prime, then 2^(n-1)*(2^n - 1) is a perfect number. Thus the perfect even numbers are in bijection with the Mersenne primes. I think it is conjectured that there are infinitely many Mersenne primes, hence infinitely many even perfect numbers. However, as you recently pointed out to me, only 39 Mersenne primes are known.

• Question: And finally: why isn't it possible to paste PARI programs from the lecure notes on the website directly into PARI to use them? if I do that, nothing works and I can't even go on typing in PARI (these may be stupid questions but they've been puzzling me for quite a while).
Answer: I don't know. You have to give me more information before I can hope to answer the question. Which computer system? How do you past, and from which file to which file? Perhaps you could try saving the PARI program in a file and reading that file into PARI using the "\r" command.
? \r filename.gp


• Question: Also, I was wondering if perhaps you could put answer keys to the homework assignments on your website so we can work through the homework again over break;
Answer: However, several students in the course have typed up excellent solutions. I'll write one of them and ask if their solutions can be made available. Solutions for assignments 1,4,5,6,7, and 9 are now posted.

• Question: I have been having problems printing out lecture notes and homework assigments from your website. It used to work but now it always says that an "internal error" occured when I try to print out a pdf file. Am I doing anything wrong?
Answer: I don't know. I haven't changed anything. Perhaps you should obtain a program for viewing or printing PS files, such as the free program "ghostview", or try printing from one of the computer labs in the Science Center (and ask at the help desk).

• Question: I was wondering if - and hoping that - there might be some way for me not to have my math final within these few days, especially as I would like to concentrate on it completely. Please let me know if that's possible.
Answer: It might be. What would be the optimal time for you? January 6-9? January 16-19?

• Question: What's an "order of vanishing"?
Answer: A C^{oo} function f vanishes at a point z0 to order r if and only if
   f(z0) = f'(z0) = ... = f(r-1)(z0) = 0

but
   f(r)(z0) =/= 0.

Thus its first r derivates (the 0th through (r-1)st) vanish at z0, but the r-th derivative does not.

• Question: Also, for our examples for 1-3, can we use small numbers?
Answer: Yes, if you want.

• Question: Do we have all the machinery we need to prove the Fermat's Last THeorem Question?
Answer: You had it after only a few weeks in Math 124. E.g., one possible solution involves Fermat's little theorem.

• Question: Regarding the homework, define "interesting". I.e., can we just illustrate the implementation of each of the methods?
Answer: Curt McMullen defined "interesting" in his seminar talk this Tuesday. He said: "Interesting means... you know, interesting!" Then he said that interesting means there is something we don't yet understand. If you want a real definition, here is the one in the OED: "Adapted to excite interest; having the qualities which rouse curiosity, engage attention, or appeal to the emotions; of interest."

• Question:
Is Doud's algorithm not guaranteed to compute the full torsion group?  I
> am puzzled by the following behavior:
>
> ? e=ellinit([0,0,0,-10846856157922827,434814147916401568208454]);
> ? elltors(e)
> %2 = [6, , [[59485323, 8627776560]]]
> ? for(i=1,6, print(ellpow(e,[59485323,8627776560],i)))
> [59485323, 8627776560]
> [60777003, 8689777200]
> [-120260022, 0]
> [60777003, -8689777200]
> [59485323, -8627776560]
> 
> ? ellisoncurve(e,[60091419,0])
> %3 = 1
> ? ellpow(e,[60091419,0],2)
> %4 = 
>
> So [60091419, 0] is in the torsion group, but not in the cyclic
> group generated by [59485323, 8627776560].


Answer:
Yes, Doud's algorithm should give the full torsion subgroup.
Evidently Doud's algorithm as implemented in PARI requires the curve
to be in "minimal form", and it doesn't change the form to be minimal
for you.  Behold:

? e=ellinit([0,0,0,-10846856157922827,434814147916401568208454]);
? elltors(e)
%2 = [6, , [[59485323, 8627776560]]]
? f=ellglobalred(e)
%3 = [2676208470, [6, 3, 3, 0], 62208]
? ee=ellchangecurve(e,f)
%4 = [1, 0, 0, -8369487776175, 9319575518172005625, 1, -16738975552350,
37278302072688022500, -70048316315967228725625000, 401735413256401,
-8052113850303732744601, 46367070089839400992758295329000000,
64836617580550319021577618714177184806649201/46367070089839400992758295329000000,
[1671349.999999999999999999999, 1669205.999999999999999999999,
-3340556.250000000000000000000]~, 0.004703740756481346451602644899,
0.001403443255552375980283896400*I, 1689.788153472741998765595537,
-163.7145638235014246650611570*I, 0.000006601433240550576622182616090]
? elltors(ee)
%5 = [12, [6, 2], [[2307180, 1512439725], [1669206, -834603]]]

The MathSciNet review of Doud's paper:

Doud, Darrin(1-IL)

A procedure to calculate torsion of elliptic curves over
$Q$. (English. English summary)
Manuscripta Math. 95 (1998), no. 4, 463--469.

The author gives an algorithm for computing the rational torsion
subgroups of an elliptic curve using the standard Weierstrass analytic
parametrization. The Lutz-Nagell algorithm is particularly simple, but
involves testing a potentially large number of cubic equations for
integral roots, as well as necessitating factorization of the
discriminant of the curve. This latter calculation can be a stumbling
block when the coefficients of the curve become large. The current
algorithm is very attractive, with most of its run time computing
values of the $\wp$ function. The author has made available the
algorithm in GP-PARI code, and gives several examples of computations
where the results are demonstrably superior to current torsion
programs.

• Question: By the way, for part a of that question, do we need to compute products of cyclic groups, etc., to describe them? It's just tedious, and we've done it already on previous homeworks.
Answer: You can just give their orders. :-)

• Question: In Homework 9, Problem 2, when I ask PARI to find the torsion subgroup of the original curve or a modified one with integer coefficients, it cannot do it with Lutz-Nagell even after several stack overflows. However, it finds the torsion subgroup quickly with Doud's algorithm. Should this be a cause of concern if I try to do the problem with Lutz-Nagell?
Answer: Good point. Lutz-Nagell requires checking over 50000 y-coordinates, because there are over 50000 divisors of the square root of the discriminant! I've rewritten the problem as follows:

(6 points) Many number theorists, such as myself one week ago, incorrectly think that Lutz-Nagell works well in practice. Describe the steps you {\em would} take if you were to use the Lutz-Nagell theorem (Lecture 27) to compute the torsion subgroup of the elliptic curve E defined by the equation

y^2 +xy = x^3 -8369487776175x + 9319575518172005625,

then tell me why it would be very time consuming to actually carry these steps out. Find the torsion subgroup of E using the elltors command in PARI. Does {\tt elltors} use the Lutz-Nagell algorithm by default?

• Question: For #2 on HW 9, when I transform the curve into "standard" form, I get non-integral coefficients, which means I don't meet the conditions for Nagel-Lutz. What do I do in that case?
Answer: Make them integral! It's always possible to make them integral. Just multiply both sides of your equation by a sixth power, and absorb the appropriate factor in x and y.

• Question: I was wondering what Mazur's theorem says when we are dealing with elliptic curves over finite fields.
Answer: Nothing. His theorem only applies to elliptic curves over the rational numbers Q.

• Question: Still with #3 on HW 8...I think that the only way to have P+Q be the group is to have E(Q) isomorphic to Z/2Z or Z/2Z X Z/2Z. Someone suggested that it was (Z/2Z)^k for any k. I'm having trouble seeing what that's true...if you have more than 4 points (1 at infinty), doesn't identity fail?
Answer: By, e.g., Mazur, if E(Q) = (Z/2Z)^k for some k, then E(Q) is isomorphic to {0}, Z/2Z or Z/2Z X Z/2Z. There is also a simple proof of this fact, using the complex torus stuff I mentioned today.

• Question: I know that it might be a little premature to ask about grading, but I was wondering if it might be possible to drop part of the midterm grade instead of dropping the two lowest homework assignments. I ask because I have been doing very well on all of the homework assignments, ...
Answer: I can't really do this, because I would have to do the same for everyone and that would amount to changing the grading system that I stated on the syllabus (=contract). However, as always, I reserve the right to adjust anybody's letter grade up when I'm assigning grades in January. At that time, I might decide to give lower weight to midterm scores of students who have done exceptionally well on the homeworks or final exam. In any case, if you were to get 90% of the points in the course (e.g., 20/40 on midterm, perfect homework, perfect take-home final), then you would get an A in the course no matter what.

• Question: Suppose that I am one of your students, and I did not come to any lectures. As the exam approaches, I want to know roughly what you did, and therefore print the hand-outs. Is there a way to do this without going through 30+ web pages?
Answer: Not at present. Each lecture is in a separate LaTeX file. I intend to put everything together into a single BOOK when the semester ends.

• Question: Also, for ps#8, I have been having some trouble with #1...I tried plugging in X = c*x + d and Y = e*x + f*y + g into Y^2=X^3+a*X+b to match up with y^2+x*y+y=x^3, but ended up with 7 equations in 5 unknowns that didn't work out. Am I approaching this correctly?
Answer:
Here is a hint.   Start with the equation y^2 + xy + y = x^3.  Think
of it as a quadratic equation with unknown y:

y^2 + (x+1)y - x^3 = 0

Now use the quadratic formula to write

y =  (-b + sqrt(b^2-4ac))/2a.

Then 2a*y + b = sqrt(b^2 - 4ac), so if we set Y = 2*a*y + b, we have

Y^2 = b^2 - 4ac = a cubic polynomial in x,

and you are well on your way!


• Question: Do you have an idea when our Math 124 take-home final will be due?
Answer: It will be due sometime between Jan 14 and Jan 23, 2002. Also, despite what I might have suggested in class, I won't assign the takehome final until reading week (Jan 2, 2002), at the earliest.

• Question: For #1, I set X=a*x+b and Y=c*y+d*x+e for some choice of a,b,c,d, and e. This yields an answer in the correct form, but I am unsure of whether this is a "linear change of variables."
Is it? :-)

Answer: Yes.

• Question: I think there may be an error on the homework...in Question 5, part (i), I think there should be a beta out front, not an alpha. I've attached my work so you can check to make sure...
Answer: I think that you can modify your proof slightly to get an alpha out front instead of a beta. Both statements are true; you have a lot of flexibility in choosing k.

• Question: In E(Q), you care about when your points are rational---those are the elements that form a group. In E(R), anything goes, right? In E(Z/pZ), you care about when your points are elements of the field Z/pZ, no?
Answer: Everything you said seems basically right, though it's not mathematically precise enough for me to give it my gold stamp. Let me just say that
    E(K) = { (x,y) in K x K :  y^2 = x^3 + ax + b }.


• Question: I was thinking...if you take the curve you gave on Lecture 26...y^2=x^3+1, and place your "point at infinity" off to the left somewhere, every line you draw from that "point" through any other rational point will intersect the curve exactly once. Does this indeed give us an abelian group where every element has order 2?
Answer: I suspect that your point at infinity to the left does not lie on the elliptic curve. Also, those lines that you're drawing do intersect the curve in three points, it's just that you can't see the other two points (they are complex -- try to find them).
I only ask this because, for the binary operation question, MUST we assume that the only possible candidate for an identity element is a point at infinity? And, if so, can the point be not "above" the curve, but to the "left" or "right" of it?
You could single out any point at all ON THE CURVE and declare that to be your identity element. The result would be a group that is isomorphic as an abstract group to the usual group.

• Question: I was looking at the Homework 9, and it looks pretty hefty. Also, there is a big Math 122 midterm on the Wednesday that it is due. Moreover, since it's the Thanksgiving Holiday, could you maybe lighten it a bit? Just thought I'd ask...
Answer: Wow. Actually I was just beginning to make Homework 9, and those problems you saw were only the first few that came to mind. I had big plans to assign even more! What to do you think of the following? I assign just those five problems, but I assign them on Monday (instead of Wednesday). They aren't as hard as they might look, and you already know enough from my lectures so far to answer all of them.

• Question: How would you incorporate an eps file in a latex document, i.e., what command would you use?
Answer: The following example works for me, with the file picture.eps in the current directory. If this doesn't work for you, then something is wrong that relates to your specific setup or where your files are located is causing a problem, and I can't easily help you with that.
   \documentclass{article}
\usepackage{graphicx}
\begin{document}
This works for me!\\
\includegraphics{picture}
\end{document}

For more information, check out epslatex.ps or l2e-grfguide.dvi.

• Question: Thanks for the help. One last question: for #2, would you like us to hand draw the graphs, or is a printout from, say, Maple sufficient?
Answer: A printout is sufficient.

• Question: I'm a bit fuzzy on how you want us to represent the structure of the class group CD, if it is not cyclic, as a product of cyclic groups... can you give some guidance please?
Answer: For any positive integer n, let Z/nZ denote the additive group of integers modulo n, so Z/nZ is a cylic group of order n. I want you to give a group of the form Z/nZ x Z/mZ x ... for various integers n, m, ..., that is isomorphic to CD. (The integers n, m,... are not uniquely determined.) For example, if CD has order 4, then the two possible answers are Z/2Z x Z/2Z and Z/4Z.

• Question: In order to help myself out with problem #1 on the HW set I wrote a little function to compute the order of one of these forms. I figure it might be something nice to include in a next version of forms.gp. The function looks like this:
{orderform(a, iden)=
local(product, order);
order = 1;
product = a;
if (a == iden, return(order), order++);
while(order > 0,
if ((product = composition(a, product)) == iden,
return(order), order++);
)
}


• Question: In problem 1 I can't compute
   composition([4,3,15],[2,-1,29])

(these two come up when computing the reduced forms for D = -231). Is there some problem with the PARI code or maybe my computer hasn't enough power?

Answer:
Yes, there was a bug.  If you didn't already find it yourself, change
line 15 of forms.gp from

if(c < a,

to

if(c < a || (c==a && b< 0),

I've changed the version of forms.gp available at

http://modular.math.washington.edu/edu/Fall2001/124/lectures/lecture24/

Second, it takes about 10 minutes to compute the reduced forms of
discriminants -12104 and -10015.  For those of you who are either
impatient or have with slow computers, I've included the reduced forms
of those two discriminants at the end of this email.  You could paste
this list into PARI and work with it.

Reduced forms of discriminant -12104:
[[1, 0, 3026], [10, -4, 303], [10, 4, 303], [13, -8, 234], [13, 8,
234], [15, -14, 205], [15, -4, 202], [15, 14, 205], [15, 4, 202], [17,
0, 178], [18, -8, 169], [18, 8, 169], [2, 0, 1513], [25, -14, 123],
[25, 14, 123], [26, -8, 117], [26, 8, 117], [27, -10, 113], [27, 10,
113], [3, -2, 1009], [3, 2, 1009], [30,-16, 103], [30, -4, 101], [30,
16, 103], [30, 4, 101], [34, 0, 89], [39, -34, 85], [39, -8, 78], [39,
34, 85], [39, 8, 78], [41, -14, 75], [41, 14, 75], [45, -26, 71], [45,
-44, 78], [45, 26, 71], [45, 44, 78], [5, -4, 606], [5, 4, 606], [50,
-36, 67], [50, 36, 67], [51, -34, 65], [51, 34, 65], [54, -44, 65],
[54, 44, 65], [6, -4, 505], [6, 4, 505], [9, -8, 338], [9, 8, 338]]

Reduced forms of discriminant -10015:
[[1, 1, 2504], [10, -5, 251], [10, 5, 251], [14, -11, 181], [14, -3,
179], [14, 11, 181], [14, 3, 179], [16, -15, 160], [16, 15, 160], [17,
-7, 148], [17, 7, 148], [19, -13, 134], [19, 13, 134], [2, -1, 1252],
[2, 1, 1252], [20, -15, 128], [20, 15, 128], [23, -17, 112], [23, 17,
112], [28, -17, 92], [28, -25, 95], [28, 17, 92], [28, 25, 95], [32,
-15, 80], [32, 15, 80], [34, -27, 79], [34, -7, 74], [34, 27, 79],
[34, 7, 74], [35, -25, 76], [35, 25, 76], [37, -7, 68], [37, 7, 68],
[38, -13, 67], [38, -25, 70], [38, 13, 67], [38, 25, 70], [4, -1,
626], [4, 1, 626], [40, -15, 64], [40, 15, 64], [43, -41, 68], [43,
41, 68], [46, -17, 56], [46, -29, 59], [46, 17, 56], [46, 29, 59],
[49, -31, 56], [49, 31, 56], [5, 5, 502], [7, -3, 358], [7, 3, 358],
[8, -1, 313], [8, 1, 313]]


• (Updated)
Question: I had a quick question regarding assignment 7: In problem 3, you say that (3,5) is a solution to y3-x2=2, however, 25-27=-2. IS it a typo on the HW?
Answer: Thanks! The equation should be
y2 - x3 = -2.

• Question: Let us say that I have defined the variable x to be something or another in PARI. If I later want to use x just as a formal variable is there a way to "clear x" or something of that nature?
Answer: Yes, use the "kill" command:
? x=5
%1 = 5
? kill(x)
? x
%2 = x
? x^2
%3 = x^2


• Question: If only I knew what a nested for loop was! :) In all seriousness, professor...am I going to have to be able to do this stuff on the final exam? If so, I'm probably in big trouble...I really have absoultely NO idea how to program.
Answer: You'll probably have to use PARI some on the final exam. Here is an example use of a "nested for loop":
? {for(x=1,3,
?    for(y=1,2,
?     p  print("x^2 + y^2 = ", x^2+y^2)
?    )
? )}
x^2 + y^2 = 2
x^2 + y^2 = 5
x^2 + y^2 = 5
x^2 + y^2 = 8
x^2 + y^2 = 10
x^2 + y^2 = 13

-- William

• Question: Also, as you know, I'm PARI-programming illiterate. How should I go about writing the four-square program?
Answer: Just use a nested for loop. Here's a hint:
for(x=0, something,    for(y=0,something, etc.
if(x^2 + y^2 + z^2 + w^2 == number,
print out x, y, z, and w.


• Question: I was wondering if you could offer any advice as to how to approach #8 and 9. I remember in lecture, when asked how to derive the g such that f|g = x2+y2, you said that you just came up with the example by first finding g and then finding f. How should we go about showing the equivalence of two forms in #8 and #9? Do we need to find specific g's?
Answer: I will answer this in my lecture on Monday. There, I describe a reduction process that relates any form to a simpler equivalent "reduced" form. If two forms are equivalent, then the corresponding reduced forms are equal. It is possible to recover the matrix that connects that form to its reduced form, so this process can be used to solve problems 8 and 9.

• Question: For #3, I'm really baffled. My argument so far is something like this: if x, x+1, x+2, and x+3 are all ...
Answer: Hint: If n is a sum of two squares, what are the possibilities for n mod 4?

• Question: For #6, I can get 8n^2 and 8n^2+2 pretty easily. I can't seem to get 8n^2+1. Any help there?
Answer: The 8n^2+1 case amounts to showing that for any integer a, the number
    f(a) = 2a^2(a+1)^2+1 = 2a^4 + 4a^3 + 2a^2 + 1

is a sum of two squares. I stared at this for a few minutes and didn't see an obvious reason. Then I wrote a tiny program to list sums of two squares of quadratic polynomials with small coefficients and looked to see whether or not 2x^4 + 4x^3 + 2x^2 + 1 appeared in the list. It does.

• Question: For #3, if a number is representable as the sum of two integer squares, isn't it directly obvious that it is representable as the sum of two rational squares? (I mean, all integers are rational numbers.) Or did you want more from that question. Moreover, to prove it, I used the argument that if ab was equal to the sum of two squares, and that if b was also equal to the sum of two squares, then a must be equal to the sum of two squares. Is that right, or did I miss something?
Answer: Yes, one direction is obvious. The crux of the question is to prove that if n is an integer and n = (a/b)^2 + (c/d)^2, then there are integers r and s such that n = r^2 + s^2. You could prove this as you suggest, by proving the following statement: if xy is a sum of two squares and y is a sum of two squares, then x is also a sum of two squares. You definitely *do* have to prove that statement.

• Question: With the help of the lecture today I managed to get #9 on the problem set. I've been working at #10 but I can't manage to finagle it into anything I think I can use. Might you have any hints?
Answer: This is a hint, so it will be necessarily vague. Start with
  x^2 + (x+1)^2 = z^2.

Multiply out and rearrange terms and do a little algebra to get
  2x^2 + 2x + 1 - z^2 = 0

Now complete the square to make the above expression look something like
    2*X^2 - Z^2 = -1/2

for some X and Y. Now do a little more algebra to get something like Z^2 - 2X^2 = 2, which you know how to deal with.

• Question: Do we need to explain why contfrac(e^2) exhibits the pattern that it does in problem 8 or can we just explain the pattern? I'm not as of yet able to deduce why it follows this pattern given contfrac(e).
Answer: You can just exhibit the pattern. You don't have to explain why it does. (In fact, I don't know how to deduce that it does from the continued fraction of e.)

• Question: To say "correct to 4 decimal places," doesn't it mean that you want the the difference to be less than 0.00001? This always confuses me. I figure that the 0's mean that they are set.
Answer: I want four digits of the decimal expansion of the answer to be correct. If you give > four your answer will still be correct. I would consider the number 2.236111111... to be the same as sqrt(5) = 2.23606797... to four decimal places of accuracy. This is all a matter of convention of course, and to decide whether I'm right or wrong one must take a poll. Here's a random example of the usage of this phrase from the internet: (From http://astronomy.swin.edu.au/pbourke/analysis/pi/) you'll find
  "22/7 is correct to 3 decimal places"

In fact,
  pi = 3.1415926... and 22/7 = 3.1428571...

so this author agrees with my usage.

• Question: I was wondering if #9 and #10 on this problem set are related to continued fractions? If so, might you be able to give me a hint as to how?
Answer: I'll tell you all about it in my lecture tomorrow. In the meantime, you should feel free to read the notes for tomorrow's lecture. There should be enough there for you to be able to solve #9 and #10.

• Question: (2) For homework 5, problem #6(ii) and #7, you said we could play around with PARI. However, > is there any theory or insight that we are supposed to invoke?
Answer: For #6(ii), you could use, e.g., that I proved in lecture two that
   |x - c_n| < 1/(q_n*q_{n+1}) <= 1/(n*(n+1))

to find an n such that

|sqrt(5) - c_n| < 10^(-3).

Then compute cn. In practice, you'll probably get an even better approximation. For problem 7, just compute.

• Question: (1) For problem #4 on homework 5, must everything be in lowest terms??
Answer: Your answer should be of the form a + b*sqrt(d), where d is a squarefree integer and a and b are elements of the rational numbers expressed in lowest terms.

• Question: I think there is a typo in the homework 5. For problem #2, in the hint, shouldn't it read:
     pn                  pn-2
----- =   an   + ----------
pn-1                pn-1


Answer: Yes, you're right. I fixed this on the web page.

• Question: What happens if, when you use the quadratic formula to find a continued fraction's value, you get TWO positive answers? (EX. See number 4 (i) (of homework 5), which is [\overline{2,3}])
Answer:

In exercise 4 (i), there is only one positive root. The two roots of 3*x2-6*x-2 are approximately 2.29099444873 and -0.29099444873, so only one is positive. The first is the value of the continued fraction.

However, to answer your question, you can decide which root is correct by computing the first few partial convergents of the continued fraction and seeing which root they converge to. It will quickly be clear that one of the two roots is out of the question.

• Question: This may just be a minor point, but in number two of the current homework you say let cn = pn/qn. Then cn is never used in the problem? Is it supposed to be somewhere?
Answer: Thanks for asking. You are right. The problem should say "If pn/qn is the th convergent of the continued fraction..."; that is, there is no reason for me to give the name cn to pn/qn in the problem.

• Question: I want to do well in this course, and by "well" I mean understand everything. Given the nature of academia, exams, etc., I'm not sure if I walked away from the first half of the course knowing what I should know. If you could offer your professional opinion on that, I'd appreciate. That way, I can fix stuff before its too late.
Answer: These are very difficult questions. My initial thought is to recall that I initially improved at mathematics by solving as many problems as I could. I used to plow through books with lots of relatively do-able problems and solve every single one of them. You could try this, in addition to the work you do for your courses. For example, you could do all of the easier Davenport problems for the relevant sections. In the long run, I did not learn how to do research mathematics by doing problems in books; learning to do research came later, and was something I was only able to learn with the guidance of people such as Ribet, Lenstra, Mazur, and Coleman. However, I would have never had the chance to learn how to do research if I had not spent a great deal of time solving tons and tons of problems in books.

• Question: For #4 on the homework, you said told me that there must exist an element of order p-1 in the group Z/p^2Z. Why is this true? We proved that there is an element of order p-1 in the group Z/pZ. I'm not clear on why you can make the extension.
Answer: If a has order p-1 modulo p, then a has order divisible by p-1 mod p^2. The only possible orders of elements mod p^2 are 1, divisors of p-1, p*(divisors of p-1). So a has order either p-1 or p*(p-1). In the latter case you are done. In the former, use your element of order p to make an element of order p*(p-1).

• Question: What's a good PARI program to compute the number of primes less than x such that 2 is a primitive root modulo p?
Answer: You might modify the program I gave in the notes for computing pi(x). You can decide whether or not a number is a primitive root using the command znorder:
  znorder(Mod(a,p)) == p-1

if and only if a is a primitive root modulo p.

• Question: In your hint for question 4 (of homework 4) you say to look for an element of order p. I'm not really sure how this will help me because in order to prove that there is a primitive root mod p^2 I would need to look for elements of (Z/p^2 Z)* of order phi(p^2) and phi(p^2) != p.
Answer:
       phi(p^2) = p^2 - p = p*(p-1).

If you can find an element of order p, and another of order (p-1), then their product will have order phi(p^2).

• Question: I'm having trouble wrapping my brain aroudn the forward implication of the corollary---i.e., if x^2 == a mod p has no solutions, then a^{thingy} == -1 mod p. Can you explain it in more detail?
Answer: Certainly a^{(p-1)/2} =/= 1 (mod p). Do you see that? If not, let me know. If so, we just have to show that the only possibilities for a^{(p-1)/2} are 1 and -1. This is true, because a^{(p-1)/2} (mod p) is a root of the polynomial x^2-1 (mod p), whose only roots are +1 and -1.

• Question: Perhaps these questions about primitive roots will clear things up.
Answer:
> (1) KTH POWER RESIDUES
> When we say that a number "a" is a kth power residue mod p, we mean that a
> == x^k mod p.  Now, do we make the distinction that x is in the set
> {1,2,3,...,p-1}?  Or, might x be greater than any of these numbers?  (And,
> if x is indeed greater, will it always be the case that x^k is congruent to
> one of numbers in the set raised to the kth power--that is, we can simply
> replace x^k by y^k, y in {1,2,3,...,p-1}?--This is, I think, related to the
> earlier question, your proof of which still confuses me.)

It doesn't matter whether or not x is in the set {1,2,3,...,p-1}.
Suppose x is any integer and a == x^k (mod p).  Let r be such that
x = c*p + r with 0 < r < p.  Then a == r^k (mod p).  This is because,
if x == r (mod p), then x^k == r^k (mod p).  Very explicitly, if
p | x - r, then p | x^k - r^k = (x-r)(x^(k-1)+...+r^(k-1)).

> (2) PAGE 66: "Half the numbers 1,2,...,p-1 are quadratic residues and the
> other half are quadratic non-residues.  The quadratic residues are
> congruent to the numbers 1^2, 2^2, ... , [1/2(p-1)]^2."  HUH???????
> WHY???????  And why do we stop at [1/2(p-1)]^2

First, we stop at [1/2(p-1)]^2, because the number between [1/2(p-1)]
and p-1 are congruent to the _negatives_ of the numbers between 1 and
[1/2(p-1)]^2, and a^2 = (-a)^2.  The numbers 1^2, 2^2, ... (mod p) are
the quadratic residues because the quadratic residues are, by definition,
exactly the set of distinct squares modulo p.

> And, I'm probably bound to stop by tomorrow for more.

Please do.

> Incidentally, the question on the 122 homework was to prove that in Fp, the
> set of all x^2, with x in Fp, is a group--is this the same thing as showing
> that all quadratic resiudes are a group?

I assume you mean "prove that the set of all _nonzero_ x^2 in F_p is a group",
since it's not a group without the nonzero condition.  And yes, this is the
same as showing that the set of all quadratic resiudes are a group.

> (If so, how do I know that I'm
> not leaving any out by just squaring and reducing each element of Fp)

If a number is a square, then it's the square of something.  As discussed
in question (1) above, that something can be taken < p.


• Question:

In Lecture 11 you write:

Remark 2.4 There are \phi(n) primitive roots modulo ..., since there are ... ways to choose ...

It is not very clear to me why differenct choices of a_i lead to different generators.
Answer: I just added a proof of this to the remark. You can either try to read the remark in this email, or view the new version of lecture 11.

There are $\vphi(p-1)$ primitive roots modulo~$p$, since there are
$q_i^{n_i} - q_i^{n_i-1}$ ways to choose $a_i$.  To see this, we check
that two distinct choices of sequence $a_1,\ldots, a_r$ define two
different primitive roots.  Suppose that
$$a_1 a_2 \cdots a_r = a'_1 a'_2 \cdots a'_r,$$
with $a_i$, $a'_i$ of order $q_i^{n_i}$, for $i=1,\ldots,r$.
Upon raising both sides of this equality to the power
$s = q_2^{n_2}\cdots q_r^{n_r}$, we see that
$a_1^s = a_1'^s$.  Since $\gcd(s,q_1^{n_1})=1$,
there exists~$t$ such that $st\con1\pmod{q_1^{n_1}}$.
It follows that
$$a_1 = (a_1^s)^t = (a_1'^s)^t = a'_1.$$
Upon canceling $a_1$ from both sides, we see that $a_2 \cdots a_r = a'_2 \cdots a'_r$; by repeating the above argument, we see that $a_i = a'_i$ for all~$i$.  Thus, different choices of the $a_i$ must lead to
different primitive roots; in other words, if the primitive roots are the
same, then the $a_i$ were the same.


• Question: You defined primitive root in lecture 11 as: A primitive root modulo p is an element of (Z/pZ)^* of order p-1. For non-prime modulos, do we extend this to: A primitive root modulo n is an element of (Z/nZ)^* of order \phi(n)? (Problem three asks about primitive roots modulo 2^n.)
Answer: Yes, you are exactly right! A primitive root mod n is a generator for the group (Z/nZ)^*, or, what is the same, an element of (Z/nZ)^* of order phi(n).

• Question: I have been working on some other stuff with consecutive primes and squares and I need to write the output of the program to a file.
Answer: Here are two options. First, you can use the \l command to log everything, both input and output, to a file. You can also use the write command to write exactly what you want to a file:
? ?write
write(filename,a): write the string expression a (same output as print) to
filename.

? for(n=1,7,write("testfile", n!,"\t",n))


• Question: I've been toying around with the proof of (n-1)! == 0 mod n. I figure that every distinct prime factor of n must occur in the product (n-1)!. However, I'm stuck on proving that all the powers of the prime factors of n must occur there. Do you see any ways to get around that? Am I on a right track?
Answer: You are on the right track. The following is meant as a hint, so it is intentionally un-crystal-clear. Suppose p^2 | n. Then, p < n, so, as you observed, p | (n-1)!. Since p^2 | n, we see that
p, 2*p, 3*p, ..., (p-1)*p < n
as well. Thus you get lots of copies of p that divide (n-1)!.
• Question: If I ever see your door open in the Math Department, am I permitted to knock on your door and ask a question? Or, should I save everything for email and office hours.
Answer: Yes, you can knock or drop in. Don't worry, if I am in the middle of something important I will tell you, and we can make an appointment for another more convenient time. I might also say, "we can talk for 20 minutes right now, but not more."

• Question: This is probably a really silly question, but the following statement is not clear to me:
If p|a and p|b, then p|gcd(a,b).
Could you furnish a quick proof for me?

Answer: Good question. Here's a proof. Let me know if you have any questions about it. Write a = p*a' and b=p*b'. Then by the proposition that I stated in class (the proof uses Euclid's algorithm), we have
gcd(a,b) = gcd(p*a',p*b') = gcd(a',b')*p,
which is divisible by p.

• Question: I was hoping you could clarify something for me, if you have your Davenport with you... On page 19, he makes the following statement in the proof of unique factorization: "Since p and p' are not the same, one at least of these two inequalities must be true with strict inequality, and it follows that pp' < n." I'm having trouble understanding why.
Answer: My first impression is that Davenports conclusion is correct, but the argument he gives is murky. Here's why his conclusion is correct. I assume that you see that p^2 <= n, (p')^2 <= n, and that p=/=p'. If p is less than p', then p*p' < (p')^2 <= n, and if p' is less than p, then p*p' < p^2 <= n, so in both cases p*p' < n.

• Question: Do you prefer William or Prof. Stein or Dr. Stein?
Answer: In an academic context, I prefer to be called what students at Harvard typically address the professors who teach their courses. I haven't been here long enough to be sure what is typical, but my initial observations suggest that "Professor LastName" is the most usual form of address.

• Question: I was told today that for two numbers a and b,
ab=gcd(a,b)lcm(a,b)
How does one go about proving this?

Answer: I'll give you some hints to get you started. First, try the case when a and b are both powers of a single prime, so a = p^r and b = p^s. Then the statement is equivalent to the assertion that
r+s = min{r,s} + max{r,s},
which is true.

• Question: I spoke with my adviser who recommended that I find out from you exactly which ideas from Math 122 (which I plan on taking this fall) I would need for 124, when I would need them, when 122 teaches them, etc. Like I said, your course sounds fabulous, and I'm psyched about elliptic curves; on the other hand, I don't want to get in over my head (I'm more of a math tortoise than a math hare), especially since I'm also CAing this term, which will require a lot of my time. The sophistication of the material seems to indicate that you're gearing it towards a more advanced group.
Answer: The textbook by Davenport does not require anything specifically from 122, though background from 122 would be helpful. Let me elaborate on what this means. After a few lectures, we will study the integers modulo N. If you know a few basic facts about groups, then it will be MUCH easier to understand what is going on. For the elliptic curves part of the course, you will certainly need to know what a group is, but you won't have to know very much about them. In summary, there will be finitely generated abelian groups hidden everywhere in this course, so the ideas will fit together more cleanly in your mind if you have experience with the abstract notion of finitely generated abelian group. However, knowing, e.g., the Sylow theorems, is certainly not necessary for 124; moreover, seeing many examples of groups "in nature" will probably make it easier for you to understand abstract groups. Historically, I think that many of the main ideas I'll teach in 124 were developed before the notion of abstract group had fully crystallized in the mathematical consciousness.

• Question: I've ran into this problem before. Is there a way to get more primes without doing something technical like recompiling the Pari source code? Which I couldn't do anyway since I have the windows version. Recompiling isn't possible for windows is it?
Answer: Use the -p option:
[[email protected] people]\$ gp -p1000000

• Question: Yes! "19th cent. number theorists rocked!" I'll read them more in depth later after I get through playing with the sopf function. I also like browsing through your notes from the conferences even though I don't understand very much of it. Weird huh?
Answer: It's counterintuitive, but not weird, in the sense that most mathematicians browse through notes or articles about things they don't understand well at some point. The canonical analogy is that if you want to learn a foreign language, then it's certainly *not* weird to try to hear it spoke fluently even if you hardly understand anything that is said. If you wanted to learn French, most people probably wouldn't think you're really weird if you went to a movie that was in French, even if you were a beginner.

• Question: Hey! I was hoping you could give me a little guidance. I am unclear, because the tutorial does not contain a "Programming" section (it says it has yet to be written), how to write a program to print HELLO KITTY 5 times.
Answer: Just do something like
for(i=1,5, printing stuff here )
That's it. By program, I just mean a line or two of PARI code.

• Question: Also, when I tried to do the gcd of two random 2000 digit numbers, I typed in gcd(1.23*10^1999,4.3322111*10^1999), and it keeps telling me that these numbers are not integers! Argh! What do I do?
Answer: To a computer, those are not integers but non-exact floating point approximations. Get rid of the decimal points. This line in PARI will create a reasonbly random roughly 2000 digit number:
a = sum(i=0,200,10^(10*i)*random(2^30))

• Question: For the experimentation with polynomials, can we pick one particular type of polynomial to examine? For example, I've been looking solely at polynomials of the form x^n+1, n in Z, and have found some cool results!!
Answer: You should try to make a general conjecture. However, after you do that, it's a great idea to look at specific families of polynomials and discover cool results. Have fun!

• Question: Congruent fractions...I see examples of where a fraction is congruent to something modulo n. Can you give me an example of where a fraction is not congruent to something modulo n? Also, if I get this whole thing, then I can say that if 2 CONG 8 mod 6, then 2/5 CONG 8/5 mod 6, which implies that 6 divides the difference between 2/5 and 8/5, which it does not...what's going on here?
Answer: The definition of congruence that I gave in class assumes that a, b, and n are all integers. It does not apply if they are not integers, like in your example. I think the correct generalization for rational numbers a and b is:
a is congruent to b modulo n if n divides the NUMERATOR of a - b.
(The numerator is the numerator when the fraction is written in lowest terms.) Thus, e.g., 2/5 - 8/5 = 6/5 has numerator divisible by 6. However, 5/6-1/6 = 2/3, and 6 does not divide 2, so 5/6 is NOT congruent to 1/6 modulo 6.

• Question: On page 46, he speaks about x^{p-1} CONG 1 mod p, where p is a prime. And, he makes the assertion that the order of any number is a divisor of p-1. Why?
Answer: Suppse x is an integer with gcd(x,p)=1. Let == mean "congruent modulo", so if i is the order of x, then x^i == 1. Since x^(p-1)==1 and i is the minimum of all a such that x^a==1, we see that i <= p-1. Using the Euclidean algorithm, write
                      p-1 = q*i + r

with 0<=r x^(p-1) == x^(q*i) * x^r. Since x^i == 1 and x^(p-1) == 1, it follows that x^r == 1. Since i is the smallest positive integer so that x^i == 1 and r < i, it follows that r = 0, which proves that i divides p - 1, as claimed. > Also, Leibniz's proof (on the same page) is a bit > confusing...could you expand a bit on what's going on here? He's using that x = 1 + ... + 1, so that
  x^p = (1 + ... + 1)^p ==

1^p + ... + 1^p + (bunch of other stuff divisible by p),

This is the same as saying that x^p = x (mod p). The key step is to show that the bunch of other stuff is divisible by p, and that follows from a binomial-theorem like formula for
          (x_1 + x_2 + ... + x_n)^p.