Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ax + by = \gcd(a, b)} ; it is generally denoted as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{xgcd}(a, b)} .

This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor.

Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout's identity of two univariate polynomials.

The extended Euclidean algorithm is particularly useful when a and b are coprime. With that provision, x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non-prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method.

Description

The standard Euclidean algorithm proceeds by a succession of Euclidean divisions whose quotients are not used. Only the remainders are kept. For the extended algorithm, the successive quotients are used. More precisely, the standard Euclidean algorithm with a and b as input, consists of computing a sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_1,\ldots, q_k} of quotients and a sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_0,\ldots, r_{k+1}} of remainders such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} r_0 & =a \\ r_1 & =b \\ & \,\,\,\vdots \\ r_{i+1} & =r_{i-1}-q_i r_i \quad \text {and} \quad 0\le r_{i+1} < |r_i| \quad\text{(this defines }q_i)\\ & \,\,\, \vdots \end{align} }

It is the main property of Euclidean division that the inequalities on the right define uniquely Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{i+1}} from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{i-1}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{i}.}

The computation stops when one reaches a remainder Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k+1}} which is zero; the greatest common divisor is then the last nonzero remainder Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}.}

The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} r_0 & =a & r_1 & =b \\ s_0 & =1 & s_1 & =0 \\ t_0 & =0 & t_1 & =1 \\ & \,\,\,\vdots & & \,\,\,\vdots \\ r_{i+1} & =r_{i-1}-q_i r_i & \text {and } 0 & \le r_{i+1} < |r_i| & \text{(this defines } q_i \text{)}\\ s_{i+1} & =s_{i-1}-q_i s_i \\ t_{i+1} & =t_{i-1}-q_i t_i \\ & \,\,\, \vdots \end{align} }

The computation also stops when Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r_{k+1}=0} and gives

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_k} is the greatest common divisor of the input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=r_0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=r_1.}
• The Bézout coefficients are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_k} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_k,} that is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)=r_k=as_k+bt_k}
• The quotients of a and b by their greatest common divisor are given by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_{k+1}=\pm\frac{b}{\gcd(a,b)}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_{k+1}=\mp\frac{a}{\gcd(a,b)}} (the sign Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mp} is opposite to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pm} ).

Moreover, if a and b are both positive and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)\neq\min(a,b)} , then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |s_i| \leq \left\lfloor\frac{b}{2\gcd(a,b)}\right\rfloor\quad \text{and} \quad |t_i| \leq \left\lfloor\frac{a}{2\gcd(a,b)}\right\rfloor}

for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\leq i \leq k,} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor x\rfloor} denotes the integral part of x, that is the greatest integer not greater than x.

This implies that the pair of Bézout's coefficients provided by the extended Euclidean algorithm is the minimal pair of Bézout coefficients, as being the unique pair satisfying both above inequalities.

It also means that if a and b fit into an unsigned integer data type, a computer program can compute the Bézout coefficients in the corresponding signed integer type without integer overflow.

Examples

The following table shows how the extended Euclidean algorithm proceeds with input 240 and 46. The greatest common divisor is the last nonzero entry, 2 in the column "remainder". The computation stops at row 6, because the remainder in it is 0. Bézout coefficients appear in the last two columns of the second-to-last row. In fact, it is easy to verify that Template:Magenta × 240 + Template:Magenta × 46 = 2. Finally the last two entries Template:Cyan and Template:Cyan of the last row are, up to the sign, the quotients of the input 46 and 240 by the greatest common divisor 2.

index i	Quotient qi−1	Template:Olive	Template:Brown	ti
0		240	Template:Brown	0
1		46	Template:Brown	1
2	240 ÷ 46 = 5	240 − 5 × 46 = Template:Olive	Template:Brown − 5 × Template:Brown = Template:Brown	0 − 5 × 1 = −5
3	46 ÷ Template:Olive = 4	46 − 4 × Template:Olive = Template:Olive	Template:Brown − 4 × Template:Brown = Template:Brown	1 − 4 × −5 = 21
4	Template:Olive ÷ Template:Olive = 1	Template:Olive − 1 × Template:Olive = Template:Olive	Template:Brown − 1 × Template:Brown = Template:Brown	−5 − 1 × 21 = −26
5	Template:Olive ÷ Template:Olive = 1	Template:Olive − 1 × Template:Olive = 2	Template:Brown − 1 × Template:Brown = Template:Magenta	21 − 1 × −26 = Template:Magenta
6	Template:Olive ÷ Template:Olive = 2	Template:Olive − 2 × Template:Olive = 0	Template:Brown − 2 × Template:Brown = Template:Cyan	−26 − 2 × 47 = Template:Cyan

