Lecture 6
Learning Objectives
To apply division algorithm
To apply the Euclidean algorithm
Algorithms
An algorithm is a systematic procedures (instructions)
for calculation.
Algorithms are basic to computer programs. Essentially,
a program implements one or more algorithms.
Therefore, algorithmic complexity is important.
In this Lecture, we will study a few algorithms:
◦ Division algorithm
◦ Euclidean algorithm
Activity
Write a set of instructions (algorithms) to
write all the integers from 0 to 10.
Algorithm example 1
Step 1: Set 𝑥 = 0
Step 2: 𝑤𝑟𝑖𝑡𝑒 𝑥.
Step 3: 𝑥 = 𝑥 + 1
Step 4: 𝑖𝑓 𝑥 > 10, stop
Step 5: Go to Step 2
The Division Algorithm
The Division Algorithm
For any integer 𝑎, we can represent a in the form of
𝑎 = 𝑏𝑞 + 𝑟
where 0 ≤ 𝑟 < 𝑏.
a – integer
b – integer > 0
q – quotient
r – remainder
Algorithms
𝑎 = 𝑏𝑞 + 𝑟
The process of expressing a in this way is
the application of the division algorithm
Essentially this says that we can divide
one integer by another if the latter is
positive, and that we get a quotient and a
remainder
The Division Algorithm
Write the following integers in the form
of 𝑎 = 𝑏𝑞 + 𝑟
1. 𝑎 = 31, 𝑏 = 7
2. 𝑎 = 42, 𝑏 = 4
3. 𝑎 = 61, 𝑏 = 3
4. 𝑎 = 1482, 𝑏 = 57
The Division Algorithm
If a > 0, then
a
q=
b (floor of a/b)
Example: a = 31, b = 7
31 3
q = = 4 = 4.428571 = 4
7 7
◦ So a = bq + r gives 31 = 7 ∙ 4 + 3
Given a, b:
a Valid input requires a, b to be
q= r = a − bq integers and b > 0
b
The Euclidean Algorithm
Factors (or Divisors) and Multiple
Let a, b and c be integers.
Suppose that ab = c
◦ We say that c is a multiple of a and of b.
◦ Also, a and b are divisors or factors of c.
Example: (3)(5) = 15
◦ 15 is the multiple of 3 and of 5.
◦ 3 and 5 are divisors (factors) of 15.
Common Factor
Let m, n be positive integers.
A positive integer q is a common factor or common divisor of
m and n if it divides (is a divisor, or factor, of) both of them
Examples:
1. What is the common factor for 16 and 24
2. What is the common factor for 15 and 30
Common Multiple
A positive integer p is a common multiple of m and n if it is a
multiple of both of them
Examples:
1. Which of the following is the common multiple of 3 and 6?
1. 15
2. 18
3. 24
4. 27
2. Which of the following is the common multiple of 4 and 9?
1. 36
2. 54
3. 72
4. 108
Greatest Common Divisor (GCD)
Let m, n be positive integers.
The GCD (greatest common divisor) of m
and n is the greatest number which is a
common divisor of both of them
It’s also called the highest common factor
or HCF
Example 1
What is the GCD of 18 and 24?
?
gcd (18, 24) = 6
There is a systematic procedure for getting the GCD.
It’s the Euclidean algorithm.
Least Common Multiple
Given integers m and n, their least common multiple (LCM) is the
smallest number which is a multiple of them both
Examples:
1. What is the LCM of 8 and 6?
2. What is the LCM of 3 and 4?
The least common multiple of 2
mn positive integers equals their
lcm(m, n) = product divided by their greatest
gcd(m, n) common divisor
Euclidean Algorithm
We can get the gcd by using
the Euclidean algorithm.
This involves repeated
application of the division Euclidean Algorithm
algorithm: a = bq + r a = q0 b + r1
b = q1r1 + r2
When the remainder becomes r1 = q 2 r2 + r3
zero, we look back to the previous
remainder, rn+1.
This must be the gcd of a and b.
rn −1 = q n rn + rn +1
rn = q n +1rn +1
Example 2
gcd (96, 22) = ?
The last nonzero remainder was 2.
96 = 4 ∙ 22 + 8 Therefore, gcd (96, 22) = 2.
22 = 2 ∙ 8 + 6 96 22 96 22
lcm(96,22) = = = 1056
gcd(96,22) 2
8=1∙6+2
6=3∙2 No remainder
Example 2
gcd (96, 22) = ?
The last nonzero remainder was 2.
96 = 4 ∙ 22 + 8 Therefore, gcd (96, 22) = 2.
22 = 2 ∙ 8 + 6 96 22 96 22
lcm(96,22) = = = 1056
gcd(96,22) 2
8=1∙6+2
6=3∙2 No remainder
Example 3
gcd (63, 256) = ?
256 = 4 ∙ 63 + 4 The last nonzero remainder was 1.
Therefore, gcd (63, 256) = 1.
63 = 15 ∙ 4 + 3 63 256
lcm(63,256) =
gcd(63,256)
4=1∙3+1
63 256
= = 16,128
1
3=3∙1 No remainder
Example 3
gcd (63, 256) = ?
256 = 4 ∙ 63 + 4 The last nonzero remainder was 1.
Therefore, gcd (63, 256) = 1.
63 = 15 ∙ 4 + 3 63 256
lcm(63,256) =
gcd(63,256)
4=1∙3+1
63 256
= = 16,128
1
3=3∙1 No remainder
Extension to the Euclidean Algorithm
If d = gcd(m, n) then d can be expressed
as a linear combination
d = xm + yn
of m and n, where x and y are integers
To find x and y, we work back through the
steps of the Euclidean algorithm from
bottom to top
Example 4
It can be shown that gcd(22, 96) = 2:
96 = 4 ∙ 22 + 8
22 = 2 ∙ 8 + 6
8=1∙6+2
6=3∙2
Now we want to express 2 as a linear combination 2 = x(22) + y(96). We use
the second-last line to make 2 the subject of the equation:
2=8–1∙6
Next we use the third-last line to express 6 in terms of 22 and 8, substituting
this into the equation we’ve just produced:
2=8–1∙6
2 = 8 – 1 ∙ (22 – 2 ∙ 8)
2 = 8 – 1 ∙ 22 + 1 ∙ 2 ∙ 8
2 = 3 ∙ 8 – 1 ∙ 22
Example 4 (cont.)
Finally we use the fourth-last line to express 8 in terms of 96 and
22, substitution this into our most recent equation
2 = 3 ∙ 8 – 1 ∙ 22
2= 3 ∙ (96 – 4 ∙ 22) – 1 ∙ 22
2= 3 ∙ 96 – 3 ∙ 4 ∙ 22 – 1 ∙ 22
2= 3 ∙ 96 – 13 ∙ 22
x=3, y=-13
Example 5
It can be shown that the gcd of 256 and 63 equals 1:
256 = 4 ∙ 63 + 4
63 = 15 ∙ 4 + 3
4=1∙3+1
3=3∙1
Then we work upwards from the second-last line, as follows:
1=4-1∙3
1 = 4 – 1 ∙ (63 – 15 ∙ 4)
1= 4 - 1 ∙ 63 + 1 ∙ 15 ∙ 4
1 = 16 ∙ 4 – 1 ∙ 63
1 = 16 ∙ (256 – 4 ∙ 63) – 1 ∙ 63
1 = 16 ∙ 256 – 64 ∙ 63 - 1 ∙ 63
1 = 16 ∙ 256 – 65 ∙ 63
So 1 = 16 ∙ 256 – 65 ∙ 63.
The End
