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

Proof:
if N < M/2 then as M mod N < N we have M mod N < N < M/2
if 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.