The following example uses a more compact notation. The greatest common divisor of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = 68} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = 30} can be calculated like this:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = \mathrm{gcd}\underset{\color{Green}\scriptstyle\;\;^\uparrow\!\!-\!-\!(-2)}{(68,30)} = \mathrm{gcd}\underset{\color{Green}\scriptstyle\!(-3)\!-\!\!-\!^\uparrow\;\;}{(8,30)} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle = \mathrm{gcd}\underset{\color{Green}\scriptstyle\;^\uparrow\!\!-\!\!-\!(-1)\!\!}{(8,\,6)} = \mathrm{gcd}\underset{\color{Green}\scriptstyle\!\!(-3)\!-\!\!-\!^\uparrow\;}{(2,\,6)} = \mathrm{gcd}(2,0) = 2, }

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \color{Green}\scriptstyle\,^\uparrow\!\!-\!-\!(-2)} in the first step means that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -2} times Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 30} is added to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 68} (the gcd does not change when adding a multiple of one number to the other).

Extended Euclidean algorithm for 𝑔 = gcd(68,30)

Extended Euclidean algorithm for 𝑔 = gcd(68,30)

Applying the green-indicated additions of multiples analogously to equations, starting with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = 1a + 0b} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = 0a + 1b,} leads to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = 4a - 9b,} according to the adjacent calculations (the corresponding table far right uses row operations).

Proof

Since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\le r_{i+1}<|r_i|} , the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i } is a strictly decreasing sequence of non-negative integers, for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\geq2} . Thus, it must stop with some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k+1}=0} . This proves that the algorithm stops, eventually.

From the equation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{i+1}=r_{i-1}-r_i q_i} it follows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(r_{i-1}, r_i)=\gcd(r_{i}, r_{i+1})} . As a consequence, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)=\gcd(r_0, r_1)=\gcd(r_k, r_{k+1})=\gcd(r_k,0)=r_k} . Until this point, the proof is the same as that of the classical Euclidean algorithm.

The recurrence relations, for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\geq0} ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases}r_{i}&=as_i+bt_i\\(-1)^i&=s_it_{i+1}-t_is_{i+1}\end{cases}}

can be proven by induction. In fact, for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=0} they reduce to

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} r_0&=a=as_0+bt_0\\ 1&=(-1)^0=1\cdot1-0\cdot0=s_0t_1-t_0s_1 \end{cases} }

Assuming they are satisfied for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , the equations for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i+1} follow from the computation

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} r_{i+1}&= r_{i-1} - r_i q_i = (as_{i-1}+bt_{i-1}) - (as_i+bt_i)q_i = (as_{i-1}-as_iq_i) + (bt_{i-1}-bt_iq_i) = as_{i+1}+bt_{i+1}\\ (-1)^{i+1}&=-(s_it_{i+1}-t_{i}s_{i+1})=s_{i+1}(t_{i}-q_{i+1}t_{i+1})-t_{i+1}(s_i-q_{i+1}s_{i+1})=s_{i+1}t_{i+2}-t_{i+1}s_{i+2} \end{cases} }

In particular, the equation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_it_{i+1}-t_is_{i+1}=(-1)^i} shows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_{k+1}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_{k+1}} are coprime.

Multiplying Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0=r_{k+1}=as_{k+1}+bt_{k+1}} by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_k} , it implies that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0=as_{k+1}s_k+bt_{k+1}s_k=as_{k+1}s_k+b((-1)^k+t_ks_{k+1})}

