Problème — Le théorème de Lamé

Ce qu'on a le droit d'utiliser. La récurrence sous ses trois formes ; la division euclidienne, avec l'unicité du quotient et du reste ; le lemme d'Euclide ; la croissance du logarithme népérien. Les termes $F_0$ à $F_{21}$ sont $0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946$. On notera que $F_n\ge 1$ pour $n\ge 1$, et que $F_{n+1}=F_n+F_{n-1}>F_n$ dès que $n\ge 2$.

1) Le nombre d'or et la minoration de Fibonacci. On calcule ${\phi }^2=\frac{1+2\sqrt{5}+5}{4}=\frac{6+2\sqrt{5}}{4}=\frac{3+\sqrt{5}}{2}$, et $\phi +1=\frac{1+\sqrt{5}+2}{2}=\frac{3+\sqrt{5}}{2}$ : ${\phi }^2=\phi +1$.

Notons ${\mathcal{A}}_n$ l'assertion « $F_{n+2}\ge {\phi }^n$ », et raisonnons par récurrence double.

Initialisation, deux rangs. $F_2=1={\phi }^0$ : ${\mathcal{A}}_0$ est vraie. $F_3=2$ et $\phi <2$ puisque $\sqrt{5}<3$ : ${\mathcal{A}}_1$ est vraie.

Hérédité. Soit $n\in \mathbb{N}$ tel que ${\mathcal{A}}_n$ et ${\mathcal{A}}_{n+1}$ soient vraies. Alors $$F_{n+4}=F_{n+3}+F_{n+2}\ge {\phi }^{n+1}+{\phi }^n={\phi }^n(\phi +1)={\phi }^n{\phi }^2={\phi }^{n+2},$$ ce qui est ${\mathcal{A}}_{n+2}$. Par récurrence double, $F_{n+2}\ge {\phi }^n$ pour tout $n\in \mathbb{N}$.

Le point à voir. C'est exactement l'identité ${\phi }^2=\phi +1$ qui rend la minoration héréditaire : les puissances de $\phi$ vérifient la même relation que la suite de Fibonacci. Et la récurrence est double parce que $F_{n+4}$ s'exprime à l'aide des deux termes précédents.

2) Le pire cas : deux nombres de Fibonacci consécutifs. Montrons par récurrence sur $n\ge 1$ que $N(F_{n+2},F_{n+1})=n$.

Pour $n=1$, le couple est $(F_3,F_2)=(2,1)$ : $2=2\times 1+0$, une seule division, donc $N(2,1)=1$.

Soit $n\ge 2$ tel que $N(F_{n+1},F_n)=n-1$. La relation de récurrence donne $$F_{n+2}=1\times F_{n+1}+F_n,\text{avec}0<F_n<F_{n+1},$$ puisque $n\ge 2$. Par unicité de la division euclidienne, c'est la division de $F_{n+2}$ par $F_{n+1}$ : le quotient vaut $1$ et le reste $r_2=F_n$, non nul. L'algorithme se poursuit donc sur le couple $(F_{n+1},F_n)$, qui demande $n-1$ divisions par hypothèse ; au total $N(F_{n+2},F_{n+1})=1+(n-1)=n$.

Le PGCD. Le lemme d'Euclide conserve le PGCD à chaque étape : $F_{n+2}\wedge F_{n+1}=F_{n+1}\wedge F_n=\cdots =F_3\wedge F_2=2\wedge 1=1$. Deux nombres de Fibonacci consécutifs ont pour PGCD $1$, et tous les quotients valent $1$, sauf le dernier, qui vaut $2$.

Vérification sur $(987,610)$. La première division est $987=1\times 610+377$ ; les restes suivants sont $233,144,89,55,34,21,13,8,5,3,2,1$, tous obtenus avec le quotient $1$, et la dernière division est $2=2\times 1+0$ : quatorze divisions, soit $16-2$, et le PGCD vaut $1$.

3) Toute exécution longue exige de grands nombres. Notons ${\mathcal{B}}_n$ l'assertion : « pour tous entiers $a>b\ge 1$ tels que $N(a,b)=n$, on a $b\ge F_{n+1}$ et $a\ge F_{n+2}$ ». Récurrence sur $n\ge 1$.

Initialisation. Si $N(a,b)=1$ : $b\ge 1=F_2$, et $a>b$ donne $a\ge 2=F_3$. Donc ${\mathcal{B}}_1$ est vraie.

Hérédité. Soit $n\ge 1$ tel que ${\mathcal{B}}_n$ soit vraie, et soient $a>b\ge 1$ tels que $N(a,b)=n+1$. Comme $n+1\ge 2$, le reste $r_2$ n'est pas nul — sinon l'algorithme se serait arrêté après une division —, et $b=r_1>r_2\ge 1$. L'algorithme appliqué au couple $(b,r_2)$ produit les restes $r_2,r_3,\dots$ de l'algorithme de départ, décalés d'un rang : il effectue une division de moins, $N(b,r_2)=n$. On peut donc appliquer ${\mathcal{B}}_n$ au couple $(b,r_2)$ : $$r_2\ge F_{n+1}\text{et}b\ge F_{n+2}.$$ Enfin la première division s'écrit $a=q_{1}b+r_2$, avec $q_1\ge 1$ puisque $a>b$ (si $q_1$ était nul, on aurait $a=r_2<b$). Donc $$a\ge b+r_2\ge F_{n+2}+F_{n+1}=F_{n+3}.$$ Ainsi $b\ge F_{n+2}$ et $a\ge F_{n+3}$ : ${\mathcal{B}}_{n+1}$ est vraie, ce qui achève la récurrence.

