Page 94 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

5 Prime numbers: indestructible

building blocks

Prime numbers are indestructible building blocks from which all other numbers are built. This is because
every integer can be uniquely factored as the product of prime numbers. This fact is know as unique prime
factorization, and the theorem which proves this fact is called the Fundamental Theorem of Arithmetic,
which we will abbreviate FTA. To prove this theorem, we will first gather the necessary ingredients.

5.1 Ingredients in the proof of the Fundamental Theorem of Arithmetic

The next three propositions are key ingredients in the proof of the FTA.

Proposition 5.1.1 (Ingredient Proposition (IP)). Let n and a be non-zero integers. If (n, a)= 1, and

n|ab , then n|b.

Proof: To prove the proposition, we will use the Incredibly Useful Theorem to put 1 in disguise. Since
(n, a)= 1, the IUT says that there exist r and s ∈ Z such that

rn + sa =1.

So, 1 has taken on the disguise rn + sa . We want to show that n|b . On the left side of the equation
we have n , but there is no b in this equation. So, let’s multiply the whole equation by b . It becomes

rnb + sab = b.

Now, look back at the hypotheses of the theorem. We know that n|ab , which means there is c ∈ Z
such that ab = nc . We can substitute nc for ab,

rnb + snc = b.

What is our goal? To prove that n|b Let’s look carefully at the left side of the equation. We can tidy it up,

n(rb + sc)= b.

Well, what do you see? I see r , b , s and c which are all integers. That means (rb + sc) ∈ Z because
Z is closed under addition and multiplication. Therefore, we have found (rb + sc) ∈ Z such that

b = n(rb + sc)=⇒ n|b.

♥

94