Therefore, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=(-1)^{k+1}(t_k-as_k)s_{k+1}} , from where it follows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_{k+1}} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} . As a consequence, there is an integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=ds_{k+1}} . Dividing by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_{k+1}} the relation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle as_{k+1}+bt_{k+1}=0} gives Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=-dt_{k+1}.} Hence, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_{k+1}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -t_{k+1}} are coprime integers that are the quotients of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} by a common factor, which is thus their greatest common divisor or its opposite.

To prove the last assertion, assume that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} are both positive and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)\neq\min(a,b)} . Then, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \neq b } , and if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < b} , it can be seen that the s and t sequences for (a,b) under the EEA are, up to initial 0s and 1s, the t and s sequences for (b,a). The definitions then show that the (a,b) case reduces to the (b,a) case. So assume that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a > b} without loss of generality.

It can be seen that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_2} is 1 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_3} (which exists by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)\neq\min(a,b)} ) is a negative integer. Thereafter, the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} alternate in sign and strictly increase in magnitude, which follows inductively from the definitions and the fact that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_i\geq 1} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \leq i \leq k} , the case Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = 1} holds because Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a > b} . The same is true for the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} after the first few terms, for the same reason. Furthermore, it is easy to see that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_k \geq 2} (when a and b are both positive and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)\neq\min(a,b)} ). Thus, noticing that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |s_{k+1}| = |s_{k-1}| + q_k |s_k|} , we obtain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |s_{k+1}|=\left |\frac{b}{\gcd(a,b)} \right | \geq 2|s_k| \qquad \text{and} \qquad |t_{k+1}|= \left |\frac{a}{\gcd(a,b)} \right | \geq 2|t_k|.}

This, accompanied by the fact that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_k,t_k} are larger than or equal to in absolute value than any previous Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} respectively completed the proof.

Polynomial extended Euclidean algorithm

See also: Polynomial greatest common divisor § Bézout's identity and extended GCD algorithm

For univariate polynomials with coefficients in a field, everything works similarly, Euclidean division, Bézout's identity and extended Euclidean algorithm. The first difference is that, in the Euclidean division and the algorithm, the inequality Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\le r_{i+1}<|r_i|} has to be replaced by an inequality on the degrees Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \deg r_{i+1}<\deg r_i.} Otherwise, everything which precedes in this article remains the same, simply by replacing integers by polynomials.

A second difference lies in the bound on the size of the Bézout coefficients provided by the extended Euclidean algorithm, which is more accurate in the polynomial case, leading to the following theorem.

If a and b are two nonzero polynomials, then the extended Euclidean algorithm produces the unique pair of polynomials (s, t) such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle as+bt=\gcd(a,b)}

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \deg s < \deg b - \deg (\gcd(a,b)), \quad \deg t < \deg a - \deg (\gcd(a,b)).}

A third difference is that, in the polynomial case, the greatest common divisor is defined only up to the multiplication by a nonzero constant. There are several ways to define unambiguously a greatest common divisor.

In mathematics, it is common to require that the greatest common divisor be a monic polynomial. To get this, it suffices to divide every element of the output by the leading coefficient of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}.} This allows that, if a and b are coprime, one gets 1 in the right-hand side of Bézout's inequality. Otherwise, one may get any nonzero constant. In computer algebra, the polynomials commonly have integer coefficients, and this way of normalizing the greatest common divisor introduces too many fractions to be convenient.

The second way to normalize the greatest common divisor in the case of polynomials with integer coefficients is to divide every output by the content of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k},} to get a primitive greatest common divisor. If the input polynomials are coprime, this normalisation also provides a greatest common divisor equal to 1. The drawback of this approach is that a lot of fractions should be computed and simplified during the computation.

A third approach consists in extending the algorithm of subresultant pseudo-remainder sequences in a way that is similar to the extension of the Euclidean algorithm to the extended Euclidean algorithm. This allows that, when starting with polynomials with integer coefficients, all polynomials that are computed have integer coefficients. Moreover, every computed remainder Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i} is a subresultant polynomial. In particular, if the input polynomials are coprime, then the Bézout's identity becomes

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle as+bt=\operatorname{Res}(a,b),}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{Res}(a,b)} denotes the resultant of a and b. In this form of Bézout's identity, there is no denominator in the formula. If one divides everything by the resultant one gets the classical Bézout's identity, with an explicit common denominator for the rational numbers that appear in it.

