THE EUCLIDEAN ALGORITHM
finds the greatest common divisor of the integers a and b by repeated division.
LEMMA 1: Let a =bq + r,
where a,b,q, and r are integers. Then
gcd(a,b) = gcd(b,r).
Proof: If we can show that the common divisors
of a and b are the same as the common divisor of b and r, we will have shown
that gcd(a,b) = gcd(b,r), since both pairs must have the same greatest divisor.
So suppose that d divides
both a and b. Then it follows that d
also divides a – bq = r (from Theorem1 of 2.3). Hence, any common divisor of a and b is also a common divisor of
b and r. Likewise, suppose that d
divides both b and r. Then d also
divides bq + r = a. Hence, any common
divisor of b and r is also a common divisor of a and b.
Consequently, gcd(a,b) =
gcd(b.r).
EXAMPLE 1: Find the greatest common divisor of 168
and 90.
168 = 90 x 1 + 78
90 = 78 x 1 + 12
78 = 12 x 6 + 6
12 = 6 x 2 + 0
gcd(168, 90) = 6.
ALGORITHM 1:
THE EUCLIDEAN ALGORITHM
procedure gcd(a, b:
positive integers)
x := a
y := b
while y ¹ 0
begin
r := x mod y
x := y
y := r
end{gcd(a,b) is x}
In this algorithm, the
initial values of x and y are a and b, respectively. At each stage of the procedure, x is replaced by y, and y is
replaced by x mod y, which is the remainder when x is divided by y. This process is repeated as long as y ¹ 0. The algorithm terminates when y = 0, and the
value of x at that point, the last nonzero remainder in the procedure, is the
greatest common divisor of a and b.
THEOREM
1: Let b be a positive integer greater than
1. then if n is a positive integer, it
can be expressed uniquely in the form
n =
akbk + ak-1bk-1 + … + a1b
+ a0,
where
k is a nonnegative integer, a0, a1,…,ak are
nonnegative integers less than b, and ak ¹ 0. This representation is called the base b
expansion of n.
EXAMPLE
2: What is the decimal expansion of the
integer that has (101011111)2 as its binary expansion?
(101011111)2
= 28 +26 +24 +23 +22 +2
+1 =351
The
base 16 expansion of an integer is called its hexadecimal
expansion. Sixteen different digits are
required for such expansions. Usually,
the hexadecimal digits used are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E,
AND F, where the letters A through F represent the digits corresponding to the
numbers 10 through 15 (in decimal notation).
EXAMPLE
3: What is the decimal expansion of the
hexadecimal expansion of (2AE0B)16 ?
(2AE0B)16
=
2x164+10x163+14x162+0x16+11
= (175627)10.
Since
a hexadecimal digit is represented using four bits, bytes, which are bit
strings of length eight, can be represented by two hexadecimal digits. For example, (11100101)2 = (E5)16
since
(1110)2
= (E)16 and (0101)2 = (5)16.
The
following example shows how to convert from base 10 to another base.
EXAMPLE
4: Find the base 8 expansion of (12345)10
.
Successively
dividing quotients by 8 gives
1543
= 8 x 192 + 7
192
= 8 x 24 + 0
24
= 8 x 3 + 0
3 =
8 x 0 + 3
Since
the remainders are the digits of thebase 8 expansion of 12345, it follows that
(12345)10
= (30071)8.
The
pseudocode given in Algorithm 2 finds the base b expansion (ak-1…a1a0)b
of the integer n.
BASE
B EXPANSIONS
procedure base b expansion(n:
positive integer)
q
:= n
k
:= 0
while q ¹ 0
begin
ak := q mod b
q := ëq/bû
k := k + 1
end {the base b expansion of n
is (ak-1…a1a0)b}
In
Algorithm 2, q represents the quotient obtained by successive divisions by
b, starting with q = n. the digits in the base b expansion are the
remainders of these divisions and are given by q mod b. the algorithm terminates when a quotient q =
0 is reached.
ALGORITHMS
FOR ADDITION AND MULTIPLICATION OF TWO INTEGERS IN BINARY NOTATION
EXAMPLE 5:
Add
a = (1110)2 and b = (1011)2.
a0
+ b0 = 0 + 1 = 0 x 2 + 1
so
that c0 = 0 and s0 = 1.
Then,
since a1 + b1 + c0 = 1 + 1 + 0 = 1 x 2 + 0,
it
follows that c1 = 1 and s1 = 0.
continuing,
a2
+ b2 + c1 = 1 + 0 + 1 = 1 x 2 + 0,
so
that c2 = 1 and s2 = 0.
Finally, since
a3
+ b3 + c2 = 1 + 1 + 1 = 1 x 2 + 1,
it
follows that c3 = 1 and s3 = 1. This means that s4 = c3 = 1. Therefore,
s =
a + b = (11001)2.
ALGORITHM 3:
ADDITION
OF INTEGERS
procedure
add(a,b: positive integers)
{the
binary expansions of a and b are
(an-1…a1a0)2
and (bn-1…b1b0)2 respectively}
c
:= 0
for
j := 0 to n-1
begin
d := ë(aj + bj
+c)/2û
sj := aj + bj
+ c – 2d
c := d
end
sn
:= c
{the
binary expansion of the sum is
(snsn-1…s1s0)2}
EXAMPLE 7: Find the product of a = (110)2 and b = (101)2.
ab0
x 20 = (110)2 x 1 x 20 = (110)2,
ab1
x 21 = (110)2 x 0 x 21 = (0000)2,
ab2
x 22 = (110)2 x 1 x 22 = (11000)2
To find the product, add (110)2, (0000)2, and (11000)2 giving ab = (11110)2.
ALGORITHM 4:
MULTIPLYING INTEGERS
procedure multiply(a,b: positive
integers)
{the
binary expansions of a and b are
(an-1…a1a0)2
and (bn-1…b1b0)2 respectively}
for j := 0 to n-1
begin
if bj = 1 then cj
:= a shifted j places
else cj := 0
end
{c0,
c1,…,cn-1 are the partial products}
p
:= 0
for j := 0 to n-1
p := p + cj
{p
is the value of ab}