Le point délicat : quantifier sur toutes les données. L'hypothèse de récurrence a été appliquée au couple $(b,r_2)$, qui n'est pas le couple de départ : c'est parce que ${\mathcal{B}}_n$ porte sur tous les couples qui demandent $n$ divisions qu'on a le droit de l'appliquer au couple suivant de l'algorithme. Et le 2) montre que ces minorations sont atteintes : deux nombres de Fibonacci consécutifs forment le plus petit couple qui demande $n$ divisions.

4) Le nombre de divisions est logarithmique. Soient $a>b\ge 1$ et $n=N(a,b)\ge 1$. Par le 3) puis le 1), appliqué au rang $n-1\ge 0$ : $$b\ge F_{n+1}=F_{(n-1)+2}\ge {\phi }^{n-1}.$$ Le logarithme étant croissant, $\ln b\ge (n-1)\ln \phi$ ; et $\ln \phi >0$, puisque $\phi >1$. En divisant par $\ln \phi$ : $$N(a,b)=n\le 1+\frac{\ln b}{\ln \phi }.$$ Contrôle : pour $b=610$, la borne vaut $1+\frac{6,4135}{0,4812}\approx 14,33$, et le couple $(987,610)$ demande quatorze divisions : elle est presque atteinte.

5) Le théorème de Lamé. On réduit les puissances de $\phi$ grâce à ${\phi }^2=\phi +1$ : $$\begin{array}{rl}{\phi }^3& =\phi \cdot {\phi }^2={\phi }^2+\phi =2\phi +1,\\ {\phi }^4& =2{\phi }^2+\phi =3\phi +2,\\ {\phi }^5& =3{\phi }^2+2\phi =5\phi +3.\end{array}$$ (Les coefficients sont des nombres de Fibonacci : ${\phi }^n=F_n\phi +F_{n-1}$.) Donc $${\phi }^5=\frac{5(1+\sqrt{5})}{2}+3=\frac{11+5\sqrt{5}}{2},$$ et ${\phi }^5>10$ équivaut à $5\sqrt{5}>9$, c'est-à-dire, les deux membres étant positifs, à $125>81$ : c'est vrai. Numériquement, ${\phi }^5\approx 11,09$. En passant au logarithme, $5\ln \phi >\ln 10$.

Soit alors $b$ un entier qui s'écrit avec $k$ chiffres en base $10$ : $10^{k-1}\le b<10^k$. Par le 4), $$N(a,b)\le 1+\frac{\ln b}{\ln \phi }<1+\frac{k\ln 10}{\ln \phi }<1+\frac{5k\ln \phi }{\ln \phi }=1+5k.$$ Comme $N(a,b)$ est un entier strictement inférieur à l'entier $5k+1$, $N(a,b)\le 5k$ : c'est le théorème de Lamé. (Plus finement, $\frac{\ln 10}{\ln \phi }\approx 4,785$ : le nombre de divisions est au plus d'environ $4,8$ par chiffre, plus une.)

6) La borne est atteinte, puis ne l'est plus. Par le 2), les couples $(F_7,F_6)=(13,8)$, $(F_{12},F_{11})=(144,89)$ et $(F_{17},F_{16})=(1597,987)$ demandent respectivement $5$, $10$ et $15$ divisions, et leur plus petit nombre a un, deux et trois chiffres : la borne $5k$ est atteinte pour $k=1$, $2$ et $3$.

Pour $k=4$, par l'absurde : si un couple $a>b$, avec $b$ à quatre chiffres, demandait $20$ divisions, le 3) donnerait $b\ge F_{21}=10946$, qui a cinq chiffres. Donc $N(a,b)\le 19<20$ : la borne $5k$ n'est pas atteinte pour $k=4$ ; le maximum $19$ est atteint par $(F_{21},F_{20})=(10946,6765)$. Contrôle : un calcul exhaustif sur tous les $b$ à un, deux et trois chiffres donne pour maximum de $N(a,b)$ exactement $5$, $10$ et $15$.

Le théorème obtenu — théorème de Lamé (1844). Pour deux entiers $a>b\ge 1$, l'algorithme d'Euclide effectue au plus $1+\frac{\ln b}{\ln \phi }$ divisions ; en particulier, si $b$ s'écrit avec $k$ chiffres en base $10$, il en effectue au plus $5k$. Le pire cas est celui de deux nombres de Fibonacci consécutifs, et le nombre de divisions croît comme le logarithme de $b$ : l'algorithme d'Euclide est rapide.

Ce que le problème installe. Deux idées qui dépassent ce chapitre. Pour compter les étapes d'un algorithme, on fait une récurrence sur leur nombre, dont l'hypothèse porte sur toutes les données — c'est le raisonnement de l'analyse de complexité, que le cours d'informatique reprendra. Et le pire cas n'est pas un accident mais une structure : tous les quotients valent $1$, l'algorithme « descend le plus lentement possible ». Le nombre d'or $\phi$ n'a servi que par la relation ${\phi }^2=\phi +1$ ; au chapitre des suites, les suites récurrentes linéaires d'ordre $2$ donneront la formule exacte de $F_n$ et diront pourquoi $\phi$ est le bon nombre. On le retrouvera dès la séance suivante : le cosinus de $\frac{\pi }{5}$ vaut exactement $\frac{\phi }{2}$.