   Homework Assignment 1 Due September 26, 2001

William Stein

Date: Math 124 HARVARD UNIVERSITY Fall 2001

Instructions: Please work in groups, and acknowledge those you work with in your write up. Some of the problem below, such as factor a number'' can be quickly done with a computer. Feel free to do so, unless otherwise stated.

1. Let be a prime number and and integer such that . Prove that divides the binomial coefficient You may not assume that this coefficient is a integer.

2. Compute the following gcd's using a pencil and the Euclidean algorithm: 3. Using mathematical induction to prove that then find a formula for 4. What was the most recent prime year? I.e., which of was it?

5. Use the Euclidean algorithm to find integers such that [I did not tell you how to do this; see §1.8 of Davenport's book.]

6. Factor the year that you should graduate from Harvard as a product of primes. E.g., frosh answer .

7. Write a PARI program to print Hello Kitty'' five times. 8. Let be a polynomial with integer coefficients. Formulate a conjecture about when the set and $f(a)$ is prime is infinite. Give computational evidence for your conjecture.

9. Is it easy or hard for PARI to compute the gcd of two random 2000-digit numbers?

10. Prove that there are infinitely many primes of the form .

1. Use PARI to compute primes 2. The prime number theorem predicts that is asymptotic to . How close is to ?   