Theorem 10.22. Euclid’s Theorem.
There are infinitely many primes.
Section 10.4 Infinitude of Primes
It is natural to ask the question
How many primes are there ?
In Figure 10.8 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.22 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.
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.22 \(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.21.
In the video in Figure 10.23 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.24. 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
of the set \(\mathbb{P}\text{.}\) Denote the elements of \(Q\) by \(p_1,p_2,...,p_n\) and let \(q=p_1\cdot p_2\cdot \dots\cdot p_n\text{.}\)
By Theorem 1, \(q\) and \(q+1\) are
- coprime
- odd
- even
- both prime
. So there is at least one prime number that
- is equal to
- divides
- does not divide
- is less than
\(q+1\) but
- is equal to
- does divide
- does not divide
- is greater than
\(q\text{.}\) Let’s call this prime number \(t\text{.}\)
Because \(t\) does not divide \(q\) we have that \(t\) is
- an element
- a finite subset
- not an element
- a infinite subset
of \(Q\text{.}\)
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.22. For example a new prove was given by UNCG Professor Filip Saidak [4] in 2006.
