If $d$ is the gcd of positive integers $a < b$, Bézout's theorem states that there are integers $t$ and $u$ such that $$d = ta + ub \;.$$
One can use the Euclidean algorithm for computing the gcd of $a$ and $b$ to compute suitable values for the "Bézout coefficients"1 $t$ and $s$.
More specifically, set $r_{-1} = b$ and $r_0 = a$, and suppose that, for some non-negative integer $n$, the Euclidean algorithm produces the following sequence of $n + 1$ equations:
$$
\begin{array}{rcl}
r_{-1} & = & r_0 q_0 + r_1 \\
\vdots & & \vdots \\
r_{i-1} & = & r_i q_i + r_{i+1} \\
\vdots & & \vdots \\
r_{n-2} & = & r_{n-1} q_{n-1} + r_n \\
r_{n-1} & = & r_n q_n
\end{array}
$$
…where
- the $q_i$ and $r_i$ are all positive integers;
- $r_{i-1} > r_i, \forall i \in \{0, \cdots, n\}$;
- $r_n = d$.
(The case $n = 0$ corresponds to the edge case where $a$ divides $b$, so $d = a$.)
One can eliminate $r_1, \cdots, r_{n-1}$ from this system of equations (actually, only the first $n$ equations are needed for this) to end up with an expression for $r_n = d$ as a linear combination of $r_0 = a$ and $r_{-1} = b$, with coefficients given as (possibly empty) sums of (possibly empty) products of the integers $q_i$.
Below are the coefficients $t$ and $u$ (of $r_0 = a$ and $r_{-1} = b$, respectively) in such linear combinations, for the first few values of $n$:
$$
\begin{array}{r|l|l}
n & t & u \\
\hline
0 & 1 & 0 \\
\hline
1 & -q_1 & 1 \\
\hline
2 & 1+q_1 q_2 & -q_2 \\
\hline
3 & -q_1-q_3-q_1 q_2 q_3 & 1+q_2 q_3 \\
\hline
4 & 1 + q_1 q_2 +q_1 q_4 +q_3 q_4 & -q_2-q_4 -q_2 q_3 q_4 \\
& + q_1 q_2 q_3 q_4 & \\
\hline
5 & -q_1 -q_3 -q_5
& 1 \\
& -q_1 q_2 q_3 -q_1 q_2 q_5 -q_1 q_4 q_5
& +q_2 q_3 +q_2 q_5 +q_4 q_5 \\
& -q_3 q_4 q_5 -q_1 q_2 q_3 q_4 q_5
& +q_2 q_3 q_4 q_5
\end{array}
$$
I have not been able to find a more direct way to compute these coefficients than to step-by-step work out the recurrence $$ r_{i+1} = r_{i-1} – r_i q_i$$ for $i$ from $0$ to $n-1$. Is there such?
I.e. is there a formula for the "Bézout coefficients" $t$ and $u$ in terms of the $n$ quotients $q_0, \cdots, q_{n-1}$ resulting from the Euclidean algorithm?
1 I came up with the term "Bézout coefficients". I have no reason to think it is at all standard.
Best Answer
$$ \gcd( 81201, 56660 ) = ??? $$
$$ \frac{ 81201 }{ 56660 } = 1 + \frac{ 24541 }{ 56660 } $$ $$ \frac{ 56660 }{ 24541 } = 2 + \frac{ 7578 }{ 24541 } $$ $$ \frac{ 24541 }{ 7578 } = 3 + \frac{ 1807 }{ 7578 } $$ $$ \frac{ 7578 }{ 1807 } = 4 + \frac{ 350 }{ 1807 } $$ $$ \frac{ 1807 }{ 350 } = 5 + \frac{ 57 }{ 350 } $$ $$ \frac{ 350 }{ 57 } = 6 + \frac{ 8 }{ 57 } $$ $$ \frac{ 57 }{ 8 } = 7 + \frac{ 1 }{ 8 } $$ $$ \frac{ 8 }{ 1 } = 8 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccc} & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 & & 8 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 10 }{ 7 } & & \frac{ 43 }{ 30 } & & \frac{ 225 }{ 157 } & & \frac{ 1393 }{ 972 } & & \frac{ 9976 }{ 6961 } & & \frac{ 81201 }{ 56660 } \end{array} $$ $$ $$ $$ 81201 \cdot 6961 - 56660 \cdot 9976 = 1 $$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
$$ \gcd( 144, 89 ) = ??? $$
$$ \frac{ 144 }{ 89 } = 1 + \frac{ 55 }{ 89 } $$ $$ \frac{ 89 }{ 55 } = 1 + \frac{ 34 }{ 55 } $$ $$ \frac{ 55 }{ 34 } = 1 + \frac{ 21 }{ 34 } $$ $$ \frac{ 34 }{ 21 } = 1 + \frac{ 13 }{ 21 } $$ $$ \frac{ 21 }{ 13 } = 1 + \frac{ 8 }{ 13 } $$ $$ \frac{ 13 }{ 8 } = 1 + \frac{ 5 }{ 8 } $$ $$ \frac{ 8 }{ 5 } = 1 + \frac{ 3 }{ 5 } $$ $$ \frac{ 5 }{ 3 } = 1 + \frac{ 2 }{ 3 } $$ $$ \frac{ 3 }{ 2 } = 1 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccc} & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 5 }{ 3 } & & \frac{ 8 }{ 5 } & & \frac{ 13 }{ 8 } & & \frac{ 21 }{ 13 } & & \frac{ 34 }{ 21 } & & \frac{ 55 }{ 34 } & & \frac{ 144 }{ 89 } \end{array} $$ $$ $$ $$ 144 \cdot 34 - 89 \cdot 55 = 1 $$ .............................................