Soient $a$ et $b$ deux entiers naturels non nuls. Vous définissez deux suites $(u_n)_{n\geq 0}$ et $(v_n)_{n\geq 0}$ par les conditions initiales $u_0=v_0=0$ et, pour tout entier naturel $n\comma$ par les relations de récurrence suivantes :

Vous allez démontrer que ces deux suites se rencontrent après leur valeur initiale une seule fois, et qu’à ce moment, leurs valeurs sont égales au $\ppcm$ des entiers $a$ et $b.$

Montrez que les deux suites précitées sont liées

Pour tout entier naturel $n\comma$ vous notez $\mathscr{P}(n)$ la propriété stipulant que $bu_n+av_n=abn.$

Initialisation. Pour $n=0\comma$ vous avez :

Ainsi, la propriété $\mathscr{P}(0)$ est vérifiée.

Hérédité. Soit $n$ un entier naturel tel que la propriété $\mathscr{P}(n)$ soit vérifiée.

Alors $bu_n+av_n = nab.$

Si $u_n \gt v_n\comma$ alors :

Si $u_n\leq v_n\comma$ alors :

Dans tous les cas, vous avez :

Donc la propriété $\mathscr{P}(n+1)$ est vérifiée.

Conclusion. Par récurrence, il vient d’être démontré que :

Montrez que l’ensemble des termes de la suite $(u_n)_{n\geq 0}$ est inclus dans l’ensemble des multiples de $a$

Pour tout entier naturel $n\comma$ vous notez $\mathscr{P}(n)$ la propriété stipulant qu’il existe un entier naturel $k$ tel que $u_n=ka.$

Initialisation. Pour $n=0\comma$ vous posez $k=0.$ Comme $u_0 = 0\comma$ il vient $u_0 = 0\times a\comma$ donc la propriété $\mathscr{P}(0)$ est vérifiée.

Hérédité. Soit $n$ un entier naturel tel que $\mathscr{P}(n)$ soit vraie.

Il existe un entier naturel $k$ tel que $u_n = ka.$

Si $u_n \gt v_n\comma$ alors $u_{n+1}=u_n.$ Or $u_n = ka$ donc $u_{n+1} = ka.$

Si $u_n\leq v_n\comma$ alors $u_{n+1}=u_n+a.$ Utilisant le fait que $u_n=ka\comma$ il vient $u_{n+1}=ka+a$ d’où $u_{n+1}=(k+1)a.$

Ainsi, la propriété $\mathscr{P}(n+1)$ est vérifiée.

Conclusion. Par récurrence, vous avez montré ce qui suit :

L’inclusion suivante est acquise :

Montrez que l’ensemble des termes de la suite $(v_n)_{n\geq 0}$ est inclus dans l’ensemble des multiples de $b$

Vous avez de même :

Pour démontrer ce résultat, la démarche est analogue à celle effectuée dans le paragraphe précédent.

Montrez qu’il existe un rang commun aux deux suites permettant d’atteindre le $\ppcm$ des nombres $a$ et $b$

Soit $\delta$ le $\ppcm$ des nombres $a$ et $b.$

Pour tout entier naturel $n\comma$ vous posez $w_n = \max(u_n,v_n).$

Soit $n$ un entier naturel. Partez de l’égalité $bu_n+av_n=abn.$ En majorant $u_n$ et $v_n$ par $w_n$ vous déduisez que :

Par conséquent, $w_n\geq \frac{ab}{a+b}n\comma$ ce qui prouve que $\lim_{n\to +\infty} w_n=+\infty.$ Ainsi, l’ensemble $A=\{n\in\N, w_n \gt \delta\}$ n’est pas vide.

Comme $A$ est une partie de $\N$ qui est non vide, elle admet un plus petit élément que vous notez $p.$

Par définition de $p\comma$ vous avez $p\in\N$ et $w_p \gt \delta.$ Or, $\delta$ est un entier naturel non nul donc $w_p\neq 0\comma$ ce qui prouve que $p$ est non nul.

