## Section 10.4 Infinitude of Primes

It is natural to ask the question

How many primes are there ?

In Table 10.2.4 we give a list of primes that comes in handy for many considerations of primes. Use it to count how many primes there are between certain numbers. You will see that as the numbers become larger there are fewer primes.

In Theorem 9.2.5 we saw that there are infinitely many natural numbers. Certainly, not every natural number is prime because there are composites, too. However, an ancient number theory result [5] asserts that there are still infinitely many primes.

### Theorem 10.4.1. Euclid's Theorem.

There are infinitely many primes.

### Proof.

Let \(\PP\) denote the set of all prime numbers. We show that for any finite subset \(Q\) of \(\PP\) there is an element in \(\PP\) that is not an element of the finite subset \(Q\text{.}\)

Let \(Q\) be a finite subset of the set \(\PP\text{.}\) Denote the elements of \(Q\) by \(p_1, p_2, \dots ,p_n\) and let \(q = p_1 \cdot p_2\cdot \ldots \cdot p_n\text{.}\)

By Theorem 4.3.7 \(q\) and \(q+1\) are coprime. So there is at least one prime number that divides \(q+1\) but does not divide \(q\text{.}\) Call that prime number \(t\text{.}\) Then \(t \not\in Q\text{.}\)

As we can find such a prime number \(t\) for every finite subset of \(\PP\text{,}\) the set \(\PP\) is infinite by Theorem 9.2.4.

In the video in Figure 10.4.2 we go through our proof of the infinitude of primes which is also called Euclid's theorem.

Read the proof of the theorem above carefully and the complete the sentences in the proof below.

### Checkpoint 10.4.3. Proof the infinitude of primes.

*Theorem 1.* Let \(b\) be a natural number. Then \(\gcd(b,b+1)=1\text{,}\) that means, \(b\) and \(b+1\) are coprime.

*Theorem 2.* Let \(B\) be a set. If for each finite subset \(S\) of \(B\) there is an element \(x\in B\) with \(x\not\in S\text{,}\) then \(B\) is infinite.

We apply the two theorems above in the proof of the next theorem. Fill in the blanks.

*Theorem 3.* There are infinitely many prime numbers.

*Proof.* Let \(\mathbb{P}\) be the set of

integers

natural numbers

prime numbers

negative integers

Let \(Q\) be a

finite subset

element

infinite subset

By Theorem 1, \(q\) and \(q+1\) are

coprime

odd

even

both prime

is equal to

divides

does not divide

is less than

is equal to

does divide

does not divide

is greater than

Because \(t\) does not divide \(q\) we have that \(t\) is

an element

a finite subset

not an element

a infinite subset

So we have shown that for any finite set of prime numbers \(Q\text{,}\) we can find another prime number that is not in the set \(Q\text{.}\) Thus, by Theorem 2, we have that \(\mathbb{P}\) is

finite

empty

not a set

infinite

There are many proofs for Theorem 10.4.1. For example a new prove was given by UNCG Professor Filip Saidak [4] in 2006.