Exercice 23

1. Par récurrence : $F_{0} \wedge F_{1} = 0 \wedge 1 = 1$, et si $F_{n} \wedge F_{n + 1} = 1$, alors, d'après la proposition 4, $$F_{n + 1} \wedge F_{n + 2} = F_{n + 1} \wedge (F_{n + 2} - F_{n + 1}) = F_{n + 1} \wedge F_{n} = 1.$$

2. On fixe $n$ et l'on raisonne par récurrence double sur $m$. Pour $m = 1$, $F_{1}F_{n + 1} + F_{0}F_{n} = F_{n + 1}$ ; pour $m = 2$, $F_{2}F_{n + 1} + F_{1}F_{n} = F_{n + 1} + F_{n} = F_{n + 2}$. Si la formule est vraie aux rangs $m$ et $m + 1$, on les additionne : $$F_{n + m + 2} = F_{n + m + 1} + F_{n + m} = (F_{m + 1} + F_{m})F_{n + 1} + (F_{m} + F_{m - 1})F_{n} = F_{m + 2}F_{n + 1} + F_{m + 1}F_{n}.$$

3. Par la question 2 et la proposition 4, $F_{n} \wedge F_{n + m} = F_{n} \wedge (F_{m}F_{n + 1})$, puisque l'on retranche un multiple de $F_{n}$. Un diviseur commun à $F_{n}$ et $F_{m}$ divise évidemment $F_{m}F_{n + 1}$. Réciproquement, un diviseur commun $c$ à $F_{n}$ et $F_{m}F_{n + 1}$ est premier avec $F_{n + 1}$, puisqu'il divise $F_{n}$ et que $F_{n} \wedge F_{n + 1} = 1$ ; le lemme de Gauss donne $c \mid F_{m}$. Les deux couples ont donc les mêmes diviseurs communs. $$\boxed{F_{n} \wedge F_{n + m} = F_{n} \wedge F_{m}}$$

4. Si $m = qn + r$, on applique $q$ fois la question 3, en retranchant $n$ à l'indice à chaque fois : $$F_{n} \wedge F_{m} = F_{n} \wedge F_{m - n} = \cdots = F_{n} \wedge F_{r}.$$ Au dernier pas, si $r = 0$, on utilise directement $F_{n} \wedge F_{n} = F_{n} = F_{n} \wedge F_{0}$.

5. La question 4 dit que le couple $(F_{m}, F_{n})$ se transforme comme le couple $(m, n)$ dans l'algorithme d'Euclide. On raisonne par récurrence forte sur $n$, pour tout $m$. Si $n \mid m$, alors $r = 0$ et $F_{n} \wedge F_{m} = F_{n} \wedge 0 = F_{n} = F_{n \wedge m}$. Sinon, $1 \leqslant r < n$, et l'hypothèse de récurrence appliquée au couple $(n, r)$ donne $$F_{n} \wedge F_{m} = F_{r} \wedge F_{n} = F_{r \wedge n} = F_{n \wedge m},$$ la dernière égalité venant de la proposition 4. $$\boxed{F_{n} \wedge F_{m} = F_{n \wedge m}}$$ Par exemple, $F_{12} \wedge F_{18} = 144 \wedge 2584 = 8 = F_{6}$. ✓

À retenir. Le choix $F_{0} = 0$, $F_{1} = 1$ est essentiel. Avec la convention décalée $F_{0} = F_{1} = 1$, le résultat devient faux : on aurait $F_{2} \wedge F_{4} = 2 \wedge 5 = 1$, alors que $F_{2 \wedge 4} = F_{2} = 2$.