Le nombre $p-1$ est un élément de $\N$ qui est strictement inférieur au minimum de $A\comma$ donc $p-1\notin A\comma$ d’où $w_{p-1}\leq \delta.$ Du coup, vous avez l’inégalité $w_{p-1}\leq \delta \lt w_p.$

Supposez que $u_{p-1} \gt v_{p-1}.$ Alors $u_p = u_{p-1}$ et $v_p = v_{p-1}+b.$ Vous avez $w_{p-1} = u_{p-1}.$ Si $w_p = u_p\comma$ alors $w_p = u_{p-1}.$ Donc $w_{p-1}\leq \delta \lt w_p$ s’écrit $u_{p-1}\leq \delta \lt u_{p-1}\comma$ ce qui est absurde. Donc $w_p = v_p.$ L’inégalité $w_{p-1}\leq \delta \lt w_p$ fournit $u_{p-1}\leq \delta \lt v_p.$ Comme $v_{p-1}\lt u_{p-1}$ vous avez $v_{p-1}\lt \delta \lt v_p$ et par suite $v_{p-1}\lt \delta \lt v_{p+1}+b.$ Comme $v_{p-1}$ est un multiple de $b$ tout comme $\delta\comma$ vous constatez que $\delta$ est strictement compris entre deux multiples consécutifs de $b\comma$ ce qui est impossible.

Donc vous avez $u_{p-1}\leq v_{p-1}.$ Alors $u_p = u_{p-1}+a$ et $v_p = v_{p-1}.$ Vous avez $w_{p-1} = v_{p-1}.$ Si $w_p = v_p\comma$ alors $w_p = v_{p-1}.$ Du coup, l’inégalité $w_{p-1}\leq \delta \lt w_p$ devient $v_{p-1}\leq \delta \lt v_{p-1}$ ce qui est impossible. Donc $w_p\neq v_p.$ Vous déduisez que $w_p = u_p.$ L’inégalité $w_{p-1}\leq \delta \lt w_p$ fournit $v_{p-1}\leq \delta \lt u_p.$ Or $u_{p-1}\leq v_{p-1}$ donc $u_{p-1}\leq \delta \lt u_p.$ Finalement, $u_{p-1}\leq \delta \lt u_{p-1}+a.$ Comme $u_{p-1}$ est un multiple de $a\comma$ vous constatez que $\delta$ est compris entre deux multiples de $a$ consécutifs. Comme $\delta$ est lui-même un multiple de $a\comma$ qui ne peut être égal à $u_{p-1}+a\comma$ il vient nécessairement $\delta = u_{p-1}.$ Compte tenu de ce résultat, l’inégalité $u_{p-1}\leq v_{p-1}$ s’écrit $\delta\leq v_{p-1}.$ Or, $v_{p-1}\leq \max(u_{p-1},v_{p-1})$ donc $v_{p-1}\leq w_{p-1}.$ Comme $w_{p-1}\leq \delta$ il vient $v_{p-1}\leq \delta.$ Du coup $\delta = v_{p-1}.$

Vous avez montré que :

Montrez l’unicité du rang commun aux deux suites pour lequel le $\ppcm$ des nombres $a$ et $b$ est atteint

Soit $r$ un entier naturel tel que $\delta = u_r = v_r.$

Partant de la relation $bu_r+av_r = abr\comma$ vous déduisez :

Du coup, $r = \frac{(a+b)\delta}{ab}.$ L’unicité de $r$ est démontrée.

Note. Comme $\delta = \frac{ab}{\pgcd(a,b)}\comma$ vous avez $r = \frac{a+b}{\pgcd(a,b)}.$

Utilisez l’algorithme sur un exemple

Prenez $a=15$ et $b=18.$

Vous obtenez successivement :

Vous observez que le premier rang non nul $n$ qui vérifie $u_n=v_n$ est $n=11.$ Cela vous fournit $90\comma$ qui est le $\ppcm$ de $15$ et de $18.$