Pseudocode

In this section and the following ones, div is an auxiliary function that computes the quotient of the Euclidean division of its left argument by its right argument.

To implement the algorithm that is described above, one should first remark that only the two last values of the indexed variables are needed at each step. Thus, for saving memory, each indexed variable must be replaced by just two variables.

For simplicity, the following algorithm (and the other algorithms in this article) uses parallel assignments. In a programming language which does not have this feature, the parallel assignments need to be simulated with an auxiliary variable. For example, the first one,

(old_r, r) := (r, old_r - quotient × r)

is equivalent to

prov := r;
r := old_r - quotient × prov;
old_r := prov;

and similarly for the other parallel assignments. This leads to the following code:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

The quotients of a and b by their greatest common divisor, which is output, may have an incorrect sign. This is easy to correct at the end of the computation but has not been done here for simplifying the code. Similarly, if either a or b is zero and the other is negative, the greatest common divisor that is output is negative, and all the signs of the output must be changed.

Finally, notice that in Bézout's identity, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ax + by = \gcd(a, b)} , one can solve for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a, b, x, \gcd(a, b)} . Thus, an optimization to the above algorithm is to compute only the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_k} sequence (which yields the Bézout coefficient Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ), and then compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} at the end:

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

However, in many cases this is not really an optimization: whereas the former algorithm is not susceptible to overflow when used with machine integers (that is, integers with a fixed upper bound of digits), the multiplication of old_s × a in computation of bezout_t can overflow, limiting this optimization to inputs which can be represented in less than half the maximal size. When using integers of unbounded size, the time needed for multiplication and division grows quadratically with the size of the integers. This implies that the "optimisation" replaces a sequence of multiplications/divisions of small integers by a single multiplication/division, which requires more computing time than the operations that it replaces, taken together.

Simplification of fractions

A fraction a/b is in canonical simplified form if a and b are coprime and b is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by

if s = 0 then output "Division by zero"
if s < 0 then s := −s;  t := −t   (for avoiding negative denominators)
if s = 1 then output −t        (for avoiding denominators equal to 1)
output −t/s

The proof of this algorithm relies on the fact that s and t are two coprime integers such that as + bt = 0, and thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{a}{b} = -\frac{t}{s}} . To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.

If b divides a evenly, the algorithm executes only one iteration, and we have s = 1 at the end of the algorithm. It is the only case where the output is an integer.

Computing multiplicative inverses in modular structures

The extended Euclidean algorithm is the essential tool for computing multiplicative inverses in modular structures, typically the modular integers and the algebraic field extensions. A notable instance of the latter case are the finite fields of non-prime order.

Modular integers

Main article: Modular arithmetic

If n is a positive integer, the ring Z/nZ may be identified with the set {0, 1, ..., n-1} of the remainders of Euclidean division by n, the addition and the multiplication consisting in taking the remainder by n of the result of the addition and the multiplication of integers. An element a of Z/nZ has a multiplicative inverse (that is, it is a unit) if it is coprime to n. In particular, if n is prime, a has a multiplicative inverse if it is not zero (modulo n). Thus Z/nZ is a field if and only if n is prime.

Bézout's identity asserts that a and n are coprime if and only if there exist integers s and t such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ns+at=1}

Reducing this identity modulo n gives

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle at \equiv 1 \mod n.}

Thus t, or, more exactly, the remainder of the division of t by n, is the multiplicative inverse of a modulo n.

To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of n is not needed, and thus does not need to be computed. Also, for getting a result which is positive and lower than n, one may use the fact that the integer t provided by the algorithm satisfies |t| < n. That is, if t < 0, one must add n to it at the end (an example can be found in the article Modular multiplicative inverse). This results in the pseudocode, in which the input n is an integer larger than 1.

function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Simple algebraic field extensions

