074. A propos d’un algorithme sur le PPCM

Avec deux suites

Dans l’intégralité de cet article, $a$ et $b$ désignent deux entiers strictement positifs.

Pour déterminer leur PPCM, deux suites $(u_n)_{n\in\N}$ et $(v_n)_{n\in\N}$ sont définies par récurrence :

$
\left\{\begin{array}{l}
u_0 = 0,\\
v_0 = 0.
\end{array}\right.$

$\forall n\in\N, u_{n+1} =
\left\{\begin{array}{ll}
u_n & \text{ si }u_n> v_n\\
u_n+a& \text{ si } u_n \leq v_n
\end{array}\right.
$

$\forall n\in\N, v_{n+1} =
\left\{\begin{array}{ll}
v_n+b & \text{ si }u_n > v_n\\
v_n& \text{ si } u_n \leq v_n.
\end{array}\right.
$

L’objectif de cet article est d’étudier le comportement de ces deux suites. Vous verrez qu’elles sont à nouveau égales après leur valeur de départ commune. De plus, quand cela se produit pour la première fois, leurs valeurs sont égales au PPCM des entiers $a$ et $b$.
Croissance des deux suites

Ce résultat est très important. Pour le voir, fixez un entier $n\in\N$.

$u_{n+1}-u_n \in \{0,a\}$ donc $u_{n+1}\geq u_n$.
De même $v_{n+1}-v_n \in \{0,b\}$ donc $v_{n+1}\geq v_n$.

Vous avez montré que les suites $(u_n)_{n\in\N}$ et $(v_n)_{n\in\N}$ sont croissantes.

Un exemple

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

Vous obtenez successivement :

$u_n$$v_n$Rang $n$
000
15181
30182
30363
45364
45545
60546
60727
75728
75909
909010
1059011
10510812

Vous observez que le premier rang $n\geq 1$ qui vérifie $u_n=v_n$ vous fournit $90$ qui est le PPCM de $15$ et de $18$.

Certaines personnes sont étonnées de constater qu’un tel rang existe. La question est légitime : pourquoi, après avoir démarré de $0$, les deux suites finissent par être de nouveau égales ? Et pourquoi sur le PPCM ?

Pour prouver ce résultat, vous avez besoin d’en savoir un peu plus.

La plus petite des deux suites finit par augmenter de façon arithmétique jusqu’à dépasser l’autre suite qui reste stationnaire.

Cela vous amène à étudier deux situations.

Les deux comportements

Comportement 1 : si $p$ est un rang tel que $u_p\leq v_p$… qu’advient-il ?

La situation s’inverse, il existe un rang $q>p$ de sorte que les suites se comportent comme suit :

  • la suite $(u_n)_{p\leq n\leq q }$ est arithmétique de raison $a$,
  • la suite $(v_n)_{p\leq n\leq q}$ est stationnaire,
  • $\forall n\in\N, p\leq n\leq q-1 \Longrightarrow u_n\leq v_n$,
  • $u_q>v_q$.
Preuve du comportement n°1

Soit $p\in\N$ tel que $u_p\leq v_p.$

D’après les définitions des deux suites, $u_{p+1} = u_p+a$ et $v_{p+1}=v_p.$

Notez $A$ la partie de $\N$ égale à l’ensemble des entiers naturels $r$ tels que :

  • $r\geq p+1$,
  • la suite $(u_n)_{p\leq n\leq r }$ est arithmétique de raison $a$,
  • la suite $(v_n)_{p\leq n\leq r}$ est stationnaire,
  • $\forall n\in\N, p\leq n\leq r-1 \Longrightarrow u_n\leq v_n.$

Constatez que $p+1\in A$ donc $A\neq \emptyset.$

Supposez que $A$ n’est pas majorée.

Alors la suite $(u_n)_{p\leq n}$ est arithmétique de raison $a$ et la suite $(v_n)_{p\leq n}$ est stationnaire. D’autre part : $$\begin{array}{l}
\forall r\in\N, r\geq p \Longrightarrow u_r\leq v_r\\
\forall r\in\N, r\geq p \Longrightarrow u_p + (r-p)a \leq v_p\\
\forall r\in\N, r\geq p \Longrightarrow r\leq p + \dfrac{v_p-u_p}{a}.
\end{array}$$

Mais il existe un entier supérieur à $p + 1 + \dfrac{v_p-u_p}{a}.$ Contradiction.

Par l’absurde, vous venez de montrer que $A$ est majorée.

La partie $A$ est incluse dans $\N$, elle est non vide et majorée.
Notez $q$ son plus grand élément. Vous savez que $q\in A$ :

  • $q\geq p+1$,
  • la suite $(u_n)_{p\leq n\leq q }$ est arithmétique de raison $a$,
  • la suite $(v_n)_{p\leq n\leq q}$ est stationnaire,
  • $\forall n\in\N, p\leq n\leq q-1 \Longrightarrow u_n\leq v_n.$
Supposez que $u_q \leq v_q$.

Alors $u_{q+1}=u_q + a$ donc la suite $(u_n)_{p\leq n\leq q+1}$ est arithmétique de raison $a$.

$v_{q+1}=v_q$ donc la suite $(v_n)_{p\leq n \leq q+1}$ est stationnaire.

D’autre part, $\forall n\in\N, p\leq n\leq q \Longrightarrow u_n\leq v_n$.

Donc $q+1\in A$. Contradiction, $q$ étant le plus grand élément de $A$.

Par l’absurde, vous venez de justifier que $u_q>v_q.$

Cela achève la démonstration.

Comportement 2 : si $p$ est un rang tel que $u_p> v_p$… qu’advient-il ?

La situation s’inverse à nouveau, il existe un rang $q>p$ de sorte que les suites se comportent comme suit :

  • la suite $(u_n)_{p\leq n\leq q }$ est stationnaire,
  • la suite $(v_n)_{p\leq n\leq q}$ est arithmétique de raison $b$,
  • $\forall n\in\N, p\leq n\leq q-1 \Longrightarrow u_n > v_n$,
  • $u_q\leq v_q$.
Preuve du comportement n°2

Soit $p\in\N$ tel que $u_p> v_p.$

D’après les définitions des deux suites, $u_{p+1} = u_p$ et $v_{p+1}=v_p+b.$

Notez $A$ la partie de $\N$ égale à l’ensemble des entiers naturels $r$ tels que :

  • $r\geq p+1$,
  • la suite $(u_n)_{p\leq n\leq r }$ est stationnaire,
  • la suite $(v_n)_{p\leq n\leq r}$ est arithmétique de raison $b$,
  • $\forall n\in\N, p\leq n\leq r-1 \Longrightarrow u_n > v_n.$

Constatez que $p+1\in A$ donc $A\neq \emptyset.$

Supposez que $A$ n’est pas majorée.

Alors la suite $(u_n)_{p\leq n}$ est stationnaire et la suite $(v_n)_{p\leq n}$ est arithmétique de raison $b$. D’autre part : $$\begin{array}{l}
\forall r\in\N, r\geq p \Longrightarrow u_r> v_r\\
\forall r\in\N, r\geq p \Longrightarrow u_p > v_p + (r-p)b\\
\forall r\in\N, r\geq p \Longrightarrow \dfrac{u_p-v_p}{b}+p>r.
\end{array}$$

Mais il existe un entier supérieur à $p + 1 + \dfrac{u_p-v_p}{b}.$ Contradiction.

Par l’absurde, vous venez de montrer que $A$ est majorée.

La partie $A$ est incluse dans $\N$, elle est non vide et majorée.
Notez $q$ son plus grand élément. Vous savez que $q\in A$ :

  • $q\geq p+1$,
  • la suite $(u_n)_{p\leq n\leq q }$ est stationnaire,
  • la suite $(v_n)_{p\leq n\leq q}$ est arithmétique de raison $b$,
  • $\forall n\in\N, p\leq n\leq q-1 \Longrightarrow u_n> v_n.$
Supposez que $u_q > v_q$.

Alors $u_{q+1}=u_q$ donc la suite $(u_n)_{p\leq n\leq q+1}$ est stationnaire.

$v_{q+1}=v_q+b$ donc la suite $(v_n)_{p\leq n \leq q+1}$ est arithmétique de raison $b$.

D’autre part, $\forall n\in\N, p\leq n\leq q \Longrightarrow u_n> v_n$.

Donc $q+1\in A$. Contradiction, $q$ étant le plus grand élément de $A$.

Par l’absurde, vous venez de justifier que $u_q\leq v_q.$

Cela achève la démonstration.

Etude des multiples de $a$ et de $b$ atteints par les suites

La suite $(u_n)$ est “tantôt stationnaire”, sur une certaine plage de rangs, “tantôt arithmétique” de raison $a$, il vous semble “logique” que tous les multiples de $a$ soient atteints par cette suite. Et effectivement, c’est bien le cas. Passez à la démonstration de ce résultat.

Vous allez montrer que $\forall k\in\N, \exists n\in\N, ka =u_n.$

Procédez par récurrence sur $k$

Pour tout $k\in\N$, notez $P(k)$ la propriété : “$\exists n\in\N, ka=u_n $”.

Initialisation : pour $k=0$, $ka = 0\times a = 0.$ Or $u_0 = 0$ donc $0\times a=u_0$ et $P(0)$ est vérifiée.

Hérédité : soit $k\in\N$, supposez $P(k)$.

Il existe $n\in\N$ tel que $ka = u_n$.

Si $u_n\leq v_n$, alors $u_{n+1} = u_n+a = ka +a= (k+1)a$ et $P(k+1)$ est vérifiée.

Sinon, $u_n > v_n$. D’après le comportement 2, il existe un rang $m>n$ de sorte que :

  • la suite $(u_i)_{n\leq i\leq m }$ est stationnaire,
  • $u_m\leq v_m$.

Comme $u_m \leq v_m$, vous obtenez $u_{m+1} = u_{m} + a = u_n +a = ka+a = (k+1)a$ et $P(k+1)$ est encore vérifiée.

Cela finit la démonstration.

La suite $(v_n)$ possède un comportement similaire. Elle est “tantôt stationnaire”, sur une certaine plage de rangs, “tantôt arithmétique” de raison $b$, il vous semble aussi “logique” que tous les multiples de $b$ soient atteints par cette suite. Et effectivement, c’est bien le cas. Passez à la démonstration de ce résultat.

Vous allez montrer que $\forall k\in\N, \exists n\in\N, kb =v_n.$

Procédez par récurrence sur $k$

Pour tout $k\in\N$, notez $P(k)$ la propriété : “$\exists n\in\N, kb=v_n $”.

Initialisation : pour $k=0$, $kb = 0\times b = 0.$ Or $v_0 = 0$ donc $0\times b=v_0$ et $P(0)$ est vérifiée.

Hérédité : soit $k\in\N$, supposez $P(k)$.

Il existe $n\in\N$ tel que $kb = v_n$.

Si $u_n> v_n$, alors $v_{n+1} = v_n+b = kb+b = (k+1)b$ et $P(k+1)$ est vérifiée.

Sinon, $u_n \leq v_n$. D’après le comportement 1, il existe un rang $m>n$ de sorte que :

  • la suite $(v_i)_{n\leq i\leq m }$ est stationnaire,
  • $u_m> v_m$.

Comme $u_m > v_m$, vous obtenez $v_{m+1} = v_{m} + b = v_n +b = kb+b = (k+1)b$ et $P(k+1)$ est encore vérifiée.

Cela finit la démonstration.

Le PPCM est atteint par les deux suites au même moment

Notez $\delta$ le PPCM des entiers $a$ et $b$. $\delta$ étant un multiple de $a$ et de $b$, il existe $(n,m)\in\N^2$, $\delta = u_n = v_m$.

Vous allez montrer que l’ensemble $\{i\in\N, \delta = u_i=v_i\}$ est non vide.

Cas 1 : $m\leq n$

Par croissance de la suite $(u_i)_{i\in\N}$, $u_m\leq u_n$, donc $u_m \leq v_m$.

D’après le comportement 1, il existe un rang $p>m$ de sorte que :

  • la suite $(u_i)_{m\leq i\leq p }$ est arithmétique de raison $a$,
  • la suite $(v_i)_{m\leq i\leq p}$ est stationnaire avec $\delta$ pour valeur,
  • $\forall n\in\N, m\leq i\leq p-1 \Longrightarrow u_i\leq v_i \leq \delta$,
  • $u_p>v_p\geq v_m\geq \delta$.

Si vous aviez $n\geq p$, par croissance de la suite $(u_i)_{i\in\N}$, $\delta \geq u_n\geq u_p>\delta$, contradiction.

Donc $m\leq n \leq p-1.$ Aussitôt : $\delta\leq u_n \leq v_n \leq \delta.$ Donc $\delta = v_n = u_n$.

Cas 2 : $n\leq m$

Par croissance de la suite $(v_i)_{i\in\N}$, $v_n\leq v_m \leq \delta \leq u_n$, donc $u_n \geq v_n$. Si $u_n=v_n$, alors $\delta = u_n=v_n$ et c’est terminé.

Supposez $u_n>v_n$.

D’après le comportement 2, il existe un rang $p>n$ de sorte que :

  • la suite $(u_i)_{n\leq i\leq p }$ est stationnaire de valeur $\delta$,
  • la suite $(v_i)_{n\leq i\leq p}$ est arithmétique de raison $b$,
  • $\forall i\in\N, n\leq i\leq p-1 \Longrightarrow \delta \geq u_i > v_i$,
  • $\delta \leq u_n \leq u_p\leq v_p$.

Si vous aviez $m\leq p-1$ alors $n\leq m \leq p-1$ et donc $\delta > v_m \geq \delta$, contradiction.

Donc $m\geq p$, donc $\delta \leq u_n \leq u_p \leq v_p \leq v_m \leq \delta$ aussitôt $\delta = v_p = u_p.$

Le plus petit rang non nul pour lequel les suites sont égales correspond au PPCM

D’après ce qui précède, il existe $n\in\N$, $\delta = u_n = v_n$. Or, $\delta\neq 0$, donc $n\neq 0$. L’ensemble $\{i\in\NN, u_i=v_i\}$ est une partie non vide de $\N$. Notez $s$ son minimum.

Vous voulez comprendre pourquoi $u_s = v_s = \delta$…

Premièrement, vous savez d’après ce qui précède qu’il existe un entier $p\in\N$ tel que $\delta = u_p = v_p.$ Par minimalité de $s$, vous avez $s\leq p$ et par croissance des suites $u$ et $v$ : $u_s\leq u_p \leq \delta$ et $ v_s \leq v_p \leq \delta$.

Ensuite, $u_s$ est un terme de la suite $(u_n)$ donc c’est un multiple de $a$, de même pour $v_s$ qui est un terme de la suite $(v_n)$ qui est un multiple de $b$. Comme $u_s = v_s$ vous en déduisez que $u_s$ est un multiple de $a$ et de $b$. Par définition du PPCM, $\delta \leq u_s$ et $\delta \leq v_s$.

Aussitôt $\delta \leq u_s\leq u_p \leq \delta$ et $\delta \leq v_s \leq v_p \leq \delta$ ce qui fournit le résultat.

Réagissez !

C’est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées.