0

The following question is from the book "How to Prove It: A Structured Approach" Second Edition.

Theorem 3 : There are infinitely many prime numbers.

Euclid's proof

Introduction Chapter : Exercise Question 3

The proof of Theorem 3 gives a method for finding a prime number different from any in a given list of prime numbers.

(a) Use this method to find a prime different from 2, 3, 5, and 7.

(b) Use this method to find a prime different from 2, 5, and 11.

Note: Theorem 3 is on page 4

My thoughts:

The proof shows that when there is a list of prime numbers from $p_1,p_2,...,p_n$, the next prime can be found by multiplying $p_1,p_2,...,p_n$.

(a) $2 \times 3 \times 5 \times 7 + 1 = 211$

(b) I'm not sure how to do this. They didn't give a consecutive list of primes and I found out that if the list doesn't contain consecutive primes, I can't just multiply them and add 1 to get the next prime.

Answers given

(a) The method yields the prime number 211.

(b) The method yields two primes, 3 and 37.

Faizal Ismaeel
  • 645

1 Answers1

1

Hint: The Euclid's proof of infinitude of primes can be modified to find a new prime, given $n$ different primes $p_1, p_2, \cdots, p_n$.

Using same argument as Euclid's,
Let $N = p_1p_2\cdots p_n+1$.
Since $N > 1$, either $N$ is a prime number or it is composite.
If $N$ is prime, we are done $N \neq p_1, N \neq p_2, \cdots$
If $N$ is composite, obtain prime factorization of $N$. Now, prime factors of $N$ can't contain any of the primes $p_1, p_2, \cdots, p_n$, because $N$ leaves remainder of $1$ in each case.
Thus, by finding prime factorization of $N$, we obtain primes different than $p_1, p_2, \cdots p_n$.

Note: This proof doesn't require the given primes to be consecutive.

In first example, $2\times3\times5\times7 + 1 = 211$ turns out to be a prime, so we are done.

In second example, $2\times5\times11 + 1= 111$ is not prime, since $111 = 3\times37$. Thus, it yields two primes other than 2, 5, 11 viz. $3$ and $37$.

taninamdar
  • 2,618
  • 14
  • 24