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.15   Let $N=20$. step 1:

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

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

$$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.16   Using the Sieve of Eratosthenes, find all the primes from $1$ to $50$.

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

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

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

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

Exercise 1.5.21   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.22 (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.23   Assume $z$ is a real number greater than $1$. Let

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

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

$$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.24   Using the fundamental theorem of arithmetic, prove (1), (2), (3), and (4) of Proposition 1.2.16.

Exercise 1.5.25   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$.)