Exercise 1.2.41 ($|x_{j+1}| = c/g$ and $|y_{j+1}| = b/g$)

Proof. The Euclidean algorithm makes sense only for $b\ge 0,c\ge 0$. The fraction $c∕g$ has no signification if $g=0$, so we may assume that $b$ and $c$ are not both zero, so that $g=b\wedge c\ne 0$.

(a)

Suppose first that $b>0$ and $c>0$, as in the hypothesis of Theorem 1.11.

If we write the relations $r_i=b{x}_i+y_{i}c$ for $i=j$ and $i=j+1$, we obtain

$$\{\begin{array}{cccc}g=\hfill & r_j\hfill & =b{x}_j\hfill & +c{y}_j,\hfill \\ 0=\hfill & r_{j+1}\hfill & =b{x}_{j+1}\hfill & +c{y}_{j+1}.\hfill \end{array}$$

Therefore

$$\begin{array}{llll}\hfill -x_{j+1}g& =c(x_j{y}_{j+1}-x_{j+1}{y}_j),& \hfill & \\ \hfill y_{j+1}g& =b(x_j{y}_{j+1}-x_{j+1}{y}_j).& \hfill & \end{array}$$

By Problem 40, $x_j{y}_{j+1}-x_{j+1}{y}_j={(-1)}^{j+1}$, so

$$\begin{array}{llll}\hfill {(-1)}^j{x}_{j+1}g& =c,& \hfill & \\ \hfill {(-1)}^{j+1}{y}_{j+1}g& =b.& \hfill & \end{array}$$

By Problem 39, $|x_{j+1}|={(-1)}^j{x}_{j+1}$, $|y_{j+1}|={(-1)}^{j+1}{y}_{j+1}$, thus

$$|x_{j+1}|=\frac{c}{g},|y_{j+1}|=\frac{b}{g}.$$

(b)

The extended Euclidean algorithm (or Bézout algorithm) gives (see Problem 39) $$r_{-1}=b,r_0=c,r_{j+1}=0,$$

Then $x_i$ and $y_i$, such that $r_i=b{x}_i+c{y}_i,-1\le i\le j+1$, satisfy for all $i\in [[-1,j-1]]$,

$$\begin{array}{lll}\hfill r_{i+2}& =r_i-q_{i+2}{r}_{i+1},& \hfill \text{(1)}\\ \hfill x_{i+2}& =x_i-q_{i+2}{x}_{i+1},& \hfill \text{(2)}\\ \hfill y_{i+2}& =y_i-q_{i+2}{y}_{i+1},& \hfill \text{(3)}\end{array}$$

where

$$\begin{array}{cc}\hfill x_{-1}=1,& \hfill y_{-1}=0,\\ \hfill x_0=0,& \hfill y_0=1,\end{array}$$

• If $b=0$, then $g=a\wedge c=0\wedge c=c$ (and $c\ne 0$), and the Euclidean algorithm gives

  $$\begin{array}{llll}\hfill 0& =c{q}_1+r_1,q_1=0,r_1=0,& \hfill & \end{array}$$

  so that $j=0$. Then

  $$\begin{array}{llll}\hfill x_{j+1}& =x_1=x_{-1}-q_1{x}_0=1,& \hfill & \\ \hfill y_{j+1}=y_1=y_{-1}-q_1{y}_0=0,& & \hfill \end{array}$$

  thus

  $$|x_{j+1}|=|x_1|=1=c∕g,|y_{j+1}|=|y_1|=0=b∕g.$$

• If $c=0$, then $g=b\wedge c=b$. There are no Euclidean division, the algorithm doesn’t enter in the loop (see the note). Since $r_0=0=r_{j+1}$, we have $j=-1$, and

  $$\begin{array}{llll}\hfill x_{j+1}& =x_0=0,& \hfill & \\ \hfill y_{j+1}& =y_0=1,& \hfill & \end{array}$$

  thus

  $$|x_{j+1}|=|x_0|=0=c∕g,|y_{j+1}|=|y_0|=1=b∕g.$$