Extended Euclidean Algorithm

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: ${\displaystyle \operatorname {ggT} (a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle s}$ ${\displaystyle t}$

${\displaystyle \operatorname {ggT} (a,b)=s\cdot a+t\cdot b}$

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 . ${\displaystyle (d=\operatorname {ggT} (a,b),s,t)}$ ${\displaystyle d=1}$ ${\displaystyle 1\equiv t\cdot b{\pmod {a}}}$ ${\displaystyle t}$ ${\displaystyle b}$ ${\displaystyle a,}$ ${\displaystyle d\neq 1,}$ ${\displaystyle b}$ ${\displaystyle a}$

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:

${\displaystyle {\begin{matrix}{\underline {99}}&=&1\cdot {\underline {78}}+{\underline {21}}\\{\underline {78}}&=&3\cdot {\underline {21}}+{\underline {15}}\\{\underline {21}}&=&1\cdot {\underline {15}}+{\underline {\ 6}}\\{\underline {15}}&=&2\cdot {\underline {\ 6}}+{\underline {\ 3}}\\{\underline {6}}&=&2\cdot {\underline {\ 3}}+{\underline {\ 0}}\end{matrix}}}$

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:

${\displaystyle {\begin{array}{rclcl}{\underline {\ 3}}&=&{\underline {15}}-2\cdot {\underline {\ 6}}\\&=&{\underline {15}}-2\cdot ({\underline {21}}-1\cdot {\underline {15}})&=&3\cdot {\underline {15}}-2\cdot {\underline {21}}\\&=&3\cdot ({\underline {78}}-3\cdot {\underline {21}})-2\cdot {\underline {21}}&=&3\cdot {\underline {78}}-11\cdot {\underline {21}}\\&=&3\cdot {\underline {78}}-11\cdot ({\underline {99}}-1\cdot {\underline {78}})&=&14\cdot {\underline {78}}-11\cdot {\underline {99}}\end{array}}}$

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:

${\displaystyle {\begin{array}{rclcrclcl}{\underline {99}}&=&1\cdot {\underline {78}}+{\underline {21}}&\iff &{\underline {21}}&=&&&1\cdot {\underline {99}}-1\cdot {\underline {78}}\\{\underline {78}}&=&3\cdot {\underline {21}}+{\underline {15}}&\iff &{\underline {15}}&=&1\cdot {\underline {78}}-3\cdot {\underline {21}}&=&-3\cdot {\underline {99}}+4\cdot {\underline {78}}\\{\underline {21}}&=&1\cdot {\underline {15}}+{\underline {\ 6}}&\iff &{\underline {\ 6}}&=&1\cdot {\underline {21}}-1\cdot {\underline {15}}&=&4\cdot {\underline {99}}-5\cdot {\underline {78}}\\{\underline {15}}&=&2\cdot {\underline {\ 6}}+{\underline {\ 3}}&\iff &{\underline {\ 3}}&=&1\cdot {\underline {15}}-2\cdot {\underline {\ 6}}&=&-11\cdot {\underline {99}}+14\cdot {\underline {78}}\end{array}}}$

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 . ${\displaystyle a=q\cdot b+r}$ ${\displaystyle q}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle (b,r)}$ ${\displaystyle (a,b)}$ ${\displaystyle b}$

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. ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle 3=s\cdot a+t\cdot b}$ ${\displaystyle s=1}$ ${\displaystyle 3\cdot 1=3}$ ${\displaystyle b=0}$ ${\displaystyle t}$ ${\displaystyle 0\cdot t=0}$ ${\displaystyle t=0}$

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. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle q}$ ${\displaystyle s}$ ${\displaystyle t}$

${\displaystyle s=t_{\mathsf {alt}}}$

or.

${\displaystyle t=s_{\mathsf {alt}}-q\cdot t_{\mathsf {alt}}}$

For the penultimate line we get so and , above then and etc. ${\displaystyle s=0}$ ${\displaystyle t=1-2\cdot 0=1}$ ${\displaystyle s=1}$ ${\displaystyle t=0-2\cdot 1=-2}$

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 ${\displaystyle s}$ ${\displaystyle t}$

${\displaystyle 3=-11\cdot 99+14\cdot 78}$

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. ${\displaystyle u}$ ${\displaystyle v}$

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. ${\displaystyle a=q\cdot b+r}$ ${\displaystyle a_{\rm {neu}}=b}$ ${\displaystyle b_{\rm {neu}}=r}$
• The new values ​​of the auxiliary variables are taken from the current line, and . ${\displaystyle u_{\rm {neu}}=s}$ ${\displaystyle v_{\rm {neu}}=t}$
• The new coefficients are given by and ${\displaystyle s_{\rm {neu}}=u-q\cdot s}$ ${\displaystyle t_{\rm {neu}}=v-q\cdot t}$