The extended Euclidean algorithm is also the main tool for computing multiplicative inverses in simple algebraic field extensions. An important case, widely used in cryptography and coding theory, is that of finite fields of non-prime order. In fact, if p is a prime number, and q = p^d, the field of order q is a simple algebraic extension of the prime field of p elements, generated by a root of an irreducible polynomial of degree d.

A simple algebraic extension L of a field K, generated by the root of an irreducible polynomial p of degree d may be identified to the quotient ring Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K[X]/\langle p\rangle,} , and its elements are in bijective correspondence with the polynomials of degree less than d. The addition in L is the addition of polynomials. The multiplication in L is the remainder of the Euclidean division by p of the product of polynomials. Thus, to complete the arithmetic in L, it remains only to define how to compute multiplicative inverses. This is done by the extended Euclidean algorithm.

The algorithm is very similar to that provided above for computing the modular multiplicative inverse. There are two main differences: firstly the last but one line is not needed, because the Bézout coefficient that is provided always has a degree less than d. Secondly, the greatest common divisor which is provided, when the input polynomials are coprime, may be any nonzero element of K; this Bézout coefficient (a polynomial generally of positive degree) has thus to be multiplied by the inverse of this element of K. In the pseudocode which follows, p is a polynomial of degree greater than one, and a is a polynomial.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Example

For example, if the polynomial used to define the finite field GF(2⁸) is p = x⁸ + x⁴ + x³ + x + 1, and a = x⁶ + x⁴ + x + 1 is the element whose inverse is desired, then performing the algorithm results in the computation described in the following table. Let us recall that in fields of order 2ⁿ, one has −z = z and z + z = 0 for every element z in the field). Since 1 is the only nonzero element of GF(2), the adjustment in the last line of the pseudocode is not needed.

step	quotient	r, newr	s, news	t, newt
		p = x8 + x4 + x3 + x + 1	1	0
		a = x6 + x4 + x + 1	0	1
1	x2 + 1	x2 = p − a (x2 + 1)	1	x2 + 1 = 0 − 1 · (x2 + 1)
2	x4 + x2	x + 1 = a − x2 (x4 + x2)	x4+x2 = 0 − 1(x4+x2)	x6 + x2 + 1 = 1 − (x4 + x2) (x2 + 1)
3	x + 1	1 = x2 − (x + 1) (x + 1)	x5+x4+x3+x2+1 = 1 − (x +1)(x4 + x2)	x7 + x6 + x3 + x = (x2 + 1) − (x + 1) (x6 + x2 + 1)
4	x + 1	0 = (x + 1) − 1 × (x + 1)	x6 + x4 + x + 1 = (x4+x2) − (x+1)(x5+x4+x3+x2+1)

Thus, the inverse is x⁷ + x⁶ + x³ + x, as can be confirmed by multiplying the two elements together, and taking the remainder by p of the result.

The case of more than two numbers

One can handle the case of more than two numbers iteratively. First we show that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b,c) = \gcd(\gcd(a,b),c)} . To prove this let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=\gcd(a,b,c)} . By definition of gcd Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} is a divisor of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} . Thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a,b)=k d} for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Similarly Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} is a divisor of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=jd} for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u=\gcd(k,j)} . By our construction of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ud | a,b,c} but since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} is the greatest divisor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} is a unit. And since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ud=\gcd(\gcd(a,b),c)} the result is proven.

So if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle na + mb = \gcd(a,b)} then there are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\gcd(a,b) + yc = \gcd(a,b,c)} so the final equation will be

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x(na + mb) + yc = (xn)a + (xm)b + yc = \gcd(a,b,c).\,}

So then to apply to n numbers we use induction

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd(a_1,a_2,\dots,a_n) =\gcd(a_1,\, \gcd(a_2,\, \gcd(a_3,\dots, \gcd(a_{n-1}\,,a_n))),\dots),}

with the equations following directly.

See also

• Euclidean domain
• Linear congruence theorem
• Kuṭṭaka

References

• Knuth, Donald. The Art of Computer Programming. Addison-Wesley. Volume 2, Chapter 4.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

External links

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)