The **Euclidean algorithm** (also called **Euclid's algorithm**) is an algorithm to determine the greatest common divisor (GCD) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's *Elements* around 300 BC. The algorithm does not require factoring.

Given two natural numbers *a* and *b*, first check if *b* is zero. If yes, then the GCD is *a*. If no, calculate *c*, the remainder after the division of *a* by *b*. Replace *a* with *b*, *b* with *c*, and start the process again.

For example, the GCD of 1071 and 1029 is computed by this algorithm to be 21 with the following steps:

a | b | c |

1071 | 1029 | 42 |

1029 | 42 | 21 |

42 | 21 | 0 |

21 | 0 |

The algorithm can be formulated in the Python programming language as follows:

`
`

def gcd(a,b): while b != 0: c = a%b a = b b = c return abs(a)

(The absolute value is used in the last line to ensure that the algorithm correctly deals with negative inputs; e.g. gcd(-7,0) = 7.)

By keeping track of the quotients occurring during the algorithm, one can also determine integers *p* and *q* with *ap*+*bq* = gcd(*a*,*b*).
This is known as the extended Euclidean algorithm.

These algorithms can be used in any context where division with remainder is possible. This includes ringss of polynomials over a field as well as the ring of Gaussian integers, and in general all Euclidean domains.

Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. This is illustrated with the following implementation in Python, which works only for positive inputs and is considerably less efficient than the method explained above:

`
`

def gcd(a,b): while a != b: if a > b: a = a - b else: b = b - a return a

Table of contents |

2 Runtime 3 Continued fractions |

### Proof of the correctness of the Euclidean Algorithm

### Runtime

When analyzing the runtime of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case requires Θ(*n*) divisions, where *n* is the number of digits in the input (see Big O notation).

### Continued fractions

The quotients that appear when the Euclidean algorithm is applied to the inputs *a* and *b* are precisely the numbers occurring in the continued fraction representation of *a*/*b*. Take for instance the example of *a* = 1071 and *b* = 1029 used above. Here is the calculation with highlighted quotients:

- 1071 = 1029 ×
**1**+ 42 - 1029 = 42 ×
**24**+ 21 - 42 = 21 ×
**2**+ 0

- .

*a*and

*b*; if

*a*/

*b*is irrational, then the Euclidean algorithm won't terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of

*a*/

*b*.