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

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

[a1]	W.J. Leveque, "Topics in number theory" , 1 , Addison-Wesley (1956) Chapt. 2 Zbl 0070.03803
[b1]	John Stillwell. Mathematics and Its History, 3rd revised and updated ed. Springer (2010). ISBN 978-1-4419-6052-8 Zbl 1207.01003