Exercice 12

1. Le dernier reste non nul $r_{N}$ est un entier naturel non nul, donc $r_{N} \geqslant 1$. La dernière division s'écrit $r_{N - 1} = q_{N}r_{N}$, avec $r_{N - 1} > r_{N}$ : le quotient vérifie $q_{N} \geqslant 2$, d'où $r_{N - 1} \geqslant 2r_{N} \geqslant 2$. Enfin, pour $k \leqslant N - 1$, le quotient $q_{k}$ est non nul puisque $r_{k - 1} > r_{k}$, donc $r_{k - 1} = q_{k}r_{k} + r_{k + 1} \geqslant r_{k} + r_{k + 1}$. $$\boxed{r_{N} \geqslant 1 = F_{2}, \qquad r_{N - 1} \geqslant 2 = F_{3}, \qquad r_{k - 1} \geqslant r_{k} + r_{k + 1}}$$

2. On montre par récurrence descendante sur $k$, de $N$ à $1$, que $r_{k} \geqslant F_{N - k + 2}$. C'est vrai pour $k = N$ et $k = N - 1$ d'après la question 1. Si c'est vrai aux rangs $k$ et $k + 1$, avec $k \geqslant 2$, alors $$r_{k - 1} \geqslant r_{k} + r_{k + 1} \geqslant F_{N - k + 2} + F_{N - k + 1} = F_{N - k + 3}.$$ Pour $k = 1$, on obtient $b = r_{1} \geqslant F_{N + 1}$. $$\boxed{b \geqslant F_{N + 1}}$$ Pour $a = 21$ et $b = 13$, l'algorithme comporte $N = 6$ divisions, de quotients $1, 1, 1, 1, 1, 2$, et $F_{7} = 13 = b$ : l'inégalité est une égalité. C'est pourquoi deux nombres de Fibonacci consécutifs sont le cas le plus lent de l'algorithme, comme l'annonçait l'introduction du cours.

3. En itérant la relation de récurrence, $F_{n + 5} = 5F_{n + 1} + 3F_{n} = 8F_{n} + 5F_{n - 1}$. Pour $n \geqslant 2$, on a $F_{n - 1} \geqslant 1$ et $F_{n} = F_{n - 1} + F_{n - 2} \leqslant 2F_{n - 1}$, donc $5F_{n - 1} > 4F_{n - 1} \geqslant 2F_{n}$. $$\boxed{F_{n + 5} = 8F_{n} + 5F_{n - 1} > 10\,F_{n}}$$

4. Par récurrence sur $j$, la question 3 donne $F_{5j + 2} > 10^{j}F_{2} = 10^{j}$ pour tout $j \geqslant 1$. Si $b$ a $k$ chiffres, alors $b < 10^{k}$. Si l'on avait $N \geqslant 5k + 1$, la suite de Fibonacci étant croissante, on aurait $$b \geqslant F_{N + 1} \geqslant F_{5k + 2} > 10^{k},$$ ce qui est absurde. $$\boxed{N \leqslant 5k}$$ À retenir. Le nombre d'étapes de l'algorithme d'Euclide croît comme le nombre de chiffres, c'est-à-dire comme le logarithme des entiers, et non comme les entiers eux-mêmes : c'est ce qui le rend utilisable sur des nombres de plusieurs centaines de chiffres, en cryptographie par exemple.