Editing Extended Euclidean algorithm (section)

== Description==
The standard Euclidean algorithm proceeds by a succession of [[Euclidean division]]s 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 <math>q_1,\ldots, q_k</math> of quotients and a sequence <math>r_0,\ldots, r_{k+1}</math> of remainders such that 
:<math>
\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}
</math>
It is the main property of [[Euclidean division]] that the inequalities on the right define uniquely <math>q_i</math> and <math>r_{i+1}</math> from <math>r_{i-1}</math> and <math>r_{i}.</math>

The computation stops when one reaches a remainder <math>r_{k+1}</math> which is zero; the greatest common divisor is then the last non zero remainder <math>r_{k}.</math>

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

:<math>
\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}
</math>

The computation also stops when <math>r_{k+1}=0</math> and gives 
*<math>r_k</math> is the greatest common divisor of the input <math>a=r_0</math> and <math>b=r_1.</math>
* The Bézout coefficients are <math>s_k</math> and <math>t_k,</math> that is <math>\gcd(a,b)=r_k=as_k+bt_k</math>
* The quotients of ''a'' and ''b'' by their greatest common divisor are given  by <math>s_{k+1}=\pm\frac{b}{\gcd(a,b)}</math> and <math>t_{k+1}=\pm\frac{a}{\gcd(a,b)}</math>

