Page 104 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

n

x = p 1 ∗ p 2 ∗ ... ∗ p n = p i .
i=1

But, we’re looking for a number which is not divisible by any of p 1 ,...,p n . What is a natural number
which is not divisible by any prime?

Hint: There is only one such natural number.

That’s right, the number is one. So, we can find a number which is divisible by all of the primes from p 1
up to p n , and we can find a number which is not divisible by any prime. So, what about

x +1?

Now you will see why we worked so hard to understand division by proving propositions and lemmas.
The CPL says that if some number a|b , and a|(b + c), then a|c . We know that each of p 1 up to p n
divides x , and the proposition tells us that if one of these primes also divides x +1 then it must divide 1.

Exercise: In the CPL, which roles do x , 1 and p i play?

Since no prime divides 1, but all of p 1 up to p n divide x , the CPL proves that none of p 1 up to p n
divide x +1. Therefore, the prime factorization of x +1 must consist of other primes. So, the set of all

prime numbers contains p 1 up to p n which makes n elements, but it must also contain other primes,
so it must contain at least n+1 elements. By induction and the definition of an infinite set, we have now
proven that there are infinitely many primes.

♥

Remark 5.3.3 Here’s a math joke: how do you prove there are infinitely many composite numbers? By
contradiction: assume there are not, then multiply them all together and do not add one!

We know there are infinitely many primes, but there are also infinitely many natural numbers, and they
are not all prime. How many of the natural numbers are prime?

5.4 Counting infinity

We have proven that there are infinitely many prime numbers. But, the definition of infinity is the size
of any infinite set. The set of prime numbers is infinite, but so is the set of all natural numbers. Since
the natural numbers are contained in the set of integers, there are infinitely many integers, and similarly,
there are infinitely many rational numbers. We will see that these sets of numbers are all countable.

104