Sieve of Eratosthenes

The key fact that is used for the method discussed in this section is the fact that if $ n$ is any composite than it must have a prime factor which is less than or equal to $ \sqrt{n}$, by Lemma 1.2.5.

The method to produce all primes up to $ N>2$:

  1. List all integers $ 2,...,N$.
  2. Let $ a=2$.
  3. Cross out all multiples of $ a$ except for $ a$ itself.
  4. If all integers between $ a$ and $ N$ are crossed out then stop. Otherwise, replace $ a$ by then next largest integer which has not been crossed out. If this new $ a$ is greater than $ \sqrt{N}$ then stop.
  5. Go to step 3.

This process must terminate after at most $ \sqrt{N}$ steps.

Example 1.5.12   Let $ N=20$. step 1:

$\displaystyle 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 $

step 2: Cross out multiples of $ 2$:

$\displaystyle 2,3,\not 4,5,\not 6,7,\not 8,9,\not 10,11,\not 12,13, \not 14,15,\not 16,17,\not 18,19,\not 20 $

step 3: Cross out multiples of $ 3$:

$\displaystyle 2,3,\not 4,5,\not 6,7,\not 8,\not 9,\not 10,11,\not 12,13, \not 14,\not 15,\not 16,17,\not 18,19,\not 20 $

All the remaining numbers are prime.

Exercise 1.5.13   Using the Sieve of Eratosthenes, find all the primes from $ 1$ to $ 50$.

Exercise 1.5.14   How many digits does $ 2^{6972593}-1$ have? (Hint: What is $ \log_{10}(2^{6972593})$?)

Exercise 1.5.15   Check that $ n=6$ and $ n=28$ are perfect.

Exercise 1.5.16   Determine the prime decomposition of (a) $ 111$, (b) $ 1111$, (c) $ 1234$.

Exercise 1.5.17   Show that if $ 2^n-1$ is a prime, for some integer $ n$, then $ n$ is also a prime.

Exercise 1.5.18   In the notation of §1.5.1, compute $ b_k(p)$ for

(a) $ p=7$, $ 1\leq k\leq p$,

(b) $ p=11$, $ 1\leq k\leq p$,

(c) $ p=13$, $ 1\leq k\leq p$.

Exercise 1.5.19 (a)   Assume some encryption scheme requires a $ 100$ digit prime. It is unlikely you will find a such a prime on your first guess. Approximately how many $ 100$ digit integers would have to be randomly picked before a prime is found?

(b) Estimate how many 100-digit prime numbers there are.

Exercise 1.5.20   Assume $ z$ is a real number greater than $ 1$. Let

$\displaystyle \zeta(z)=\sum_{n=1}^\infty n^{-z} =1+2^{-z}+3^{-z}+...\ , $

denote the Riemann zeta function. Here the sum runs over all integers $ n\geq 1$. Let

$\displaystyle P(z)=\prod_{p\ {\rm prime}} (1-p^{-z})^{-1}= (1-2^{z})^{-1}(1-3^{-z})^{-1}(1-5^{-z})^{-1}...\ , $

denote the Euler product. Here the product runs over all prime numbers $ p\geq 2$. Without worrying about convergence issues (using calculus, one can show that these series considered here all converge absolutely), show that $ \zeta(z)=P(z)$. In other words, show

$\displaystyle 1+2^{-z}+3^{-z}+4^{-z}+5^{-z}+... =(1-2^{z})^{-1}(1-3^{-z})^{-1}(1-5^{-z})^{-1}(1-7^{-z})^{-1}...\ . $

(Hint: Recall $ 1/(1-x)=1+x+x^2+x^3+...$ and use the Fundamental Theorem of Arithmetic.)

Exercise 1.5.21   Using the fundamental theorem of arithmetic, prove (1), (2), (3), and (4) of Proposition 1.2.16.

Exercise 1.5.22   Show that if $ 2^p-1$ is a prime then $ p$ must also be a prime. (Hint: $ 2^{ab}-1=(2^a)^b-1$ is divisible by $ 2^a-1$.)


David Joyner 2007-09-03