Page 67 - 'Blast_Into_Math
P. 67
Blast into Math! The Euclidean algorithm: a computational recipe
4 The Euclidean algorithm: a
computational recipe
In both mathematics and modern computing prime numbers play a leading role, because they are the
fundamental building blocks for all integers. Prime numbers are distinguished by their divisors. In this
chapter, we will use the propositions, lemmas, and theorems we proved in the last chapter to prove new
propositions, lemmas, and theorems about division. Then in the next chapter we will use these to prove
the Fundamental Theorem of Arithmetic, which means that you can write any integer as the product of
a unique set of prime numbers. This fact is called unique prime factorization.
4.1 Division
Definition 4.1.1. Let a, b ∈ Z , and b =0. Then we say that a divides b and write a|b if there is c ∈ Z
such that
b = ac.
67
