Exercise 1.4

Proof. With a slight modification of the notations of exercise 2, we note the Euclid’s algorithm under the form

We show by induction on $i$ ( $i\le k+1$) the proposition

$\text{∙}$ $r_0=a=1.a+0.b$. Define $m_0=1,n_0=0$. We obtain $r_0=a{m}_0+b{n}_0$, then $P(0)$ is true.

$r_1=b=0.a+1.b$. Define $m_1=0,n_1=1$. We obtain $r_1=a{m}_1+b{n}_1$, then $P(1)$ is true.

$\text{∙}$ Suppose for $0\le i<k$ the induction hypothesis $P(i)$ et $P(i+1)$ :

Then $r_{i+2}=r_i-r_{i+1}{q}_{i+1}=a(m_i-q_{i+1}{m}_{i+1})+b(n_i-q_{i+1}{n}_{i+1})$.

If we define $m_{i+1}=m_i-q_{i+1}{m}_{i+1},n_{i+1}=n_i-q_{i+1}{n}_{i+1}$, we obtain $r_{i+2}=a{m}_{i+2}+b{n}_{i+2},m_{i+2},n_{i+2}\in \mathbb{Z}$, so $P(i+2)$.

$\text{∙}$ The conclusion is that $P(i)$ is true for all $i,0\le i\le k+1$, in particular $r_{k+1}=a{m}_{k+1}+b{n}_{k+1}$, that is

where $m=m_{k+1},n=n_{k+1}\in \mathbb{Z}$. □