Homework Assignment 1 Due September 26, 2001

William Stein

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 p be a prime number and r and integer such that 1 ≤ r < p. Prove that p divides the binomial coefficient

\frac{p!}{r!(p − r)!}.

You may not assume that this coefficient is a integer.

2. Compute the following gcd’s using a pencil and the Euclidean algorithm:

gcd(15, 35), gcd(247, 299), gcd(51, 897), gcd(136, 304)

3. Using mathematical induction to prove that

1 + 2 + 3 + ⋯ + n = \frac{n(n + 1)}{2},

then find a formula for

1 − 2 + 3 − 4 + ⋯ ± n = ∑_{a=1}^{n}(−1)^{a−1}a.

4. What was the most recent prime year? I.e., which of 2001, 2000, … was it?

5. Use the Euclidean algorithm to find integers x, y ∈ ℤ such that

2261x + 1275y = 17.

[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 2005 = 5 × 401.

7. Write a PARI program to print “Hello Kitty” five times.

8. Let f(x) ∈ ℤ[x] be a polynomial with integer coefficients. Formulate a conjecture about when the set {f(a) : a ∈ ℤ 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 6x − 1.

11. (a) Use PARI to compute

π(2001) = #{ primes p ≤ 2001}.

(b) The prime number theorem predicts that π(x) is asymptotic to x/ log(x). How close is π(2001) to 2001/ log(2001)?