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$ |
|---|---|---|
| 0 | 0 | 0 |
| 15 | 18 | 1 |
| 30 | 18 | 2 |
| 30 | 36 | 3 |
| 45 | 36 | 4 |
| 45 | 54 | 5 |
| 60 | 54 | 6 |
| 60 | 72 | 7 |
| 75 | 72 | 8 |
| 75 | 90 | 9 |
| 90 | 90 | 10 |
| 105 | 90 | 11 |
| 105 | 108 | 12 |
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$.
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.
[/su_yspoiler]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$.
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.$
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.$
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.
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. 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.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !