function gcd( a,b : Integer ) returns IntegerThe 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.
if ( b != 0 )
return gcd( b, a mod b )
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 <
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
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.