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

Pseudo Code:

function gcd( a,b : Integer ) returns IntegerThe fact we need is that gcd(

{

if ( b != 0 )

return gcd( b, a mod b )

return abs(a)

}

Explanation

*a*,

*b*) = gcd(

*b*,

*a*-

*k*

*b*) 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

*k*

*b*(as it divides

*b*), so it divides their difference

*a*-

*k*

*b*. Conversely, let

*h*be any common divisor of

*b*and

*a*-

*k*

*b*. Then

*h*divides

*k*

*b*(as it divides

*b*) and it divides

*a*-

*k*

*b*, 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*-

*k*

*b*. 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 <

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

*a*and

*b*divides gcd(

*a*,

*b*)

gcd(

*a*,

*b*) is expressible as

*a*

*x*+

*b*

*y*for some integers

*x*and

*y*

More generally, the equation

*a*

*x*+

*b*

*y*=

*c*has integer solutions for

*x*and

*y*if and only if gcs(a,b) divides c.

## No comments:

## Post a Comment