Moreover, if ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>, then 
:<math>|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</math>
for <math>0\leq i \leq k,</math> where <math>\lfloor x\rfloor</math> denotes the [[integral part]] of {{mvar|x}}, that is the greatest integer not greater than {{mvar|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 the algorithm can be done without [[integer overflow]] by a [[computer program]] using integers of a fixed size that is larger than that of ''a'' and ''b''.

=== Example ===

The following table shows how the extended Euclidean algorithm proceeds with input {{nowrap|{{green|240}}}} and {{nowrap|{{green|46}}}}. The greatest common divisor is the last non zero entry, {{nowrap|{{red|2}}}} in the column "remainder". The computation stops at row 6, because the remainder in it is {{nowrap|{{red|0}}}}. Bézout coefficients appear in the last two columns of the second-to-last row. In fact, it is easy to verify that {{nowrap|1={{magenta|−9}} × {{green|240}} + {{magenta|47}} × {{green|46}} = {{red|2}}}}. Finally the last two entries  {{nowrap|{{cyan|23}}}} and {{nowrap|{{cyan|−120}}}} of the last row are, up to the sign, the quotients of the input {{nowrap|{{green|46}}}} and {{nowrap|{{green|240}}}} by the greatest common divisor {{nowrap|{{red|2}}}}.

{| class="wikitable" style="text-align:right;"
! index ''i''!! {{blue|quotient ''q''<sub>''i''−1</sub> }}!! {{olive|Remainder ''r''<sub>''i''</sub>}}!! {{brown|''s''<sub>''i''</sub> }}!! ''t''<sub>''i''</sub>
|-
| 0 || ||{{green|240}}||{{brown|1}} || 0
|-
| 1 || 
||{{green|46}} || {{brown|0}} || 1
|-
| 2 ||{{green|240}} ÷ {{green|46}} = {{blue|5}}
||{{green|240}} − {{blue|5}} × {{green|46}} = {{olive|10}}
||{{brown|1}} − {{blue|5}} × {{brown|0}} = {{brown|1}}
|| 0 − {{blue|5}} × 1 = −5
|-
| 3 ||{{green|46}} ÷ {{olive|10}} = {{blue|4}}
||{{green|46}} − {{blue|4}} × {{olive|10}} = {{olive|6}}
||{{brown|0}} − {{blue|4}} × {{brown|1}} = {{brown|−4}}
|| 1 − {{blue|4}} × −5 = 21
|-
| 4 ||{{olive|10}} ÷ {{olive|6}} = {{blue|1}}
||{{olive|10}} − {{blue|1}} × {{olive|6}} = {{olive|4}}
||{{brown|1}} − {{blue|1}} × {{brown|−4}} = {{brown|5}}
|| −5 − {{blue|1}} × 21 = −26
|-
| 5 ||{{olive|6}} ÷ {{olive|4}} = {{blue|1}}
||{{olive|6}} − {{blue|1}} × {{olive|4}} = {{red|2}}
||{{brown|−4}} − {{blue|1}} × {{brown|5}} = {{magenta|−9}}
|| 21 − {{blue|1}} × −26 = {{magenta|47}}
|-
| 6 ||{{olive|4}} ÷ {{olive|2}} = {{blue|2}}
||{{olive|4}} − {{blue|2}} × {{olive|2}} = {{red|0}}
||{{brown|5}} − {{blue|2}} × {{brown|−9}} = {{cyan|23}}
|| −26 − {{blue|2}} × 47 = {{cyan|−120}}
|}

=== Proof ===
As <math> 0\le r_{i+1}<|r_i|, </math> the sequence of the <math> r_i </math> is a decreasing sequence of nonnegative integers (from ''i'' = 2 on). Thus it must stop with some <math> r_{k+1}=0.</math> This proves that the algorithm stops eventually.

As <math> r_{i+1}= r_{i-1} - r_i q_i,</math> the greatest common divisor is the same for <math>(r_{i-1}, r_i)</math>  and <math>(r_{i}, r_{i+1}).</math> This shows that the greatest common divisor of the input <math>a=r_0, b=r_1 </math> is the same as that of <math> r_k, r_{k+1}=0.</math> This proves that <math> r_k </math> is the greatest common divisor of ''a'' and ''b''. (Until this point, the proof is the same as that of the classical Euclidean algorithm.)

As <math> a=r_0</math> and <math> b=r_1,</math> we have <math>as_i+bt_i=r_i</math> for ''i'' = 0 and 1. The relation follows by induction for all <math>i>1</math>:
<math display="block">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}.</math>

Thus <math>s_k</math> and <math>t_k</math> are Bézout coefficients.

Consider the matrix
<math display="block">A_i=\begin{pmatrix} s_{i-1} & s_i\\ t_{i-1} & t_i \end{pmatrix}.</math>

The recurrence relation may be rewritten in matrix form
<math display="block">A_{i+1} = A_i \cdot \begin{pmatrix} 0 & 1\\ 1 & -q_i \end{pmatrix}.</math>

The matrix <math>A_1</math> is the identity matrix and its determinant is one. The determinant of the rightmost matrix in the preceding formula is −1. It follows that the determinant of <math>A_i</math> is <math>(-1)^{i-1}.</math> In particular, for <math>i=k+1,</math> we have <math>s_k t_{k+1} - t_k s_{k+1} = (-1)^k.</math> Viewing this as a Bézout's identity, this shows that <math>s_{k+1}</math> and <math>t_{k+1}</math> are [[coprime]]. The relation <math>as_{k+1}+bt_{k+1}=0</math> that has been proved above and [[Euclid's lemma]] show that <math>s_{k+1}</math> divides {{mvar|b}}, that is that <math>b=ds_{k+1}</math> for some integer {{mvar|d}}. Dividing by <math>s_{k+1}</math> the relation <math>as_{k+1}+bt_{k+1}=0</math> gives <math>a=-dt_{k+1}.</math> So, <math>s_{k+1}</math> and <math>-t_{k+1}</math> are coprime integers that are the quotients of {{mvar|a}} and {{mvar|b}} by a common factor, which is thus their greatest common divisor or its [[additive inverse|opposite]].

To prove the last assertion, assume that ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>. Then, <math>a \neq b </math>, and  if <math>a < b</math>, 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 <math>a > b</math> [[without loss of generality]].

It can be seen that <math>s_2</math> is 1 and <math>s_3</math> (which exists by <math>\gcd(a,b)\neq\min(a,b)</math>) is a negative integer. Thereafter, the <math>s_i</math> alternate in sign and strictly increase in magnitude, which follows inductively from the definitions and the fact that <math>q_i\geq 1</math> for <math>1 \leq i \leq k</math>, the case <math>i = 1</math> holds because <math>a > b</math>. The same is true for the <math>t_i</math> after the first few terms, for the same reason. Furthermore, it is easy to see that <math>q_k \geq 2</math> (when ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>). Thus, noticing that <math>|s_{k+1}| = |s_{k-1}| + q_k |s_k|</math>, we obtain
<math display="block">|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|.</math>

This, accompanied by the fact that <math>s_k,t_k</math> are larger than or equal to in absolute value than any previous <math>s_i</math> or <math>t_i</math> respectively completed the proof.