Problème — La matrice de Fibonacci : identité de Cassini, formule d'addition, et le PGCD de Fibonacci

Exercice de TD · niveau 3 (difficile) · mathématiques MPSI, chapitre 9 — Calcul matriciel et systèmes linéaires · E. Problèmes et applications

Énoncé

Soit $F = (1110)$ et $(F_{n})_{n \in N}$ la suite de Fibonacci, $F_{0} = 0$ , $F_{1} = 1$ , $F_{n + 2} = F_{n + 1} + F_{n}$ (ainsi $F_{2} = 1$ , $F_{3} = 2$ , $F_{4} = 3$ , $F_{5} = 5$ , $F_{6} = 8$ , $F_{7} = 13$ ).

1) Montrer que pour tout $n \geq 1$ : $F^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1})$ .

2) Pour $M = (a c b d) \in M_{2} (K)$ , on pose $δ (M) = a d - b c$ (le nombre que le cours associe à une matrice $2 \times 2$ ). Vérifier par le calcul que $δ (M N) = δ (M) δ (N)$ .

3) En déduire l'identité de Cassini : $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ pour $n \geq 1$ . Vérifier pour $n = 5$ et $n = 6$ . En déduire, par Bézout, que $F_{n} \land F_{n + 1} = 1$ .

4) En écrivant $F^{m + n} = F^{m} F^{n}$ et en identifiant un coefficient, établir la formule d'addition : $F_{m + n} = F_{m + 1} F_{n} + F_{m} F_{n - 1}$ pour $m, n \geq 1$ . En déduire, par récurrence sur $q$ , que $F_{n}$ divise $F_{q n}$ pour tout $q \geq 1$ ; puis que, pour $n \geq 5$ , si $F_{n}$ est premier alors $n$ est premier.

5) Soit $m = q n + r$ la division euclidienne de $m$ par $n$ , avec $q \geq 1$ et $1 \leq r < n$ . Montrer que $F_{m} \equiv F_{q n + 1} F_{r} (mod F_{n})$ , puis que $F_{q n + 1} \land F_{n} = 1$ , et conclure $F_{m} \land F_{n} = F_{r} \land F_{n}$ . En déduire, comme dans l'algorithme d'Euclide, que $F_{m} \land F_{n} = F_{m \land n}$ .

6) Expliquer comment calculer $F_{n}$ avec environ $2 lo g_{2} n$ produits de matrices, et pourquoi c'est bien plus rapide que la récurrence.

Corrigé

1) Les puissances de $F$ . Par récurrence sur $n \geq 1$ . Initialisation : $F^{1} = (F_{2} F_{1} F_{1} F_{0}) = (1110)$ , ce qui est bien $F$ . Hérédité : si la formule vaut au rang $n$ , $F^{n + 1} = F \cdot F^{n} = (1110) (F_{n + 1} F_{n} F_{n} F_{n - 1}) = (F_{n + 1} + F_{n} F_{n + 1} F_{n} + F_{n - 1} F_{n}) = (F_{n + 2} F_{n + 1} F_{n + 1} F_{n}),$ par la relation de récurrence. Ce qui achève la récurrence. La récurrence de Fibonacci est encodée dans la première ligne de $F$ .

2) La multiplicativité de $δ$ . Avec $N = (a^{'} c^{'} b^{'} d^{'})$ , $M N = (a a^{'} + b c^{'} c a^{'} + d c^{'} a b^{'} + b d^{'} c b^{'} + d d^{'})$ , donc $δ (M N) = (a a^{'} + b c^{'}) (c b^{'} + d d^{'}) - (a b^{'} + b d^{'}) (c a^{'} + d c^{'}) .$ Développons : le premier produit donne $a a^{'} c b^{'} + a a^{'} d d^{'} + b c^{'} c b^{'} + b c^{'} d d^{'}$ , le second $a b^{'} c a^{'} + a b^{'} d c^{'} + b d^{'} c a^{'} + b d^{'} d c^{'}$ . Les termes $a a^{'} c b^{'}$ et $a b^{'} c a^{'}$ se détruisent, ainsi que $b c^{'} d d^{'}$ et $b d^{'} d c^{'}$ . Il reste $δ (M N) = a a^{'} d d^{'} + b c b^{'} c^{'} - a b^{'} d c^{'} - b d^{'} c a^{'} = a d (a^{'} d^{'} - b^{'} c^{'}) - b c (a^{'} d^{'} - b^{'} c^{'}) = (a d - b c) (a^{'} d^{'} - b^{'} c^{'}) = δ (M) δ (N) .$ La multiplicativité est vérifiée — par un calcul direct, sans aucune théorie du déterminant, qui viendra au chapitre 14.

