Euclidean Algorithm

The Euclidean algorithm is an algorithm for finding the greatest common divisor of two integers.

Pseudo Code:

function gcd( a,b : Integer ) returns Integer
{
if ( b != 0 )
return gcd( b, a mod b )
return abs(a)
}


Explanation

The fact we need is that gcd(a,b) = gcd(b,a - kb) for any integer k. To see why this is true, let g be any common divisor of a and b. Then g divides a and kb (as it divides b), so it divides their difference a - kb. Conversely, let h be any common divisor of b and a - kb. Then h divides kb (as it divides b) and it divides a - kb, so it divides their sum a. Thus, the set of common divisors of a and b is the same as the set of common divisors of b and a - kb. In particular, their greatest common divisor is the same.

Complexity:

The estimation of the complexity of the Euclidean Algorithm is slightly tricky.

We shall prove a small theorem to estimate the time complexity.

Theorem: if M > N then M mod N <> M/2 then clearly N goes once in to M with a remainder M-N which is less than M/2.


Now having proved the above theorem, we shall look into the time complexity.

after 2 iterations the remainder decreases by atleast half(using the above theorem... employ it for 2 iterations!!)
hence in the worst case,the no of iterations are 2*(logN) =O(logN).


Some Properties of the gcd

Any number that divides both a and b divides gcd(a,b)

gcd(a,b) is expressible as ax + by for some integers x and y

More generally, the equation ax + by = c has integer solutions for x and y if and only if gcs(a,b) divides c.