Page 103 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

Theorem 5.3.2 (Infinitely many primes (IMP)). There are infinitely many prime numbers.

Proof of IMP: To prove the theorem, we need to show that for any n ∈ N there are at least n prime
numbers. Because this is a statement for all positive integers, we can prove the theorem by induction. The
base case is that for n =1, the set of all primes contains at least 1 prime number. Is this true? Because
2 is prime the set of all prime numbers has at least one prime number, namely the prime number 2.
This proves the base case. The next step in a proof by induction is to assume the statement is true for n,
which means that we assume there are at least n, prime numbers. To prove the theorem by induction,
we need to show that there are at least n +1 prime numbers. So, we know that there are n primes,
which we list in order from smallest to largest

p 1 =2 <p 2 =3 < ... <p n .

How can we find another prime number? There are infinitely many natural numbers, and the FTA
tells us that every natural number greater than or equal to two has a unique prime factorization: every
natural number greater than or equal to two is equal to the product of a unique set of prime numbers.
So, if we can find a natural number which is not divisible by any of these primes p 1 up to p n , then it
must be divisible by other primes, by the FTA. How do we cook up a number which is not divisible by
any of p 1 , ... , p n ? It would be a lot easier to cook up a number which is divisible by p 1 up to p n : we
can just multiply them all together,

103