We saw a lot of different statements about primes today, so much so that you might be feeling a bit overwhelmed. For reference, here is a list of the properties we actually proved:

  • An integer $n>1$ is composite if and only if it has a prime divisor $p\leq \sqrt{n}$.
  • There are infinitely many primes.
  • If $p_1,p_2,p_3,\ldots, p_n, p_{n+1}$ are the first $n+1$ primes, then $p_{n+1}\leq p_1p_2p_3\cdots p_n+1$.

Here are some facts we saw that are true, but which we did not prove ourselves:

  • [Bonse] The last inequality above can be improved to $p_{n+1}\leq \sqrt{p_1p_2p_3\cdots p_n}$.
  • [Bertrand-Tchebycheff] For every integer $n\geq 2$, there is always a prime between $n$ and $2n$.
  • There is an upper bound $p_n < 2^n$ for every $n\geq 2$.

We also saw how to find primes using the so-called Sieve of Eratosthenes. This is illustrated nicely in the animation above (credit due to the unknown creator).

Tomorrow we will finish our initial survey of the primes, listing some of the more fascinating theorems and conjectures about the prime numbers (and answering many of the questions posed at the end of today’s class).