Due to this rule, the relationships apply in every line except the first line

${\displaystyle a=u\cdot a_{\rm {orig}}+v\cdot b_{\rm {orig}}}$and , ${\displaystyle b=s\cdot a_{\rm {orig}}+t\cdot b_{\rm {orig}}}$

here with the initial values and . The last two lines show that 3 is the greatest common factor and that it holds. ${\displaystyle a_{\rm {orig}}=99}$ ${\displaystyle b_{\rm {orig}}=78}$ ${\displaystyle 3=-11\cdot 99+14\cdot 78}$

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: ${\displaystyle a,u}$ ${\displaystyle v}$

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 ${\displaystyle (q_{k})_{k}}$ ${\displaystyle (r_{k})_{k}}$ ${\displaystyle r_{0}=a,\;r_{1}=b}$ ${\displaystyle k=1,2,\ldots }$

${\displaystyle r_{k-1}=q_{k}\cdot r_{k}+r_{k+1}}$, . ${\displaystyle |r_{k+1}|<|r_{k}|}$

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 ${\displaystyle r_{0}=a=1\cdot a}$ ${\displaystyle r_{1}=b=0\cdot a+1\cdot b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle [r_{k}]_{b}}$ ${\displaystyle [a]_{b}}$ ${\displaystyle k=0,1}$ ${\displaystyle k=2,3,\ldots }$ ${\displaystyle (s_{k})_{k}}$ ${\displaystyle s_{0}=1}$ ${\displaystyle s_{1}=0}$

${\displaystyle r_{k}\equiv s_{k}\cdot a{\pmod {b}}}$

applies. The result is the recursive relationship

${\displaystyle s_{k-1}\equiv q_{k}\cdot s_{k}+s_{k+1}}$.

This recursion can be summarized in the following sequence of steps for the extended Euclidean algorithm:

• Receive and as input. ${\displaystyle a}$ ${\displaystyle b}$
• Set , , and . ${\displaystyle k=0}$ ${\displaystyle r_{0}=a,\;r_{1}=b}$ ${\displaystyle s_{0}=1}$ ${\displaystyle s_{1}=0}$
• Repeat:
  • Increase by one. ${\displaystyle k}$
  • Find the integer quotient . ${\displaystyle q_{k}=r_{k-1}\;\div \;r_{k}}$
  • Put and . ${\displaystyle r_{k+1}=r_{k-1}-q_{k}\cdot r_{k}}$ ${\displaystyle s_{k+1}=s_{k-1}-q_{k}\cdot s_{k}}$
• until applies. ${\displaystyle r_{k+1}=0}$
• Give the rest and the number of returns. ${\displaystyle r_{k}=\operatorname {ggT} (a,b)}$ ${\displaystyle s_{k}}$ ${\displaystyle \operatorname {ggT} (a,b)\equiv s_{k}\cdot a{\pmod {b}}}$

Each step implicitly also contains a multiplier , whereby this division leaves no remainder. The sequence can also be determined explicitly , and ${\displaystyle t_{k}=(r_{k}-s_{k}\cdot a)\div b}$ ${\displaystyle (t_{k})_{k}}$ ${\displaystyle t_{0}=0}$ ${\displaystyle t_{1}=1}$

${\displaystyle t_{k-1}\equiv q_{k}\cdot t_{k}+t_{k+1}}$.

After the last step it now results ${\displaystyle \operatorname {ggT} (a,b)=s_{k}\cdot a+t_{k}\cdot b}$

For the sake of clarity, the auxiliary sequences and and and are also carried along with manual calculations . ${\displaystyle (a_{k}=r_{k-1})_{k}}$ ${\displaystyle (b_{k}=r_{k})_{k}}$ ${\displaystyle (u_{k}=s_{k-1})_{k}}$ ${\displaystyle (v_{k}=t_{k-1})_{k}}$

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')  ${\displaystyle \leftarrow }$ extended_euclid(b, a mod b)
4  (d,s,t)  ${\displaystyle \leftarrow }$ (d',t',s' – (a div b)t')
5  return (d,s,t)

The following mathematical function definition with case distinction is synonymous:

${\displaystyle \operatorname {extended\_euclid} (a,b)={\begin{cases}(a,1,0)&{\text{wenn }}b=0\\(d',t',s'-t'(a{\text{ div }}b))&{\text{mit }}(d',s',t')=\operatorname {extended\_euclid} (b,a\ {\text{mod}}\ b)\end{cases}}}$

Tricks for Efficient Computer Implementation

Representation of the number of loop iterations for two numbers and , for which the simple implementation of the extended Euclidean algorithm was used. ${\displaystyle m}$ ${\displaystyle n}$

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 , ${\displaystyle k}$ ${\displaystyle m_{k}=n_{k}\cdot q_{k}+r_{k}}$ ${\displaystyle \,m_{k+1}=n_{k}}$ ${\displaystyle \,n_{k+1}=r_{k}=m_{k}-q_{k}\cdot n_{k}}$ ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle {\begin{pmatrix}m_{k+1}\\n_{k+1}\end{pmatrix}}={\begin{pmatrix}0&1\\1&-q_{k}\end{pmatrix}}\cdot {\begin{pmatrix}m_{k}\\n_{k}\end{pmatrix}}}$.

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 , ${\displaystyle L}$ ${\displaystyle \,n_{L+1}=r_{L}=0}$ ${\displaystyle \,m_{L+1}=n_{L}=\operatorname {ggT} (a,b)}$

${\displaystyle {\begin{pmatrix}\operatorname {ggT} (a,b)\\0\end{pmatrix}}={\begin{pmatrix}0&1\\1&-q_{L}\end{pmatrix}}\cdot \ldots \cdot {\begin{pmatrix}0&1\\1&-q_{1}\end{pmatrix}}\cdot {\begin{pmatrix}a\\b\end{pmatrix}}}$.

By multiplying by the row vector , the first row on both sides is extracted, so the following applies ${\displaystyle (1,0)}$

${\displaystyle \operatorname {ggT} (a,b)={\begin{pmatrix}1&0\end{pmatrix}}\cdot {\begin{pmatrix}0&1\\1&-q_{L}\end{pmatrix}}\cdot \ldots \cdot {\begin{pmatrix}0&1\\1&-q_{1}\end{pmatrix}}\cdot {\begin{pmatrix}a\\b\end{pmatrix}}}$.

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 ${\displaystyle (s_{1},t_{1})=(1,0)}$

${\displaystyle (s_{k+1},t_{k+1})=(s_{k},t_{k}){\begin{pmatrix}0&1\\1&-q_{L+1-k}\end{pmatrix}}}$ For ${\displaystyle k=1,\ldots ,L}$

certainly. In the end it applies . However, all quotients must first be determined before the first recursion step can be carried out. ${\displaystyle \,\operatorname {ggT} (a,b)=s_{L+1}a+t_{L+1}b}$

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

${\displaystyle {\begin{pmatrix}s_{1}&t_{1}\\u_{1}&v_{1}\end{pmatrix}}=I_{2}={\begin{pmatrix}1&0\\0&1\end{pmatrix}}}$set and for ${\displaystyle {\begin{pmatrix}s_{k+1}&t_{k+1}\\u_{k+1}&v_{k+1}\end{pmatrix}}={\begin{pmatrix}0&1\\1&-q_{k}\end{pmatrix}}\cdot {\begin{pmatrix}s_{k}&t_{k}\\u_{k}&v_{k}\end{pmatrix}}}$ ${\displaystyle k=1,\ldots ,L}$

is iterated. Overall, this results

${\displaystyle {\begin{pmatrix}s_{L+1}&t_{L+1}\\u_{L+1}&v_{L+1}\end{pmatrix}}={\begin{pmatrix}0&1\\1&-q_{L}\end{pmatrix}}\cdot \ldots \cdot {\begin{pmatrix}0&1\\1&-q_{1}\end{pmatrix}}}$.

In the end, the following applies , although the last iteration step can also be omitted because of the relationships and ${\displaystyle \,\operatorname {ggT} (a,b)=s_{L+1}a+t_{L+1}b}$ ${\displaystyle \,s_{L+1}=u_{L}}$ ${\displaystyle \,t_{L+1}=v_{L}}$

Web links

• Ulm University: "Elementary Number Theory" [1]
• Java applet with step-by-step execution and an understandable summary explanation
• Online tool for calculating the greatest common factor
• Iterative variant in Java (source code)
• JavaScript calculator with calculation details and intermediate steps
• Video: Extended Euclidean Algorithm Part 1 . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19885 .
• Video: Extended Euclidean Algorithm Part 2 . Heidelberg University of Education (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19886 .
• Video: Extended Euclidean Algorithm Part 3 . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19887 .

Individual evidence

1. ^ 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 .