# Euclidean algorithm

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.