Euclidean algorithm

2020 Mathematics Subject Classification: Primary: 11A05 Secondary: 13F0768W40 [68W40) MSN][68W40 ZBL]

A method for finding the greatest common divisor of two integers, two polynomials (and, in general, two elements of a Euclidean ring) or the common measure of two intervals. It was described in geometrical form in Euclid's Elements (3rd century B.C.).

For two positive integers $a \ge b$, the method is as follows. Division with remainder of $a$ by $b$ always leads to the result $a = n b + b_1$, where the quotient $n$ is a positive integer and the remainder $b_1$ is either 0 or a positive integer less than $b$, $0 \le b_1 < b$. Successive divisions are performed: $$ \begin{array}{rcl} a &=& n b + b_1 \\ b & = & n_1 b_1 + b_2 \\ b_1 & = & n_2 b_2 + b_3 \\ & \cdots & \end{array} \tag{*} $$ where the $n_i$ are positive integers and $0 \le b_i < b_{i-1}$, until a remainder $b_{k+1} = 0$ is obtained. The series of equations (*) finishes thus: $$ b_{k-2} = n_{k-1} b_{k-1} + b_k \,,\ \ \ b_{k-1} = n_k b_k \ . $$

The least positive remainder $b_k$ in this process is the greatest common divisor of $a$ and $b$.

The Euclidean algorithms for polynomials or for intervals are similar to the one for integers. In the case of incommensurable intervals the Euclidean algorithm leads to an infinite process.

Comments[edit]

The Euclidean algorithm to determine the greatest common divisor of two integers $a \ge b > 0$ is quite fast. It can be shown that the number of steps required is at most $$ \frac{\log a}{\log((1+\sqrt5)/2)} \ . $$ A slight extension of the algorithm also yields a solution of $ax + by = \mathrm{gcd}(a,b)$ in $x,y \in \mathbb{Z}$.

Euler observed that the Euclidean algorithm applied to a pair of natural numbers $(a,b)$ yields the continued fraction development of the rational number $a/b$.

References[edit]