Math 124: Final Examination

Due at 5pm on Sunday, January 13th, 2001

William Stein

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 n was “inspired” by homework assignment n. 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 F_{n} are defined as follows: F_{1} = F_{2} = 1 and for n ≥ 3, F_{n} = F_{n−2} + F_{n−1}. Prove that for every integer n, the greatest common divisor of F_{n} and F_{n+1} is 1.

2. Let n be an odd positive integer, and let f(n) = ∏_{x∈(ℤ/nℤ)^{∗}} x, where (ℤ/nℤ)^{∗} is the

group of integers modulo n that are coprime to n.

(i) (5 points) Prove that f(n) ∈ {±1}.

(ii) (5 points) Find a formula for f(n) in terms of the number of prime factors of n. [Hint: You might find the result of Problem 4 on this exam useful.]

3. Consider the RSA cryptosystem with public key

(n, e) = (409333777761339043060441442265769, 254815086050320391994953910098867).

(i) (3 points) A secret message has been encoded as the number m = 12939458. Encrypt the number m using the above RSA cryptosystem.

(ii) (4 points) Find the decoding key d; i.e., “break” this RSA cryptosystem.

(iii) (3 points) Decrypt 320572443460498799159818530970246. [Hint: The answer won’t look like total nonsense.]

4. Let p be an odd prime. Prove that (ℤ/p^{n}ℤ)^{∗} is cyclic for all n ≥ 1. (I.e., prove that there is an element of (ℤ/p^{n}ℤ)^{∗} of order #(ℤ/p^{n}ℤ)^{∗}.)

5. (i) (5 points) Evaluate the infinite continued fraction [3, \overline{1, 4}].

(ii) (5 points) Determine the infinite continued fraction of (1 + \sqrt{23})/5.

6. Write m = 106215561890727905176155473 as a sum of two positive integer squares.

7. Determine the structure of the group C_{D} of equivalence classes of primitive positive definite binary quadratic forms of discriminant D = −888. Your answer should consist of C_{D} 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 E be the elliptic curve given by the equation

y^{2} = x^{3} − 4x^{2} + 16.

Let M_{p} = #E(ℤ/pℤ) be the number of points on E over ℤ/pℤ (don’t forget the point at infinity). Calculate M_{p} for p = 3, 5, 7, 13, 17, 19, 23, 29.

(ii) (3 points) Let f(q) be the (formal) power series given by the infinite product

f(q) = q ∏_{n=1}^{∞}(1 − q^{n})^{2}(1 − q^{11n})^{2} = q − 2q^{2} − q^{3} + 2q^{4} + ⋯

Let N_{n} be the coefficient of q^{n} in f(q),

f(q) = ∑_{n=1}^{∞} N_{n}q^{n}.

Calculate N_{n} for n < 30.

(iii) (4 points) For each p = 3, 5, 7, 13, 17, 19, 23, 29, compute the sum M_{p} + N_{p} of the quantities calculated in (i) and (ii), then formulate a conjecture as to what this value should be for any prime p > 29.

9. Let E be the elliptic curve defined by the equation y^{2} = x^{3} + x. For each odd prime p, let N_{p} be the number of points in the group E(ℤ/pℤ) of points on E with coordinates in ℤ/pℤ.

(i) (5 points) For each odd prime p < 30, find N_{p}.

(ii) (5 points) Make a general conjecture for the value of N_{p} when p ≡ 3 (mod 4), and prove your conjecture.

10. Demonstrate how to use the elliptic curve factorization method to completely factor the integer 124531325385603661726997. (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 E be the elliptic curve y^{2} + xy = x^{3} − x^{2} − 79x + 289. Prove that L^{(2)}(E, 1) = 0, where L^{(2)}(E, s) is the second derivative of the L-series associated to E.