3) Cassini, et deux Fibonacci consécutifs sont premiers entre eux. $δ (F) = 1 \cdot 0 - 1 \cdot 1 = - 1$ . Par le 2) et une récurrence immédiate, $δ (F^{n}) = δ (F)^{n} = (- 1)^{n}$ . Par le 1), $δ (F^{n}) = F_{n + 1} F_{n - 1} - F_{n}^{2}$ . Donc $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ pour tout $n \geq 1$ . Pour $n = 5$ : $F_{6} F_{4} - F_{5}^{2} = 8 \cdot 3 - 25 = - 1 = (- 1)^{5}$ . Pour $n = 6$ : $F_{7} F_{5} - F_{6}^{2} = 13 \cdot 5 - 64 = 65 - 64 = 1 = (- 1)^{6}$ . (C'est le secret du puzzle « $64 = 65$ » : un carré de côté $8 = F_{6}$ redécoupé en quatre pièces qui semblent former un rectangle $5 \times 13 = F_{5} \times F_{7}$ ; l'unité d'aire manquante est cachée le long d'une diagonale, et Cassini dit qu'elle vaut exactement $1$ .) Bézout : l'identité s'écrit $(- 1)^{n} F_{n - 1} \cdot F_{n + 1} + (- (- 1)^{n} F_{n}) \cdot F_{n} = 1$ , une relation de Bézout entre $F_{n}$ et $F_{n + 1}$ à coefficients entiers. Donc $F_{n} \land F_{n + 1} = 1$ .

4) La formule d'addition et ses conséquences. Comme $F^{m + n} = F^{m} F^{n}$ (associativité, ou règle $x^{m + n} = x^{m} x^{n}$ dans un anneau), identifions le coefficient $(1, 2)$ des deux membres. À gauche, par le 1), c'est $F_{m + n}$ . À droite, c'est $(F^{m})_{1, 1} (F^{n})_{1, 2} + (F^{m})_{1, 2} (F^{n})_{2, 2} = F_{m + 1} F_{n} + F_{m} F_{n - 1}$ . Donc $F_{m + n} = F_{m + 1} F_{n} + F_{m} F_{n - 1}$ .

$F_{n}$ divise $F_{q n}$ . Par récurrence sur $q \geq 1$ . Pour $q = 1$ , $F_{n} ∣ F_{n}$ . Si $F_{n} ∣ F_{q n}$ , la formule d'addition avec $m = q n$ donne $F_{(q + 1) n} = F_{q n + n} = F_{q n + 1} F_{n} + F_{q n} F_{n - 1}$ : le premier terme est un multiple de $F_{n}$ , le second aussi par hypothèse. Donc $F_{n} ∣ F_{q n}$ pour tout $q \geq 1$ .

Si $F_{n}$ est premier avec $n \geq 5$ , alors $n$ est premier. Par contraposée : soit $n \geq 5$ composé, $n = ab$ avec $2 \leq a \leq b$ . Alors $b \geq 3$ (car $ab \geq 6$ et $a \leq b$ forcent $b^{2} \geq 6$ ), et $b < n$ (car $a \geq 2$ ). Par ce qui précède, $F_{b}$ divise $F_{n} = F_{ab}$ . Or la suite est strictement croissante à partir de l'indice $2$ ( $F_{3} = 2 < F_{4} = 3 < \dots$ ), donc $2 = F_{3} \leq F_{b} < F_{n}$ : $F_{b}$ est un diviseur de $F_{n}$ strictement compris entre $1$ et $F_{n}$ , et $F_{n}$ n'est pas premier. (La borne $n \geq 5$ est nécessaire : $F_{4} = 3$ est premier alors que $4$ ne l'est pas — c'est parce que $F_{2} = 1$ divise tout sans rien dire.)

5) L'algorithme d'Euclide transporté. La congruence. La formule d'addition avec les indices $q n \geq 1$ et $r \geq 1$ donne $F_{m} = F_{q n + r} = F_{q n + 1} F_{r} + F_{q n} F_{r - 1}$ . Comme $F_{n} ∣ F_{q n}$ par le 4), le second terme est un multiple de $F_{n}$ : $F_{m} \equiv F_{q n + 1} F_{r} (mod F_{n})$ .

