The extended Euclidean algorithm is an algorithm from the mathematical branch of number theory . In addition to the greatest common divisor of two natural numbers , it also calculates two whole numbers and that satisfy the following equation:
The algorithm is an extension of already in antiquity known Euclidean algorithm , which calculates only the greatest common divisor.
The main area of application of the extended Euclidean algorithm is the calculation of the inverse elements in integer remainder class rings , because when the algorithm determines the triple , either and thus , i.e. the multiplicative inverse of modulo, or what means that modulo has no inverse. This is the basis for the solution of Diophantine equations or, more generally, of integral linear systems of equations. The determination of inverse elements is also a basis for the Chinese remainder theorem , which in turn is the basis of the important trick of the small prime numbers in computable algebra. A task is solved in several finite fields and these partial solutions are lifted into ever larger residual class rings until an integer solution can be read off. The algorithm also provides a constructive proof for Bézout's lemma .
Function using the example
The most widely known version of the Euclidean algorithm refers to the range of whole numbers. However, it can literally be applied to any ring in which a least-remainder division can be performed. Such rings are called Euclidean , an example is the polynomial ring in a variable with rational or real coefficients. A clearly defined remainder with the smallest degree can always be found in this.
Let's look at an example. For the specification of the numbers 99 and 78, the simple Euclidean algorithm produces the sequence of divisions with remainder:
3 is a divisor of 6 and thus the greatest common divisor of 99 and 78 you are looking for. You can now read these equations backwards and represent the remainder as the difference between the other two terms. If these remainder representations are inserted into one another recursively, then different representations of the last remainder 3 result:
The greatest common divisor is shown as an integral linear combination of the two output numbers 78 and 99.
In the calculation rule just presented, one must first wait for the last step of the simple Euclidean algorithm before the calculation of the coefficients sought can begin. But you can also represent all other remainders as an integral linear combination of 78 and 99 and determine the associated coefficients in each step of the simple Euclidean algorithm:
Tabular representation
Recursive variant
The intermediate results of both calculation options can be clearly displayed in tables. For the first variant, in which the sequence of divisions with remainder is worked up backwards, this can take the following form:
a
|
b
|
q
|
s
|
t
|
99 |
78 |
1 |
|
|
78 |
21st |
3 |
|
|
21st |
15th |
1 |
|
|
15th |
6th |
2 |
|
|
6th |
3 |
2 |
|
|
3 |
0 |
|
|
|
|
|
a
|
b
|
q
|
s
|
t
|
99 |
78 |
1 |
|
|
78 |
21st |
3 |
|
|
21st |
15th |
1 |
|
|
15th |
6th |
2 |
|
|
6th |
3 |
2 |
|
|
3 |
0 |
|
1 |
0
|
|
|
a
|
b
|
q
|
s
|
t
|
99 |
78 |
1 |
−11 |
14th
|
78 |
21st |
3 |
3 |
−11
|
21st |
15th |
1 |
−2 |
3
|
15th |
6th |
2 |
1 |
−2
|
6th |
3 |
2 |
0 |
1
|
3 |
0 |
|
1 |
0
|
|
|
First, as in the table on the left, the simple Euclidean algorithm is executed. The division with remainder always has the form (in other words, with is the result of the integer division of by , with remainder ), where and are determined. is noted in the line, the pair is entered in place of the pair in the next line. This step is repeated until there is a zero in the column .
Up to this point the simple Euclidean algorithm has been carried out, and the greatest common factor can be read in the lower left corner (column ). In our case the three. Now the calculation of the integer coefficients and begins . In each line should apply. Accordingly, the last line is entered because . Since it is in the last line of the column , any value can be used, because . Here in the example is set, the result is the middle table.
Now you work your way up from the bottom. For that you take the line below. This is calculated from the the relevant line and the and the line below.
or.
For the penultimate line we get so and , above then and etc.
We repeat this step until the table is filled out. The table on the right results. The entries for and in the first line are the values you are looking for. As already mentioned, the greatest common factor can be found in the lower left corner. The following applies to the example
Iterative variant
Again the values 99 and 78 are given:
As can be seen from the example, the current calculation step depends on the intermediate results of the two previous calculation steps. This can be taken into account by placing an auxiliary line in front of the initialization. Next, for clarity, are auxiliary variables and inserted with a separate column.
a
|
b
|
q
|
u
|
s
|
v
|
t
|
0 |
99 |
0 |
0 |
1 |
1 |
0
|
99 |
78 |
1 |
1 |
0 |
0 |
1
|
78 |
21st |
3 |
0 |
1 |
1 |
−1
|
21st |
15th |
1 |
1 |
−3 |
−1 |
4th
|
15th |
6th |
2 |
−3 |
4th |
4th |
−5
|
6th |
3 |
2 |
4th |
−11 |
−5 |
14th
|
3 |
0 |
|
−11 |
26th |
14th |
−33
|
|
|
The following operations are carried out to determine the next line in each case:
- The division with remainder is carried out, and as is set.
- The new values of the auxiliary variables are taken from the current line, and .
- The new coefficients are given by and
Due to this rule, the relationships apply in every line except the first line
-
and ,
here with the initial values and . The last two lines show that 3 is the greatest common factor and that it holds.
If you are familiar enough with this method, you can omit the columns and in the table , as these only repeat entries already above. Further examples in this abridged form are shown in the following tables:
k.
|
b
|
q
|
s
|
t
|
−1. |
a orig = 122
|
- |
1 |
0
|
0. |
b orig = 22
|
5 |
0 |
1
|
1. |
12 |
1 |
1 |
−5
|
2. |
10 |
1 |
−1 |
6th
|
3. |
2 = gcd |
5 |
2 = s |
-11 = t
|
4th |
0 |
- |
- |
-
|
|
k.
|
b
|
q
|
s
|
t
|
−1. |
a orig = 120
|
- |
1 |
0
|
0. |
b orig = 23
|
5 |
0 |
1
|
1. |
5 |
4th |
1 |
−5
|
2. |
3 |
1 |
−4 |
21st
|
3. |
2 |
1 |
5 |
−26
|
4th |
1 = gcd |
2 |
-9 = s |
47 = t
|
|
General mathematical basis
The Euclidean algorithm generates two sequences for given integers a and b (in general: elements of a Euclidean ring): a sequence of quotients and a sequence of remainders, where . The same applies to
every step
-
, .
After a finite number of steps, the remainder is zero.
We now move on to remainder classes modulo b . It is trivial to see that and are multiples of after adding or subtracting multiples of . More precisely, the remainder classes are multiples of the remainder class for , and according to the recursion rule also for . So a sequence of multipliers can be constructed that is initialized with and so that
applies. The result is the recursive relationship
-
.
This recursion can be summarized in the following sequence of steps for the extended Euclidean algorithm:
- Receive and as input.
- Set , , and .
- Repeat:
- Increase by one.
- Find the integer quotient .
- Put and .
- until applies.
- Give the rest and the number of returns.
Each step implicitly also contains a multiplier , whereby this division leaves no remainder. The sequence can also be determined explicitly , and
-
.
After the last step it now results
For the sake of clarity, the auxiliary sequences and and and are also carried along with manual calculations .
Algorithmic implementation
Recursive variant
There is also a recursive variant for the extended Euclidean algorithm , which is given by the following pseudocode :
a,b: zwei Zahlen für die der erweiterte euklidische Algorithmus durchgeführt wird
extended_euclid(a,b)
1 wenn b = 0
2 dann return (a,1,0)
3 (d',s',t') extended_euclid(b, a mod b)
4 (d,s,t) (d',t',s' – (a div b)t')
5 return (d,s,t)
The following mathematical function definition with case distinction is synonymous:
Tricks for Efficient Computer Implementation
Representation using matrices
If the variables of the Euclidean algorithm are provided with indices for the iteration step, division with remainder is carried out in step . In the transition to the next step and is set. If one forms and a column vector , the entire step has a representation with transition matrix ,
-
.
If the algorithm terminates according to steps, then and therefore applies . If the rules of formation of the column vectors are inserted into one another, the connection between the first and the last column vector results from a matrix product ,
-
.
By multiplying by the row vector , the first row on both sides is extracted, so the following applies
-
.
The different ways of calculating the matrix product of the last identity result in the different variants of the extended Euclidean algorithm. In the classic variant, in which the divisions are evaluated starting with the remainder from the last, the matrix products are formed starting from the left. This corresponds to the following recursive algorithm. It is set and recursive
-
For
certainly. In the end it applies . However, all quotients must first be determined before the first recursion step can be carried out.
If the product formation is started from the right, the quotient of division with remainder is used at the moment in which it was determined and can then be forgotten. This corresponds to the algorithm given at the beginning, in which at the beginning
-
set and for
is iterated. Overall, this results
-
.
In the end, the following applies , although the last iteration step can also be omitted
because of the relationships and
Web links
Individual evidence
-
^ Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms . 2nd Edition. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7 .