# Euclidean algorithm

The **Euclidean Algorithm** to compute the greatest common divisor for two integers *a* and *b* (not
zero) is based on the following fact:

Ifris the remainder whenais divided byb(see the division algorithm), then gcd (a,b)=gcd(b,r).

For example, gcd(356,96) = gcd(96,68) (because 68 = 356 -
3^{.}96). Continuing this process of dividing, then continuing with the remainder and divisor, we have

gcd(356,96) = gcd(96,68) = gcd(68,28) = gcd(28,12) = gcd(12,4) = gcd(4,0) = 4.

This ancient algorithm was stated by Euclid in his *Elements* over 2000 years ago, and is still one of the most efficient ways to find the greatest common divisor of two integers.

The algorithm can be written in pseudo-code as follows

`Euclid(`

a,b) { while (bnot 0) { interchange(a,b)b:=bmoda} return(a) }

On modern computers the binary gcd algorithm is usually faster even though it takes more (but simpler) steps.

One of the uses of the Euclidean algorithm is to
solve the diophantine equation *ax*+*by* = *c*. This is solvable (for *x* and *y*) whenever gcd(*a*,*b*) divides *c*. If we keep track of the quotients in the Euclidean algorithm while finding gcd(*a*,*b*), we can reverse the steps to find *x* and *y*.

**See Also:** LamesTheorem