Download THE NUMBER SYSTEM

Unit 1 The Number System
Solution:
a
6
7 47
42
5
q = 6 and r = 5
∴ 47 = 7 (6) + 5
b
c
37
3 111
9
21
21
0
0
8 5
0
5
q = 0 and r = 5
∴ 5 = 8 (0) + 5.
q = 37 and r = 0
∴ 111 = 3 (37) + 0
Exercise 1.13
For each of the following pairs of numbers, let a be the first number of the pair and b
the second number. Find q and r for each pair such that a = b × q + r, where 0 ≤ r < b:
B
a
72, 11
b
16, 9
c
11, 18
d
106, 13
e
176, 21
f
25, 39
The Euclidean algorithm
ACTIVITY 1.20
Given two numbers 60 and 36
1
Find GCF (60, 36).
2
Divide 60 by 36 and find the GCF of 36 and the remainder.
3
Divide 36 by the remainder you got in Step 2. Then, find the GCF of the two
remainders, that is, the remainder you got in Step 2 and the one you got in step 3.
4
Compare the three GCFs you got.
5
Generalize your results.
The above Activity leads you to another method for finding the GCF of two numbers,
which is called Euclidean algorithm. We state this algorithm as a theorem.
Theorem 1.5
Euclidean algorithm
If a, b, q and r are positive integers such that
a = q × b + r, then, GCF (a, b) = GCF (b, r).
57