Euclidean algorithm

From Algorithmist
Jump to navigation Jump to search

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

Pseudocode[edit]

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

Explanation[edit]

Why does this work?

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

As is indeed a number of the form for some , our algorithm is justified.

The point of the algorithm is to continue this procedure until one number is 0, because , which we can then return as our answer.