Euclidean algorithm: Difference between revisions
imported>Michael Hardy m (→Full-fledge and faster version: typo) |
imported>Michael Hardy (→Solution of linear Diophantine equations: format adjustments in an array) |
||
(17 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{subpages}} | |||
In [[mathematics]], the '''Euclidean algorithm''', or '''Euclid's algorithm''', named after the ancient Greek geometer and number-theorist [[Euclid]], is an [[algorithm]] for finding the [[greatest common divisor]] (gcd) of two [[integer]]s. The algorithm does not require [[prime number|prime factorizations]] and runs efficiently even when methods using prime factorizations do not. | |||
The algorithm is based on this simple fact: If ''d'' is a divisor of both ''m'' and ''n'', then ''d'' is a divisor of ''m'' − ''n''. Thus, for example, any divisor shared in common by both 1989 and 867 must also be a divisor of 1989 − 867 = 1122. This reduces the problem of finding gcd(1989, 867) to the problem of finding gcd(1122, 867). This reduction to smaller integers is iterated as many times as possible. Since one cannot go | == The algorithm == | ||
=== Simple but slow version === | |||
The algorithm is based on this simple fact: If ''d'' is a divisor of both ''m'' and ''n'', then ''d'' is a divisor of ''m'' − ''n''. Thus, for example, any divisor shared in common by both 1989 and 867 must also be a divisor of 1989 − 867 = 1122. This reduces the problem of finding gcd(1989, 867) to the problem of finding gcd(1122, 867). This reduction to smaller integers is iterated as many times as possible. Since one cannot go on getting smaller and smaller positive integers forever, one must reach a point where one of the two is 0. But one can get 0 when subtracting two integers only if the two integers are equal. Therefore, one must reach a point where the two are equal. At that point, the problem of the gcd becomes trivial. | |||
Thus: | Thus: | ||
Line 25: | Line 29: | ||
:<math> \frac{1989}{867} = \frac{51 \times 39}{51 \times 17} =\frac{39}{17}. </math> | :<math> \frac{1989}{867} = \frac{51 \times 39}{51 \times 17} =\frac{39}{17}. </math> | ||
== | === Efficient version === | ||
In the example above, | In the example above, successive subtraction of 867 from the larger of the two numbers whose gcd was sought led to the [[remainder]] on division of the larger number, 1989, by the smaller, 867. Thus the algorithm may be stated: | ||
* Replace the larger of the two numbers by the remainder on division of the larger one by the smaller one. | * Replace the larger of the two numbers by the remainder on division of the larger one by the smaller one. | ||
* Repeat until the two numbers are equal. | * Repeat until one of the two numbers is 0. The gcd is the other number. | ||
The "simple but slow" version was presented only to show the simplicity of the underlying idea. | |||
== Example == | |||
It is desired to find the gcd of 357765 and 110959. | |||
to lowest terms. We have | |||
: gcd(357765, 110959) = gcd(24888, 110959) | |||
because 24888 is the remainder when 357765 is divided by 110959. Then | |||
: gcd(24888, 110959) = gcd(24888, 11407) | |||
because 11407 is the remainder when 110959 is divided by 24888. Then | |||
: gcd(24888, 11407) = gcd(2074, 11407) | |||
because 2074 is the remainder when 24888 is divided by 11407. Then | |||
: gcd(2074, 11407) = gcd(2074, 1037) | |||
because 1037 is the remainder when 11407 is divided by 2074. Then | |||
: gcd(2074, 1037) = gcd(0, 1037) | |||
because 0 is the remainder when 2074 is divided by 1037. | |||
No further reduction is possible, and the gcd is 1037. | |||
=== Two applications === | |||
==== Reducing a fraction to lowest terms ==== | |||
It is desired to reduce | |||
:<math> \frac{357765}{110959} </math> | |||
to lowest terms. We have | |||
:<math> \frac{357765}{110959} = \frac{1037 \times 345}{1037 \times 107} = \frac{345}{107}. </math> | |||
==== Finding a common denominator ==== | |||
It is desired to find the exact value of | |||
:<math> \frac{6}{357765} + \frac{5}{110959} </math> | |||
(not a decimal approximation, such as any conventional calculator would give). We have | |||
:<math> \frac{6}{1037\times 345} + \frac{5}{1037 \times 107} | |||
= \frac{6 \times 107}{1037\times 345 \times 107} + \frac{5 \times 345}{1037 \times 107 \times 345} | |||
= \frac{642}{38280855} + \frac{1725}{38280855} </math> | |||
etc. The common denominator 38280855 is the [[least common multiple]] of the two denominators 357765 and 110959, and is much smaller than what would have resulted from multiplying the two denominators. | |||
== Solution of linear Diophantine equations == | |||
In an example above we found the gcd of 357765 and 110959 to be 1037. In [[number theory]] it is of some interest that this entails that the [[Diophantine equation]] | |||
: <math> 357765x + 110959y = 1037 \,</math> | |||
can be solved in integers ''x'' and ''y''. Generally if gcd(''a'', ''b'') = ''c'', then the equation | |||
: <math> ax + by = c\,</math> | |||
has a solution a pair (''x'', ''y'') of integers. Moreover, if we make use of the quotients, rather than only the remainders, in the divisions we did while executing Euclid's algorithm, we can find ''x'' and ''y''. Here is how: | |||
: <math> | |||
\begin{array}{rcrclclll} | |||
357765 & - & 110959 & \cdot & 3 & = & 24888 & (\text{quotient} = 3, \text{ remainder} = 24888) & {}\qquad (1) \\ | |||
110959 & - & 24888 & \cdot & 4 & = & 11407 & (\text{quotient} = 4, \text{ remainder} = 11407) & {} | |||
\qquad (2) \\ | |||
24888 & - & 11407 & \cdot & 2 & = & 2074 & (\text{quotient} = 2, \text{ remainder} = 2074) & {} \qquad (3) \\ | |||
11407 & - & 2074 & \cdot & 5 & = & 1037 & (\text{quotient} = 5, \text{ remainder} = 1037) & {} \qquad (4) \\ | |||
2074 & - & 1037 & \cdot & 2 & = & 0 & (\text{quotient} = 2, \text{ remainder} = 0) & {} \qquad (5) | |||
\end{array} | |||
</math> | |||
As above, when we get 0 as a remainder, we know that the last remainder preceding it, 1037, is the gcd. Now we want to write the gcd, 1037, as a [[linear combination]] of the two numbers we started with, in which the coefficients ''x'' and ''y'' are integers. We start with the information on line (4) above: | |||
: <math> 1037 = [11407] - [2074] \cdot 5. \, </math> | |||
This gives 1037 as a linear combination of the two numbers in square brackets, which were among the successive remainders. First, we replace the smaller of those two remainders with what line (3) tells us it is equal to: | |||
: <math> 1037 = [11407] - ([24888] - [11407]\cdot 2) \cdot 5 \, </math> | |||
<!-- extra blank space between two lines of "displayed" TeX for ease of legibility --> | |||
::: <math> = [11407]\cdot 11 - [24888]\cdot 5. \, </math> | |||
This gives us 1037 as a linear combination of the two remainders that appear in line (3) above. Then, we replace the smaller of those two remainders with what line (2) tells us it is equal to: | |||
: <math> 1037 = ([110959] - [24888]\cdot 4)\cdot 11 - [24888] \cdot 5 \, </math> | |||
<!-- extra blank space between two lines of "displayed" TeX for ease of legibility --> | |||
::: <math> = [110959]\cdot 11 - [24888]\cdot 49. \, </math> | |||
This gives us 1037 as a linear combination of the two remainders that appear in line (2) above. Then, we replace the smaller of those two remainders with what line (1) tells us it is equal to: | |||
: <math> 1037 = [110959]\cdot 11 - ([357765] - [110959]\cdot 3)\cdot 49 \, </math> | |||
<!-- extra blank space between two lines of "displayed" TeX for ease of legibility --> | |||
::: <math> = [110959]\cdot 158 - [357765] \cdot 49. \, </math> | |||
This gives us 1037 as a linear combination of the two numbers we started with, 357765 and 110959. Thus ''x'' = −49 and ''y'' = 158 is a solution. |
Revision as of 12:05, 3 May 2016
![](http://s9.addthis.com/button1-share.gif)
In mathematics, the Euclidean algorithm, or Euclid's algorithm, named after the ancient Greek geometer and number-theorist Euclid, is an algorithm for finding the greatest common divisor (gcd) of two integers. The algorithm does not require prime factorizations and runs efficiently even when methods using prime factorizations do not.
The algorithm
Simple but slow version
The algorithm is based on this simple fact: If d is a divisor of both m and n, then d is a divisor of m − n. Thus, for example, any divisor shared in common by both 1989 and 867 must also be a divisor of 1989 − 867 = 1122. This reduces the problem of finding gcd(1989, 867) to the problem of finding gcd(1122, 867). This reduction to smaller integers is iterated as many times as possible. Since one cannot go on getting smaller and smaller positive integers forever, one must reach a point where one of the two is 0. But one can get 0 when subtracting two integers only if the two integers are equal. Therefore, one must reach a point where the two are equal. At that point, the problem of the gcd becomes trivial.
Thus:
- gcd(1989, 867) = gcd(1989 − 867, 867) = gcd(1122, 867)
- = gcd(1122 − 867, 867) = gcd(255, 867)
- = gcd(255, 867 − 255) = gcd(255, 612)
- = gcd(255, 612 − 255) = gcd(255, 357)
- = gcd(255, 357 − 255) = gcd(255, 102)
- = gcd(255 − 102, 102) = gcd(51, 102)
- = gcd(51, 102 − 51) = gcd(51, 51) = 51.
Thus the largest integer that is a divisor of both 1989 and 867 is 51. One use of this fact is in reducing the fraction 1989/867 to lowest terms:
Efficient version
In the example above, successive subtraction of 867 from the larger of the two numbers whose gcd was sought led to the remainder on division of the larger number, 1989, by the smaller, 867. Thus the algorithm may be stated:
- Replace the larger of the two numbers by the remainder on division of the larger one by the smaller one.
- Repeat until one of the two numbers is 0. The gcd is the other number.
The "simple but slow" version was presented only to show the simplicity of the underlying idea.
Example
It is desired to find the gcd of 357765 and 110959.
to lowest terms. We have
- gcd(357765, 110959) = gcd(24888, 110959)
because 24888 is the remainder when 357765 is divided by 110959. Then
- gcd(24888, 110959) = gcd(24888, 11407)
because 11407 is the remainder when 110959 is divided by 24888. Then
- gcd(24888, 11407) = gcd(2074, 11407)
because 2074 is the remainder when 24888 is divided by 11407. Then
- gcd(2074, 11407) = gcd(2074, 1037)
because 1037 is the remainder when 11407 is divided by 2074. Then
- gcd(2074, 1037) = gcd(0, 1037)
because 0 is the remainder when 2074 is divided by 1037.
No further reduction is possible, and the gcd is 1037.
Two applications
Reducing a fraction to lowest terms
It is desired to reduce
to lowest terms. We have
Finding a common denominator
It is desired to find the exact value of
(not a decimal approximation, such as any conventional calculator would give). We have
etc. The common denominator 38280855 is the least common multiple of the two denominators 357765 and 110959, and is much smaller than what would have resulted from multiplying the two denominators.
Solution of linear Diophantine equations
In an example above we found the gcd of 357765 and 110959 to be 1037. In number theory it is of some interest that this entails that the Diophantine equation
can be solved in integers x and y. Generally if gcd(a, b) = c, then the equation
has a solution a pair (x, y) of integers. Moreover, if we make use of the quotients, rather than only the remainders, in the divisions we did while executing Euclid's algorithm, we can find x and y. Here is how:
As above, when we get 0 as a remainder, we know that the last remainder preceding it, 1037, is the gcd. Now we want to write the gcd, 1037, as a linear combination of the two numbers we started with, in which the coefficients x and y are integers. We start with the information on line (4) above:
This gives 1037 as a linear combination of the two numbers in square brackets, which were among the successive remainders. First, we replace the smaller of those two remainders with what line (3) tells us it is equal to:
This gives us 1037 as a linear combination of the two remainders that appear in line (3) above. Then, we replace the smaller of those two remainders with what line (2) tells us it is equal to:
This gives us 1037 as a linear combination of the two remainders that appear in line (2) above. Then, we replace the smaller of those two remainders with what line (1) tells us it is equal to:
This gives us 1037 as a linear combination of the two numbers we started with, 357765 and 110959. Thus x = −49 and y = 158 is a solution.