# 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 ${\displaystyle \gcd(a,b)=\gcd(b,a-kb)}$ for any integer ${\displaystyle k}$. To see why this is true, let ${\displaystyle g}$ be any common divisor of ${\displaystyle a}$ and ${\displaystyle b}$. Then ${\displaystyle g}$ divides ${\displaystyle a}$ and ${\displaystyle kb}$ (as it divides ${\displaystyle b}$), so it divides their difference ${\displaystyle a-kb}$. Conversely, let ${\displaystyle h}$ be any common divisor of ${\displaystyle b}$ and ${\displaystyle a-kb}$. Then ${\displaystyle h}$ divides ${\displaystyle kb}$ (as it divides ${\displaystyle b}$) and it divides ${\displaystyle a-kb}$, so it divides their sum ${\displaystyle a}$. Thus, the set of common divisors of ${\displaystyle a}$ and ${\displaystyle b}$ is the same as the set of common divisors of ${\displaystyle b}$ and ${\displaystyle a-kb}$. In particular, their greatest common divisor is the same.

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

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