2.1.2 Euclidean Algorithms 2

Theorem 2.1.7 If a and b are positive integers with a>b, then gcd(a, b)=gcd(b, a mod b).

The Euclidean algorithm consists of performing the following sequence of divisions Then

the greatest common divisor will be

gcd(a, b)=gcd(b, r1)=gcd(r2,r1)=···= gcd(rn, 0) = rn.

Hence, it follows that gcd(a, b)=rn.

Theorem 2.1.8 The above algorithm has a running time of O ((ln n)^2) bit operations.

The Euclidean algorithm can be extended so that it not only yields the greatest common

divisor d of two integers a and b, but also integers x and y satisfying ax + by = d.

Theorem 2.1.9 Extended Euclidean algorithm has running time of O((ln n)2) bits op-

erations.

Since the Euclidean algorithm computes the greatest common divisors, it can be used

to determine if a positive integer a modulo n. However it does not compute the value of the multiplicative inverse.