Exercise 1.2.39 (Properties of Euclid's algorithm )

Proof. We put

so that the equations of Euclid’s algorithm are

Here $b>0,c>0,r_i>0$ thus $q_i\ge 0$ for all $i$.

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]]$,

• Note first that

  $$\begin{array}{llll}\hfill r_{-1}& =b=b\cdot 1+c\cdot 0,& \hfill & \\ \hfill r_0& =c=b\cdot 0+c\cdot 1,& \hfill & \end{array}$$

  thus

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

  and so

  $$\begin{array}{cccc}{(-1)}^{-1}{x}_{-1}\hfill & \hfill \le 0,& {(-1)}^{-1}{y}_{-1}\hfill & \hfill \ge 0,\\ {(-1)}^0{x}_0\hfill & \hfill \le 0,& {(-1)}^0{y}_0\hfill & \hfill \ge 0.\end{array}$$

• Reasoning by induction, suppose that for some $i\in [[-1,j-1]]$

  $$\begin{array}{cccc}{(-1)}^i{x}_i\hfill & \hfill \le 0,& {(-1)}^i{y}_i\hfill & \hfill \ge 0,\\ {(-1)}^{i+1}{x}_{i+1}\hfill & \hfill \le 0,& {(-1)}^{i+1}{y}_{i+1}\hfill & \hfill \ge 0.\end{array}$$

  Then (2) and (3) give, using ${(-1)}^{i+2}={(-1)}^i$ and $q_{i+2}\ge 0$,

  $$\begin{array}{llll}\hfill & {(-1)}^{i+2}{x}_{i+2}={(-1)}^i{x}_i+q_{i+2}{(-1)}^{i+1}{x}_{i+1}\le 0,& \hfill & \\ \hfill & {(-1)}^{i+2}{y}_{i+2}={(-1)}^i{y}_i+q_{i+2}{(-1)}^{i+1}{y}_{i+1}\ge 0.& \hfill & \\ \hfill & & \hfill \end{array}$$
• The induction is done, thus ${(-1)}^i{x}_i\le 0,{(-1)}^i{y}_i\ge 0$ are true for $-1\le i\le j+1$.

Since ${(-1)}^{i+1}{x}_i=|x_i|$, for $i\in [[-1,j+1]]$,

and similarly, ${(-1)}^i{y}_i=|y_i|$, thus

Equivalently,

for $i=0,1,\dots ,j$. □