   # MATH 124: FINAL EXAMINATIONDUE AT 5PM ON SUNDAY, JANUARY 13TH, 2001

William Stein

Date: Math 124 HARVARD UNIVERSITY Fall 2001

Instructions. Thoroughly justify all answers. While taking the exam, please do not discuss these problems with anyone else, and consult only those references that are explicitly mentioned on the Math 124 web page. (If you inadvertently stumble upon a solution while reading or studying for another class, e.g., Math 122, please make that clear in your solution.)

If you wish to use the result of a homework problem in the solution of one of the problems below, include your solution of that homework problem (a photocopy is acceptable). You may use any result that was proved in the lecture notes or the course textbooks, but please give a precise reference.

There are 10 problems, each worth 10 points, and problem was inspired'' by homework assignment . Problems 3, 5(ii), 6, 7, and 10 would be difficult to do without a computer; for these problems, you do not have to use PARI, though I recommend that you do.

Turning in the exam. The exam is due on Sunday, January 13th at 5pm. Some of you don't have a key to the math department, so you might not be able to go to my office (SC 515) and give me your exam. If this is the case, call me at (617)495-1790 or (617)308-0144, and I'll come downstairs and meet you at the elevator, and if that doesn't work just slide it under my door on Monday morning (but no later!!).

1.
The Fibonnaci numbers are defined as follows: and for , . Prove that for every integer , the greatest common divisor of and is .

2.
Let be an odd positive integer, and let , where is the group of integers modulo that are coprime to .
(i)
(5 points) Prove that .
(i)
(5 points) Find a formula for in terms of the number of prime factors of . [Hint: You might find the result of Problem 4 on this exam useful.]

3.
Consider the RSA cryptosystem with public key (i)
(3 points) A secret message has been encoded as the number . Encrypt the number using the above RSA cryptosystem.
(i)
(4 points) Find the decoding key ; i.e., break'' this RSA cryptosystem.
(i)
(3 points) Decrypt . [Hint: The answer won't look like total nonsense.]

4.
Let be an odd prime. Prove that is cyclic for all . (I.e., prove that there is an element of of order .)

5.
(i)
(5 points) Evaluate the infinite continued fraction .
(i)
(5 points) Determine the infinite continued fraction of .

6.
Write as a sum of two positive integer squares.

7.
Determine the structure of the group of equivalence classes of primitive positive definite binary quadratic forms of discriminant . Your answer should consist of expressed as a product of cyclic groups. [Hint: Use the functions in forms.gp from Lecture 24.]

8.
This problem describes a special case of a theorem that was originally proven by Eichler and Shimura. The modularity theorem says that a similar statement is true for every elliptic curve over .
(i)
(3 points) Let be the elliptic curve given by the equation Let be the number of points on over (don't forget the point at infinity). Calculate for (i)
(3 points) Let be the (formal) power series given by the infinite product Let be the coefficient of in , Calculate for .
(i)
(4 points) For each , compute the sum of the quantities calculated in (i) and (ii), then formulate a conjecture as to what this value should be for any prime .

9.
Let be the elliptic curve defined by the equation . For each odd prime , let be the number of points in the group of points on with coordinates in .
(i)
(5 points) For each odd prime , find .
(i)
(5 points) Make a general conjecture for the value of when , and prove your conjecture.

10.
Demonstrate how to use the elliptic curve factorization method to completely factor the integer . (You may use the isprime function of PARI to verify primality of numbers.)

11.
(Extra credit: automatic A in course, plus fame and glory) Let be the elliptic curve . Prove that , where is the second derivative of the -series associated to .   