Soient \(a\) et \(b\) deux nombres entiers relatifs. On note \(d\) leur pgcd. Construisons les suites \(a_n\) et \(b_n\) \(n \in \mathbb{N},\) à valeurs dans \(\mathbb{Z}\)de la manière suivante : \[\begin{aligned} a_0 &=& a\\ b_0 &=& b\\\end{aligned}\] et pour tout \(n \in \mathbb{N},\) on pose \(a_{n+1}= b_n\) et \(b_{n+1}= r\) où \(r\) est le reste de la division euclidienne de \(a_n\) par \(b_n.\)
Montrer que si \(d_n\) est le pgcd de \(a_n\) et \(b_n\) alors \(d_n\) est également le pgcd de \(a_{n+1}\) et \(b_{n+1}.\)
Déduire de la questionh précédente que \(d\) est le pgcd des nombres \(a_n\) et \(b_n\) pour tout \(n \in \mathbb{N}.\)
Montrer que la suite \(b_n\) est strictement décroissante. Que peut-on en déduire?
Déduire de ce qui précède que pour tout couple d’entiers relatifs \((a,b)\) il existe un couple d’entier relatifs \((u,v)\) tel que: \[d = au+bv.\]