$F_{q n + 1}$ et $F_{n}$ sont premiers entre eux. Par le 3) à l'indice $q n$ , $F_{q n + 1} \land F_{q n} = 1$ . Un diviseur commun de $F_{q n + 1}$ et de $F_{n}$ divise aussi $F_{q n}$ (multiple de $F_{n}$ ), donc divise $F_{q n + 1} \land F_{q n} = 1$ . Donc $F_{q n + 1} \land F_{n} = 1$ .

Conclusion. Comme $F_{m}$ et $F_{q n + 1} F_{r}$ diffèrent d'un multiple de $F_{n}$ , ils ont les mêmes diviseurs communs avec $F_{n}$ (chapitre 7 : $a \land b = (a + k b) \land b$ ), donc $F_{m} \land F_{n} = (F_{q n + 1} F_{r}) \land F_{n}$ . Soit $d$ un diviseur commun de $F_{q n + 1} F_{r}$ et de $F_{n}$ ; comme $F_{q n + 1} \land F_{n} = 1$ , on a $d \land F_{q n + 1} = 1$ , et le lemme de Gauss donne $d ∣ F_{r}$ . Réciproquement tout diviseur commun de $F_{r}$ et $F_{n}$ divise $F_{q n + 1} F_{r}$ et $F_{n}$ . Les deux couples ont les mêmes diviseurs communs : $F_{m} \land F_{n} = F_{r} \land F_{n}$ .

Le théorème. Le couple d'indices $(m, n)$ est remplacé par $(n, r)$ , exactement comme dans une étape de l'algorithme d'Euclide sur $(m, n)$ ; si $r = 0$ , alors $n ∣ m$ , $F_{n} ∣ F_{m}$ par le 4), et $F_{m} \land F_{n} = F_{n} = F_{m \land n}$ . En itérant, les indices suivent l'algorithme d'Euclide, qui s'arrête sur le couple $(m \land n, 0)$ , et l'on obtient $F_{m} \land F_{n} = F_{m \land n}$ . Par exemple $F_{12} \land F_{18} = F_{6} = 8$ : et de fait $F_{12} = 144 = 8 \cdot 18$ , $F_{18} = 2584 = 8 \cdot 323$ , avec $18 \land 323 = 1$ car $323 = 17 \cdot 19$ .

6) L'exponentiation rapide. Pour calculer $F^{n}$ , on n'effectue pas $n - 1$ produits : on écrit $F^{2 k} = (F^{k})^{2}$ et $F^{2 k + 1} = F \cdot F^{2 k}$ . Chaque étape divise l'exposant par $2$ (au prix d'un ou deux produits), et il y a environ $lo g_{2} n$ étapes : environ $2 lo g_{2} n$ produits de matrices $2 \times 2$ au plus, contre $n - 1$ additions pour la récurrence. Pour $n = 1000$ , cela fait une vingtaine de produits contre un millier d'additions ; pour $n = 1 0^{6}$ , une quarantaine contre un million. Le coût de chaque produit augmente avec la taille des nombres, mais le nombre d'opérations, lui, est logarithmique — c'est l'exponentiation rapide du cours d'informatique, appliquée à une matrice.

Le théorème obtenu — identité de Cassini (1680) et théorème de Lucas. Pour tout $n \geq 1$ , $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ ; et pour tous $m, n \geq 1$ , $F_{m} \land F_{n} = F_{m \land n}$ : le PGCD de deux nombres de Fibonacci est le nombre de Fibonacci d'indice le PGCD des indices.

Ce que le problème installe. Une matrice $2 \times 2$ démontre de l'arithmétique : la récurrence de Fibonacci, mise dans une matrice, transforme l'associativité $F^{m + n} = F^{m} F^{n}$ en une formule d'addition, et la multiplicativité de $a d - b c$ en une identité de Bézout. Le reste est l'algorithme d'Euclide, transporté des indices aux valeurs — le même transport qu'au TD 7 pour les nombres $2^{a} - 1$ . On retiendra que « $a d - b c$ est multiplicatif » n'est pas un accident du cas $2 \times 2$ : le chapitre 14 en fera le déterminant, et sa multiplicativité, un théorème.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.