CSE-3203 – Design & Analysis of
Algorithm-2
Number Theory
Divisors
Let a, b and c be integers such that
a = b ·c .
Then b and c are said to divide (or are
factors) of a, while a is said to be a
multiple of b (as well as of c). The
pipe symbol “|” denotes “divides” so
the situation is summarized by:
b|a c|a.
Divisors Examples
Q: Which of the following is true?
1. 77 | 7
2. 7 | 77
3. 24 | 24
4. 0 | 24
5. 24 | 0
Division & Remainders
31.1
Common Divisors
Greatest Common Divisor
Relatively Prime
• Let a,b be integers, not both zero. The
greatest common divisor of a and b (or
gcd(a,b) ) is the biggest number d which
divides both a and b.
• a and b are said to be relatively prime if
gcd(a,b) = 1, so no prime common divisors.
Greatest Common Divisor
Relatively Prime
Q: Find the following gcd’s:
1. gcd(11,77)
2. gcd(33,77)
3. gcd(24,36)
4. gcd(24,25)
Greatest Common Divisor
Relatively Prime
A:
1. gcd(11,77) = 11
2. gcd(33,77) = 11
3. gcd(24,36) = 12
4. gcd(24,25) = 1. Therefore 24 and 25
are relatively prime.
NOTE: A prime number are relatively
prime to all other numbers which it
doesn’t divide.
Greatest Common Divisor
Relatively Prime
EG: More realistic. Find gcd(98,420).
Find prime decomposition of each number
and find all the common factors:
98 = 2·49 = 2·7·7
420 = 2·210 = 2·2·105 = 2·2·3·35
= 2·2·3·5·7
Underline common factors: 2·7·7,
2·2·3·5·7
Therefore, gcd(98,420) = 14
Greatest Common Divisor
The GCD and Linear Combinations
Theorem 31.2:
If a and b are integers not both 0, then
gcd(a, b) is the smallest positive element of the set {ax
+ by : x, y are integers} of linear combinations of a
and b.
The GCD and Linear Combinations (2)
Corollaries:
For any integers a and b, if d|a and d|b then
d|gcd(a, b).
For all integers a and b and any nonegative integer n,
gcd(an, bn) = n gcd(a, b).
For all positive integers n, a, and b, if n|ab and
gcd(a, n) = 1, then n|b.
Relatively Prime Integers
Two integers a and b are relatively prime if and only if
their only common divisor is 1
(i.e., gcd(a, b) = 1).
Theorem 31.6:
For any integers a, b, and p, if both
gcd(a, p) = 1 and gcd(b, p) = 1, then
gcd(ab, p) = 1.
Divisibility by Primes
Theorem 31.7:
For all primes p and all integers a, b, if p|ab, then p|a
or p|b (or both).
The Unique Factorization Theorem
Theorem 31.8 (Unique Factorization):
A composite number a can be written in exactly one
way as a product of the form
e1 e2 er
a p p ... p
1 2 r
where the pi are prime, p1 < p2 < …< pr, and the ei
are positive integers.
The GCD Recursion Theorem
Theorem 31.9 (GCD recursion theorem):
For any nonnegative integer a and any positive integer
b,
gcd(a, b) = gcd(b, a mod b).
Euclid’s Algorithm – Finding
GCD
Based on the following theorem
gcd(a, b) = gcd(b, a mod b)
Proof
If d = gcd(a, b), then d|a and d|b
For any positive integer b, a = kb + r ≡ r mod b, a mod b = r
a mod b = a – kb (for some integer k)
because d|b, d|kb
because d|a, d|(a mod b)
∴ d is a common divisor of b and (a mod b)
Conversely, if d is a common divisor of b and (a mod b), then
d|kb and d|[ kb+(a mod b)]
d|[ kb+(a mod b)] = d|a
∴ Set of common divisors of a and b is equal to the set of
common divisors of b and (a mod b)
ex) gcd(18,12) = gcd(12,6) = gcd(6,0) = 6
gcd(11,10) = gcd(10,1) = gcd(1,0) = 1
Euclid’s GCD Algorithm
Euclid(a, b):
if (b == 0)
return a
else
return Euclid(b, a mod b)
Euclid’s Algorithm – Finding
GCD
Recursive algorithm
Function Euclid (a, b) /* assume a b 0
*/
if b = 0 then return a
else return Euclid(b, a mod b)
Iterative algorithm
Euclid(d, f) /* assume d > f > 0
*/
1. X d; Y f
2. if Y=0 return X = gcd(d, f)
3. R = X mod Y
4. X Y
5. Y R
6. goto 2
Euclid’s Algorithm Example
Euclid(1155, 546) =
Euclid(546, 63) =
Euclid(63, 42) =
Euclid(42, 21) =
Euclid(21, 0)
The gcd of 1155 and 546 is 21.
Properties of Euclid’s Algorithm
Since the second argument is monotonically
decreasing, and the gcd is positive, the algorithm
terminates.
Extended Euclidean
Algorithm
You are given two integer number a and
b. Find integer coefficients x and y such
that
d=gcd(a, b) = ax+by
The extended Euclidean algorithm works
the same as the regular Euclidean
algorithm except that we keep track of
more details –namely the quotient q = a/b
in addition to the remainder r = a mod b.
This allows us to backtrack and write the
gcd(a,b) as a linear combination of a and
b.
Extended Euclid’s Algorithm
ExtEuclid(a, b):
if b == 0
return (a, 1, 0)
(d´, x´, y´) ← ExtEuclid(b, a mod b)
(d, x, y) ← (d´, y´, x´-floor(a/b)·y´)
return (d, x, y)
d = gcd(a, b) = ax + by
Extended Euclid’s Algorithm
Suppose a and b are given. Find x and y such that,
ax+by=gcd (a,b)
Let, d=gcd(a,b)
Then, ax+by=d [by Thm 31.2]
Again, gcd(a,b)=gcd(b, a mod b)
So, ax+by = d = bx´+(a mod b)y´
We know that, a = b.a/b+a mod b
So, a mod b = a – b.a/b
Thus, ax+by = bx´+(a – b.a/b).y´
= ay´+b(x´- a/b.y´)
Finally, x = y´
y =x´- a/b.y´
