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