Pour $m=1$ et $n$ entier naturel quelconque :

$u_{n+m}=u_{n+1}=u_{n+1}u_1+u_nu_0=u_{n+1}u_m+u_{m-1}u_n.$

Pour $m=2$ et $n$ entier naturel quelconque :

$u_{n+m}=u_{n+2}=u_{n+1}+u_n=u_{n+1}u_2+u_nu_1=u_{n+1}u_m+u_{m-1}u_n.$

Soit $m\geq1$ . Supposons que pour tout entier naturel $n$ , on a $u_{n+m}=u_{n+1}u_m+u_{m-1}u_n$ et $u_{n+m+1}=u_{n+1}u_{m+1}+u_mu_n$ . Alors, pour tout entier naturel $n$ ,

$\begin{align*}\ensuremath u_{n+m+2}&=u_{n+m+1}+u_{n+m}=u_{n+1}u_{m+1}+u_mu_n+u_{n+1}u_m+u_{m-1}u_n\;(\mbox{par hypothèse de récurrence})\\ &=u_{n+1}(u_{m+1}+u_m)+u_n(u_m+u_{m-1})=u_{n+1}u_{m+2}+u_nu_{m+1}. \end{align*}$

ce qui démontre l’égalité proposée par récurrence.

Soient $n$ et $m$ deux entiers naturels tels que $n\geq m$ . La division euclidienne de $n$ par $m$ s’écrit $n=mq+r$ avec $q$ et $r$ entiers tels que $0\leq r\leq m-1$ .

Or, $u_{m+r}=u_mu_{r+1}+u_{m-1}u_r$ . Par suite, un diviseur commun à $u_m$ et $u_r$ divise encore $u_m$ et $u_{m+r}$ et réciproquement un diviseur commun à $u_m$ et $u_{m+r}$ divise $u_{m-1}u_r$ . Mais, $u_m$ et $u_{m-1}$ sont premiers entre eux et, d’après le théorème de Gauss, un diviseur commun à $u_m$ et $u_{m+r}$ divise $u_r$ . Les diviseurs communs à $u_m$ et $u_r$ sont encore les diviseurs communs à $u_m$ et $u_{m+r}$ et donc :

$u_m\wedge u_r=u_m\wedge u_{m+r}.$

Puis, par récurrence

$u_m\wedge u_r=u_m\wedge u_{m+r}=u_m\wedge u_{2m+r}=...=u_m\wedge u_{qm+r}=u_m\wedge u_n.$

Ainsi, les algorithmes d’Euclide appliqués d’une part à $u_m$ et $u_n$ et d’autre part à $m$ et $n$ s’effectuent en parallèle et en particulier, $u_m\wedge u_n=u_{m\wedge n}.$

exo7 5302