Page 68 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Remark 4.1.2 It might help you to remember how to write “a divides b” as a|b if you notice that the

line divides a and b. If a|b , then a is a divisor of b. Why is b =0? If we let b =0, then every integer
would divide b because if c =0, then for every a ∈ Z ,

b =0 = a ∗ 0.

You have already learned this concept but it probably was not presented in this way. If a|b, that means
that b = ac , and c is an integer. You would say “a goes into b, c times.” What are some examples?
2|4, because 4= 2 ∗ 2, so in this example a =2, b =4 and c =2. You would say “2 goes into 4,
2 times.” Another example is 3|(−6), because −6= 3 ∗ (−2), so in this example a =3, b = −6

and c = −2.

Exercise: Does −6|3? Make up your own examples until you are fluent with the concept a|b.

We can get warmed up to the definition of divide by proving the following proposition.

Proposition 4.1.3 The multiplicative identity divides all integers.

Proof: Let x ∈ Z . Then,

x =1 ∗ x,

so 1|x because, in the definition of divide, 1= a , x = b and x = c ∈ Z .

♥

Definition 4.1.4. A number x ∈ N , x> 1, is prime if the only natural numbers that divide x are 1
and x. A number x ∈ N , x> 1, which is not prime is composite.

Remark 4.1.5 The mutliplicative identity 1 is not prime because it already has an important and unique
role to play: the multiplicative identity is the unique natural number which divides all integers.

To prove that a natural number x is prime, we must prove that the only natural numbers which divide
x are 1 and x . Is 23979 prime? What about 199924893048329? It is not easy to prove that a very
large number is prime! Since primality is based on division, to understand prime numbers, we need to
understand division. Let’s start by proving a basic fact about division.

Proposition 4.1.6. Let a, b, c ∈ Z with a =0,b =0, and assume a|b and b|c. Then a|c.

68