Homework Assignment 1
Due September 26, 2001

William Stein

Date: Math 124 $\quad$ HARVARD UNIVERSITY $\quad$ 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\leq 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),\quad \gcd(247,299),\quad \gcd(51,897), \quad \gcd(136,304)$$

3. Using mathematical induction to prove that
   $$1+2+3 + \cdots + n = \frac{n(n+1)}{2},$$
   then find a formula for
   $$1 - 2 + 3 - 4 + \cdots \pm n = \sum_{a=1}^{n}(-1)^{a-1} a.$$

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

5. Use the Euclidean algorithm to find integers $x,\, y\in\mathbb{Z}$ 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\times 401$.

7. 
   Write a PARI program to print ``Hello Kitty'' five times.

8. Let $f(x)\in\mathbb{Z}[x]$ be a polynomial with integer coefficients. Formulate a conjecture about when the set $\{ f(a) : a \in \mathbb{Z}$ 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. 1. Use PARI to compute
       $$\pi(2001) = \char93 \{$$    primes $$p \leq 2001\}.$$

    2. The prime number theorem predicts that $\pi(x)$ is asymptotic to $x/\log(x)$. How close is $\pi(2001)$ to $2001/\log(2001)$?