Namespaces
Variants
Actions

Difference between revisions of "Euclidean algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
 
A method for finding the greatest common divisor of two integers, two polynomials (and, in general, two elements of a [[Euclidean ring|Euclidean ring]]) or the common measure of two intervals. It was described in geometrical form in Euclid's Elements (3rd century B.C.).
 
A method for finding the greatest common divisor of two integers, two polynomials (and, in general, two elements of a [[Euclidean ring|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363201.png" />, the method is as follows. Division with remainder of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363202.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363203.png" /> always leads to the result <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363204.png" />, where the quotient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363205.png" /> is a positive integer and the remainder <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363206.png" /> is either 0 or a positive integer less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363207.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363208.png" />. Successive divisions are performed:
+
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 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 \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e0363209.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
The least positive remainder $b_k$ in this process is the greatest common divisor of $a$ and $b$.
 
 
where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632010.png" /> are positive integers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632011.png" />, until a remainder 0 is obtained. The series of equations (*) finishes thus:
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632012.png" /></td> </tr></table>
 
 
 
The least positive remainder <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632013.png" /> in this process is the greatest common divisor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632015.png" />.
 
  
 
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.
 
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.
Line 16: Line 22:
  
 
====Comments====
 
====Comments====
The Euclidean algorithm to determine the [[Greatest common divisor|greatest common divisor]] of two integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632016.png" /> is quite fast. It can be shown that the number of steps required is at most
+
The Euclidean algorithm to determine the [[Greatest common divisor|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
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632017.png" /></td> </tr></table>
+
\frac{\log a}{\log((1+\sqrt5)/2)}
 
+
$$
A slight extension of the algorithm also yields a solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632018.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036320/e03632019.png" />.
+
A slight extension of the algorithm also yields a solution of $ax + by = \mathrm{gcd}(a,b)$ in $x,y \in \mathbb{Z}$.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.J. Leveque,  "Topics in number theory" , '''1''' , Addison-Wesley  (1956)  pp. Chapt. 2</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.J. Leveque,  "Topics in number theory" , '''1''' , Addison-Wesley  (1956)  pp. Chapt. 2</TD></TR></table>
 +
 +
{{TEX|done}}

Revision as of 08:06, 18 October 2014

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 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}$.

References

[a1] W.J. Leveque, "Topics in number theory" , 1 , Addison-Wesley (1956) pp. Chapt. 2
How to Cite This Entry:
Euclidean algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euclidean_algorithm&oldid=33779
This article was adapted from an original article by BSE-3 (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article