Page 102 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

5.3 How many primes are there?

To answer the question “how many prime numbers are there? ” we will use the FTA together with the
following lemma.

Proposition 5.3.1 (Counting Primes Lemma (CPL)). Let a , b , and c ∈ Z . If a|b and a|(b + c), then

a|c .

Proof: By the definition of divide, there exists d ∈ Z such that b = ad , and there exists e ∈ Z such
that b + c = ae . Let’s think about these two equations:

b = ad, and b + c = ae.

To make things tidier, let’s bring all the a ’s together, which we can do by substituting ad for b in the
equation b + c = ae , so that we have

ad + c = ae.

Then, we can make things even more tidy by re-arranging the equation like this

c = ae − ad = a(e − d).

Now, let’s think about the definition of divide. We know that e ∈ Z and d ∈ Z . Is (e − d) ∈ Z ? Yes,
because Z is closed under subtraction. So, we have found (e − d) ∈ Z such that c = a(e − d). This
fits perfectly the definition of divide,

a|c.

♥

Finally, we will prove how many prime numbers there are. Would you like to guess first? Do you think
there are 100? Maybe more? Or fewer? Take a moment to think about this… When you’re ready for the
answer (and its proof), turn the page…

102