# Euclidean algorithm

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

## Pseudocode

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

## Explanation

Why does this work?

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.

As $a\,{\bmod {b}}$ is indeed a number of the form $a-kb$ for some $k$ , our algorithm is justified.

The point of the algorithm is to continue this procedure until one number is 0, because $gcd(x,0)=abs(x)$ , which we can then return as our answer.