Prérequis
Résumé
Le "Lifting The Exponent Lemma" (LTE) et le théorème de Zsigmondy sont des résultats puissants qui s'intéressent aux facteurs premiers des expressions $a^n + b^n$ et $a^n - b^n$. Ils permettent parfois de résoudre de manière très simple des problèmes qui ne le sont pourtant pas. De manière similaire, la méthode "Vieta jumping" a récemment vu le jour et est vite devenue fondamentale dans le domaine de la résolution de problèmes de théorie des nombres.
Ce chapitre a été
écrit par N. Radu et
mis en ligne le 6 octobre 2016.
1. Lifting The Exponent Lemma
Nous présentons ici le
Lifting The Exponent Lemma, souvent appelé plus simplement
LTE. Il s'agit d'un résultat permettant, sous certaines conditions, de savoir le nombre de fois qu'un facteur premier $p$ apparaît dans une expression du type $a^n \pm b^n$. On introduit pour cela une notation :
Par exemple, $v_3(18) = 2$, $v_5(35) = 1$ et $v_7(68) = 0$. Le problème qui nous intéresse est alors simplement celui de trouver une formule pour $v_p(a^n+b^n)$ et $v_p(a^n-b^n)$.
On peut commencer par quelques remarques simples :
- Si exactement un des deux nombres $a$ et $b$ est divisible par $p$, alors $a^n+b^n$ et $a^n-b^n$ ne sont jamais divisibles par $p$. Autrement dit, $v_p(a^n \pm b^n) = 0$. Il s'agit là d'une évidence.
- Si les deux nombres $a$ et $b$ sont divisibles par $p$, alors on peut noter $a = p \cdot a'$ et $b = p \cdot b'$ et on obtient $a^n \pm b^n = p^n \cdot (a'^n \pm b'^n)$. On a donc $v_p(a^n \pm b^n) = n + v_p(a'^n \pm b'^n)$ et on s'est ramené au même problème mais avec des nombres ($a'$ et $b'$) plus petits.
De ces deux remarques, on déduit qu'on peut dorénavant supposer que ni $a$ ni $b$ n'est divisible par $p$.
Première forme
Intéressons-nous à présent à l'expression $a^n - b^n$. Comme on l'a déjà vu précédemment, on a
$$a^n- b^n = (a-b) \cdot (a^{n-1} + a^{n-2}b + \ldots + ab^{n-2} + b^{n-1}).$$ Cela signifie déjà que $v_p(a^n-b^n) \geq v_p(a-b)$. La première forme du LTE nous donne en fait une formule plus précise que cela,
pourvu que $a-b$
soit divisible par $p$ (c'est-à-dire que $v_p(a-b) \geq 1$) et que $p \neq 2$. Elle s'énonce comme suit :
LTE pour $a^n-b^n$
Soit $a$ et $b$ des entiers (non nécessairement positifs), $n$ un entier strictement positif et $p$ un nombre premier impair tel que $p$ divise $a-b$ mais $p$ ne divise ni $a$ ni $b$. Alors
$$v_p(a^n-b^n) = v_p(a-b) + v_p(n).$$
La preuve de ce résultat consiste à montrer que le nombre de facteurs $p$ apparaissant dans l'expression $a^{n-1} + a^{n-2}b + \ldots + ab^{n-2} + b^{n-1}$ est, sous les conditions de l'énoncé, égal à $v_p(n)$. Nous ne donnons pas la preuve ici, bien qu'elle ne soit pas très compliquée.
Remarque importante : Il est primordial de retenir les hypothèses de ces résultats ! Il arrive souvent d'oublier que $p$ doit diviser $a \pm b$, mais dans ce cas le résultat est complètement faux ! Cette remarque est également valable pour les autres formes du lemme, ci-dessous.
Deuxième forme
En ce qui concerne l'expression $a^n+b^n$, il a déjà été vu précédemment que l'on avait la factorisation suivante
pourvu que $n$
soit impair :
$$a^n + b^n = (a+b) \cdot (a^{n-1} - a^{n-2}b + \ldots - ab^{n-2} + b^{n-1})$$ Il faut donc logiquement s'attendre à ce que l'hypothèse comme quoi $n$ est impair apparaisse dans la deuxième forme du LTE. Les autres hypothèses restent les mêmes : $p$ doit être différent de $2$ et doit diviser $a+b$.
LTE pour $a^n+b^n$
Soit $a$ et $b$ des entiers (non nécessairement positifs), $n$ un entier strictement positif impair et $p$ un nombre premier impair tel que $p$ divise $a+b$ mais $p$ ne divise ni $a$ ni $b$. Alors
$$v_p(a^n+b^n) = v_p(a+b) + v_p(n).$$
Quid de $p = 2$ ?
Dans les deux formes du LTE, le nombre $p$ doit être impair et on ne peut donc pas le prendre égal à $2$. Il existe toutefois un résultat similaire à la première forme du LTE pour $p = 2$, mais $a-b$ doit être divisible par $4$ (et pas seulement par $2$).
LTE pour $p = 2$
Soit $a$ et $b$ des entiers impairs tels que $4$ divise $a-b$ et soit $n$ un entier strictement positif. Alors
$$v_2(a^n - b^n) = v_2(a-b) + v_2(n).$$
Preuves et problèmes
Ces résultats proviennent de
cette page (voir le PDF qui y est attaché). On peut y trouver les preuves des différents résultats, ainsi que de nombreux problèmes d'olympiades (certains avec solutions) pouvant se résoudre plus facilement grâce au LTE. Nous détaillons les preuves de deux tels problèmes dans la suite de ce chapitre, mais nous conseillons le lecteur intéressé d'en essayer encore d'autres.
2. Exemples d'application
Nous donnons ici deux applications concrètes du LTE. La première est plus ou moins directe (on peut penser au LTE dès qu'on lit le problème), alors que la deuxième est un peu plus cachée.
Solution
Puisque $1991$ divise $1990+1992$, il est très tentant d'utiliser le LTE. Mais cela ne va quand même pas être aussi simple : les exposants de $1990$ et $1992$ ne sont pas les mêmes et, en plus, $1991$ n'est pas premier ! On a en effet $1991 = 11 \cdot 181$. Ce deuxième obstacle peut facilement être passé : nous allons essayer d'utiliser le LTE avec successivement $p = 11$ et $p = 181$. Pour ce qui est des exposants qui ne sont pas les mêmes, on peut en fait simplement constater que :
$$1990^{1991^{1992}} + 1992^{1991^{1990}} = \left(1990^{1991^2}\right)^{1991^{1990}} + 1992^{1991^{1990}}.$$ On a donc bien une expression de la forme $a^n+b^n$, avec $a = 1990^{1991^2}$, $b = 1992$ et $n = 1991^{1990}$. Prenons $p = 11$ et vérifions les hypothèses du LTE (deuxième forme). On a $n$ qui est bien impair, et $p$ qui est bien différent de $2$. Il suffit donc d'avoir $p$ qui divise $1990^{1991^2} + 1992$ pour pouvoir appliquer le lemme. Cela peut se voir de plusieurs manières. La plus simple est peut-être de regarder l'expression modulo $p$ : puisque $1991 \equiv 0 \bmod p$, on a $1990 \equiv -1$ et $1992 \equiv 1$, d'où $1990^{1991^2} + 1992 \equiv (-1)^{1991^2} + 1 \equiv 0 \bmod p$. Les hypothèses du LTE sont donc vérifiées et celui-ci donne
$$v_p\left(\left(1990^{1991^2}\right)^{1991^{1990}} + 1992^{1991^{1990}}\right) = v_p\left(1990^{1991^2} + 1992\right) + v_p(1991^{1990}).$$ On a $v_p(1991^{1990}) = 1990$, et il reste à évaluer $v_p\left(1990^{1991^2} + 1992\right)$. Pour cela, on peut utiliser le résultat général suivant (celui-ci est très important et très facile à la fois : la démonstration est laissée au lecteur) :
Lemme
Soit $p$ un nombre premier et $x, y$ deux entiers. On a
$$v_p(x+y) \geq \min(v_p(x), v_p(y)) \text{ avec égalité lorsque $v_p(x) \neq v_p(y)$}.$$
Suite de la solution
Dans notre contexte, en prenant $x = 1990^{1991^2}+1$ et $y = 1991$, on obtient $v_p(x) = 3$ (à nouveau à l'aide du LTE !) et $v_p(y) = 1$, donc $v_p(x+y) = 1$ (car $3 \neq 1$).
Au final, nous avons prouvé que la valuation $p$-adique de l'expression de départ est égale à $1990 + 1 = 1991$. Tout notre raisonnement est valide pour $p = 11$ mais aussi pour $p = 181$, donc on en déduit que la réponse au problème est $k = 1991$.
Voici un autre problème :
Si l'on souhaite appliquer le LTE à l'expression $2^n+1$, alors on ne peut prendre pour $p$ qu'un diviseur de $2+1$, c'est-à-dire $3$. Pour cette raison nous allons d'abord prouver le petit lemme suivant :
Lemme
Si $n^2$ divise $2^n+1$, alors $n$ est divisible par $3$.
Démonstration du lemme
Considérons $n$ tel que $n^2$ divise $2^n+1$. Notons $p$ le plus petit facteur premier de $n$ : clairement $p \neq 2$. On a $2^n +1 \equiv 0 \bmod p$, donc $2^n \equiv -1 \bmod p$ et $2^{2n} \equiv 1 \bmod p$. Or, on a aussi $2^{p-1} \equiv 1 \bmod p$ par le théorème de Fermat. On en déduit que l'ordre multiplicatif $o_p(2)$ de $2$ modulo $p$ doit diviser à la fois $2n$ et $p-1$. Mais $n$ et $p-1$ sont premiers entre eux, puisque $p$ est le plus petit facteur premier de $n$. Donc $o_p(2) = 2$ (il ne peut clairement pas être égal à $1$) et $2^2 \equiv 1 \bmod p$, d'où $p = 3$. Cela prouve que $n$ est divisible par $3$.
On peut maintenant utiliser ce lemme pour résoudre le problème.
Solution du problème
Par le lemme, $n$ est divisible par $3$. Nous appliquons alors le LTE (deuxième forme) avec $p = 3$. On a $v_3(2^n+1) = v_3(2+1) + v_3(n) = 1+v_3(n)$ (les hypothèses sont bien vérifiées). D'autre part, $v_3(n^2) = 2 \cdot v_3(n)$. Pour que $n^2$ divise $2^n+1$, il faut donc que $2 v_3(n) \leq 1+v_3(n)$. On en déduit que $v_3(n) =1$ et donc que $n$ est de la forme $n = 3 m$ avec $m$ non multiple de $3$.
Nous faisons à présent le même argument que dans notre lemme. Supposons $m > 1$ et notons $q$ le plus petit facteur premier de $m$. On a $2^{3m} \equiv -1 \bmod q$ et donc $2^{6m} \equiv 1 \bmod q$. D'autre part, par Fermat on sait que $2^{q-1} \equiv 1 \bmod q$. Donc l'ordre multiplicatif $o_q(2)$ de $2$ modulo $q$ divise $6m$ et $q-1$. Comme $m$ et $q-1$ n'ont aucun facteur commun, $o_q(2)$ divise $6$. Ainsi, $2^6 \equiv 1 \bmod q$. Donc $q$ divise $2^6-1 = 63$ et ainsi $q = 7$ (car $q \neq 3$).
Cela étant, une expression de la forme $2^n+1$ n'est jamais divisible par $7$ ! En effet, les puissances de $2$ modulo $7$ donnent successivement $1, 2, 4, 1, 2, 4, \ldots$, et donc $2^n+1$ n'est jamais divisible par $7$. Nous avons donc une contradiction : $q$ ne peut pas être égal à $7$. Cela signifie que le nombre $m$ était en fait égal à $1$, d'où $n = 3$. Le seul entier $n$ vérifiant l'énoncé est donc $n = 3$ (qui fonctionne bien : $3^2 = 9$ divise $2^3+1 = 9$).
3. Théorème de Zsigmondy
Nous avons vu avec le LTE comment obtenir des informations sur le nombre d'occurence des facteurs premiers de $a^n \pm b^n$ apparaissant déjà dans $a \pm b$. Le
théorème de Zsigmondy s'intéresse également aux facteurs premiers de $a^n \pm b^n$, mais ceux qui ne se situent pas dans $a \pm b$. Il affirme en fait que, si $a$ et $b$ sont premiers entre eux et à part pour quelques rares exceptions, le nombre $a^n \pm b^n$ aura toujours au moins un facteur premier qui n'apparaît ni dans $a \pm b$, ni dans $a^2 \pm b^2$, ..., ni dans $a^{n-1} \pm b^{n-1}$.
Première forme
La première forme du théorème, pour $a^n - b^n$, s'énonce comme suit :
Théorème de Zsigmondy pour $a^n - b^n$
Soit $a > b$ des entiers strictement positifs
premiers entre eux. Alors,
à l'exception des cas particuliers suivants, pour tout entier $n \geq 2$, il existe un nombre premier $p$ (appelé
facteur premier primitif) qui divise $a^n - b^n$ mais ne divise aucun $a^k - b^k$ pour $1 \leq k < n$. Les exceptions sont les suivantes :
- Si $a+b$ est une puissance de $2$, alors l'énoncé est faux pour $n = 2$.
- Si $a = 2$ et $b = 1$, alors l'énoncé est faux pour $n = 6$.
Une petite justification des exceptions :
- Lorsque $a+b$ est une puissance de $2$ et $n = 2$, les facteurs premiers de $a^2-b^2 = (a-b)(a+b)$ sont exactement ceux de $a-b$ (car le seul diviseur premier de $a+b$ est $2$, qui se trouve déjà dans $a-b$).
- Pour $a = 2$, $b = 1$ et $n = 6$, on a $2^6 - 1^6 = 63$ qui n'a que $3$ (apparaissant déjà dans $2^2-1^2$) et $7$ (apparaissant déjà dans $2^3-1$) comme facteurs premiers.
La preuve de ce théorème est compliquée (plus difficile que le LTE : ce n'est pas pour rien que l'un s'appelle Lemme et l'autre Théorème !), elle sort du cadre de ce cours.
Deuxième forme
En ce qui concerne $a^n + b^n$, l'énoncé est le même mais il n'y a qu'une seule exception :
Théorème de Zsigmondy pour $a^n+b^n$
Soit $a > b$ des entiers strictement positifs premiers entre eux. Alors, pour tout entier $n \geq 2$ à l'exception du cas $a = 2$, $b = 1$ et $n = 3$, il existe un nombre premier $p$ (appelé facteur premier primitif) qui divise $a^n + b^n$ mais ne divise aucun $a^k + b^k$ pour $1 \leq k < n$.
L'exception est claire : on a $2^3 + 1^3 = 9$ qui n'a que $3$ comme facteur premier, apparaissant déjà dans $2^1+1^1 = 3$.
Démonstration de la deuxième forme à partir de la première
Prenons $a, b$ et $n$ comme dans l'énoncé. On cherche un facteur premier de $a^n + b^n$ n'apparaissant dans aucun $a^k + b^k$ avec $k < n$. Considérons le nombre $a^{2n} - b^{2n} = (a^n - b^n)(a^n + b^n)$. Par la première forme du théorème, il existe un nombre $p$ divisant $a^{2n} - b^{2n}$ mais ne divisant aucun $a^k - b^k$ avec $k < 2n$. En particulier, $p$ ne divise pas $a^n - b^n$. Il doit donc diviser $a^n + b^n$. D'autre part, comme $p$ ne divise aucun $a^{2k} - b^{2k}$ avec $k < n$, il ne divise aucun $a^k + b^k$ avec $k < n$.
Nous n'avons jusqu'ici pas tenu compte des exceptions lors de l'application de la première forme de Zsigmondy, donc regardons cela maintenant. La première exception apparaît si $n = 1$ (de sorte que $2n = 2$) et $a+b$ est une puissance de $2$. Mais l'énoncé du résultat ne parle que de $n \geq 2$, donc ce n'est pas un souci. La deuxième exception se présente pour $a = 2$, $b = 1$ et $n = 3$ (de sorte que $2n = 6$). C'est celle-ci qui donne lieu à l'unique exception de la deuxième forme de Zsigmondy.
4. Exemples d'application
Comme pour le LTE, nous donnons ici des applications du théorème de Zsigmondy à des problèmes d'olympiades.
Solution
Il apparaît assez clairement que le théorème de Zsigmondy va pouvoir être utile dans cette situation. Il faut d'abord traiter le cas particulier $a = 1$. On a alors directement $0 = 0$, donc tous les $5$-uplets du type $\boxed{(1,n,p,q,r)}$ conviennent. Supposons à présent que $a \geq 2$. Il est clair que $n$ doit être supérieur ou égal à $p, q$ et $r$. Si $n = p$, alors on trouve directement que $1=(a^q-1)(a^r-1)$, donc $(a,q,r) = (2,1,1)$. On trouve donc le $5$-uplet $\boxed{(2,n,n,1,1)}$, et de la même façon pour $n = q$ et $n = r$ on trouve les solutions $\boxed{(2,n,1,n,1), (2,n,1,1,n)}$. Supposons à présent que $n > p, q, r$. Alors le théorème de Zsigmondy nous dit que $a^n-1$ possède,
sauf exceptions, un facteur premier que $a^p - 1, a^q - 1$ et $a^r - 1$ ne possèdent pas. C'est donc impossible, ce qui signifie qu'il reste à vérifier les exceptions au théorème de Zsigmondy.
- On a une exception quand $a = 2$ et $n = 6$. Celle-ci donne $63 = (2^p-1)(2^q-1)(2^r-1)$. Comme $2^k-1 \in \{1,3,7,15,31\}$ pour les premières valeurs de $k$, on trouve que $p,q,r$ doivent valoir $2,2,3$ dans un certain ordre. Cela donne donc les solutions $\boxed{(2,6,2,2,3), (2,6,2,3,2), (2,6,3,2,2)}$.
- L'autre exception a lieu pour $n=2$ quand $a+1$ est une puissance de $2$. Puisque $p,q,r < n$, il faut alors que $p=q=r=1$, d'où l'équation devient $a^2-1 = (a-1)^3$, ou encore $a+1 = (a-1)^2$. Celle-ci se réécrit $a^2-3a = 0$ et donne donc $a = 3$. On trouve ainsi la dernière solution $\boxed{(3,2,1,1,1)}$.
Notez bien que ce problème peut se résoudre également sans faire appel à ce (gros) théorème, et ce sans trop de difficultés supplémentaires, mais notre but est bien sûr ici d'illustrer la puissance de cet outil.
Solution
Modulo $4$, on a $5^y$ qui vaut toujours $1$ et $3^x$ qui vaut $1$ ou $3$ selon que $x$ est pair ou impair. Si $x$ est impair alors on obtient directement une contradiction puisque le membre de gauche est alors égal à $2$ modulo $4$, ce qui est impossible pour un carré. Le nombre $x$ doit donc être pair : posons $x = 2a$. On réécrit alors
$$3^{2a} - z^2 = 5^y,$$ ou encore
$$(3^a - z)(3^a+z) = 5^y.$$ Les deux nombres $3^a - z$ et $3^a + z$ doivent donc tous les deux être des puissances de $5$, disons $3^a - z = 5^s$ et $3^a + z = 5^t$ (avec $s < t$). En additionnant ces deux égalités, on obtient $2 \cdot 3^a = 5^s + 5^t$. Les nombres $s$ et $t$ ne peuvent pas tous les deux être non-nuls, puisqu'alors $2 \cdot 3^a$ serait multiple de $5$ : impossible. On doit donc avoir $s = 0$ et
$$2 \cdot 3^a = 5^t + 1$$ Mais, par le théorème de Zsigmondy, pour $t > 1$ le nombre $5^t + 1^t$ possède un facteur premier ne divisant pas $5^1 + 1^1 = 6$, c'est-à-dire différent de $2$ et $3$. Le nombre $t$ ne peut donc pas être supérieur à $1$. On en déduit que $t = 1$ et $a = 1$, ce qui donne $(x,y,z) = (2, 1, 2)$ comme unique solution.
5. Vieta Jumping
Le
Vieta jumping est une technique de preuve. Son nom provient du fait qu'elle utilise les
formules de Viète. Cette technique est assez récente puisque sa première apparition dans une preuve d'un problème d'olympiade date de 1988, avec le problème le plus difficile de l'IMO 1988. Nous prendrons ce problème en exemple plus bas.
Vieta jumping standard
La technique standard de Vieta jumping s'applique lorsque l'on doit prouver une affirmation sur des variables vérifiant une certaine relation. Afin d'être plus concret, nous allons illustrer la technique sur le problème 6 de l'IMO 1988, dont l'énoncé est le suivant :
Solution
La technique comporte plusieurs étapes et consiste en une preuve par l'absurde :
- On suppose par l'absurde qu'il existe des variables vérifiant les hypothèses mais ne vérifiant pas l'affirmation demandée.
Sur l'exemple : Supposons qu'il existe $a$ et $b$ tels que $ab+1$ divise $a^2+b^2$ mais $\frac{a^2+b^2}{ab+1}$ n'est pas un carré parfait. Nous supposons donc que $\frac{a^2+b^2}{ab+1} = k$ est entier mais n'est pas un carré parfait.
- On considère une solution "minimale" (dans un certain sens à préciser) $(A,B)$ à la relation du point 1. En ce point, cette méthode va se rapprocher de la méthode de descente infinie.
Sur l'exemple : Fixons $k$ une fois pour toute et prenons $(A,B)$ tels que $\frac{A^2+B^2}{AB+1} = k$, avec $A+B$ minimal. Nous supposons sans perte de généralité que $A \geq B$ (cela se révélera utile plus tard).
- On réarrange la relation sur $A$ et $B$ en une équation quadratique dont les coefficients dépendent de $B$ et dont une racine est $A$. On utilise alors les formules de Viète pour déterminer la deuxième racine $R$ de cette équation quadratique.
Sur l'exemple : La relation plus haut peut se réécrire $A^2+B^2 = k \cdot (AB+1)$, ou encore $A^2 - kB \cdot A + (B^2 - k) = 0$. Autrement dit, $A$ est une racine du polynôme
$$x^2 - kB \cdot x + (B^2-k) = 0.$$ La deuxième racine $R$ de ce polynôme vérifie, par les formules de Viète, $R+A = kB$ et $R \cdot A = B^2-k$. On a donc $R = kB - A\ \ (*)$ ainsi que $R = \frac{B^2-k}{A}\ \ (**)$.
- On montre que la deuxième racine $R$ de l'équation quadratique donne lieu à une deuxième solution $(R,B)$ qui est à la fois valide (c'est-à-dire vérifiant les hypothèses) et plus petite que la solution $(A,B)$. Cela contredit la minimalité de $(A,B)$ et termine la preuve.
Sur l'exemple : L'équation $(*)$ implique que le nombre $R$ est entier, et l'équation $(**)$ implique que $R$ est non-nul (car $k$ n'est pas un carré). Du fait que $\frac{R^2+B^2}{RB+1} = k > 0$ il découle aussi que $R$ est positif. Finalement, on a $R = \frac{B^2-k}{A} \leq \frac{A^2-k}{A} < A$, ce qui montre que $R < A$. Donc $(R,B)$ vérifie la même équation que $(A,B)$ mais est tel que $R+B < A+B$, ce qui contredit la minimalité de $(A,B)$. On a donc notre absurdité.
Autre exemple avec les idées du Vieta jumping
La méthode décrite ci-dessus est la méthode "standard", mais l'idée essentielle est d'utiliser les formules de Viète pour construire une solution plus petite que celle en notre possession. Il n'est donc pas obligatoire de suivre à la lettre les étapes ci-dessus pour pouvoir dire qu'on a utilisé le Vieta jumping. Voici un autre problème pour lequel on peut appliquer ce type de méthode :
Une solution à ce problème est la suivante :
Solution
- Si $a = b$, alors $a^2$ divise $2a^2+1$ donc $a = 1$ et l'énoncé est bien vérifié. Supposons à présent que $a \neq b$, et sans perte de généralité que $a > b$.
- Notons $k = \frac{a^2+b^2+1}{ab}$. Cette relation s'écrit aussi $a^2 - bk \cdot a + (b^2+1) = 0$. Donc $a$ est une racine du polynôme
$$x^2 - bk \cdot x + (b^2+1) = 0.$$ L'autre racine $r$ de ce polynôme vérifie, au vu des formules de Viète, $a+r = bk$ et $ar = b^2+1$. On a donc $r = bk - a \ \ (*)$ et $r = \frac{b^2+1}{a} \ \ (**)$.
- On a par $(*)$ que $r$ est un nombre entier, et par $(**)$ que $r > 0$. De plus, comme $a > b$, on a $r = \frac{b^2+1}{a} < b$ sauf pour $(a,b) = (2,1)$. À moins d'être dans ce dernier cas, on peut donc remplacer $(a,b)$ par $(b,r)$, qui est une solution plus petite et pour laquelle la valeur de $k$ reste inchangée.
- Cette opération peut être répétée tant que $(a,b) \neq (2,1)$. À terme, on arrive au cas où $(a,b) = (2,1)$ pour lequel on a $k = 3$. Cela signifie que, depuis le début de notre descente, $k$ est égal à $3$.
(
Cette page est inspirée de l'article Wikipédia correspondant.)