next up previous
Next: About this document ...

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

    $\displaystyle \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:

    $\displaystyle \gcd(15,35),\quad
\gcd(51,897), \quad

  3. Using mathematical induction to prove that

    $\displaystyle 1+2+3 + \cdots + n = \frac{n(n+1)}{2},$

    then find a formula for

    $\displaystyle 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

    $\displaystyle 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. \includegraphics[width=7em]{hkcomp.eps}

  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$.

    1. Use PARI to compute

      $\displaystyle \pi(2001) = \char93 \{$    primes $\displaystyle 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)$?

next up previous
Next: About this document ...
William A Stein 2001-10-11