Problème MPSI : suite de Fibonacci, matrices et pgcd

↩ Chapitre : Arithmétique (MPSI-MP)

Introduction

La suite de Fibonacci 0,1,1,2,3,5,8,13,\dots cache des propriétés arithmétiques surprenantes. Par exemple, le pgcd de deux nombres de Fibonacci est encore un nombre de Fibonacci : \mathrm{pgcd}(F_{12},F_{18})=\mathrm{pgcd}(144,2584)=8=F_6, et 6=\mathrm{pgcd}(12,18).

Le problème démontre cette propriété en passant par les puissances de la matrice \begin{pmatrix}1&1\\1&0\end{pmatrix}, qui donnent l’identité de Cassini et une formule d’addition. On en tire des conséquences sur les nombres de Fibonacci premiers.

Le sujet

Problème pour la MPSI. Durée indicative : 2 heures. Programme : récurrence, produit et déterminant de matrices 2\times2, divisibilité, pgcd, théorème de Bézout, lemme de Gauss, Python.

Niveau : ★★. Faisable : après le chapitre Arithmétique dans ℤ et le calcul matriciel.

Énoncé et corrigé

On définit la suite de Fibonacci par F_0=0, F_1=1 et F_{n+2}=F_{n+1}+F_n pour tout n\in\mathbb N. On note a\wedge b le pgcd de deux entiers naturels, avec la convention a\wedge0=a. On pose M=\begin{pmatrix}1&1\\1&0\end{pmatrix}.

Partie I – Matrices et identité de Cassini

1 ▷ Montrer que M^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} pour tout n\geqslant1. En déduire l’identité de Cassini : F_{n+1}F_{n-1}-F_n^2=(-1)^n.

Indication

Récurrence en calculant M^{n+1}=M^n\,M. Pour Cassini, prendre le déterminant.

Corrigé

Pour n=1 : M=\begin{pmatrix}F_2&F_1\\F_1&F_0\end{pmatrix} car F_2=1. Si la formule est vraie au rang n : M^{n+1}=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}F_{n+1}+F_n&F_{n+1}\\F_n+F_{n-1}&F_n\end{pmatrix}=\begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{pmatrix}.

\det(M^n)=(\det M)^n=(-1)^n et \det(M^n)=F_{n+1}F_{n-1}-F_n^2. Par exemple, pour n=5 : 8\times3-5^2=-1.

2 ▷ En déduire que F_n\wedge F_{n+1}=1 pour tout n\geqslant1.

Indication

Écrire l’identité de Cassini comme une relation de Bézout.

Corrigé

(-1)^n\left(F_{n+1}F_{n-1}-F_nF_n\right)=1 s’écrit uF_{n+1}+vF_n=1 avec u=(-1)^nF_{n-1} et v=(-1)^{n+1}F_n entiers. Par le théorème de Bézout, F_n\wedge F_{n+1}=1.

Partie II – Le pgcd de deux nombres de Fibonacci

3 ▷ À l’aide de l’égalité M^{m+n}=M^m\,M^n, montrer que pour tous m,n\geqslant1 : F_{m+n}=F_{m+1}F_n+F_mF_{n-1}.

Indication

Comparer les coefficients en position (1,2).

Corrigé

Le coefficient (1,2) de M^{m+n} est F_{m+n}. Celui de M^mM^n est le produit de la première ligne (F_{m+1},F_m) de M^m par la deuxième colonne {}^t(F_n,F_{n-1}) de M^n, soit F_{m+1}F_n+F_mF_{n-1}.

4 ▷ Montrer que F_{m+n}\wedge F_n=F_m\wedge F_n pour tous m\geqslant0 et n\geqslant1.

Indication

Un diviseur commun de F_{m+n} et F_n divise F_mF_{n-1} ; utiliser le lemme de Gauss avec la question 2.

Corrigé

Le cas m=0 est évident. Pour m\geqslant1, soit d un diviseur commun de F_n et de F_{m+n}. Par la question 3, d divise F_{m+n}-F_{m+1}F_n=F_mF_{n-1}. Comme d divise F_n et que F_n\wedge F_{n-1}=1, on a d\wedge F_{n-1}=1 ; le lemme de Gauss donne d\mid F_m.

Réciproquement, un diviseur commun de F_m et F_n divise F_{m+1}F_n+F_mF_{n-1}=F_{m+n}.

Les couples (F_{m+n},F_n) et (F_m,F_n) ont les mêmes diviseurs communs, donc le même pgcd.

5 ▷ Montrer que F_m\wedge F_n=F_{m\wedge n} pour tous m,n\in\mathbb N.

Indication

Récurrence forte sur m+n. Si m>n\geqslant1, appliquer la question 4 avec m-n à la place de m, et utiliser m\wedge n=(m-n)\wedge n.

Corrigé

Si n=0 : F_m\wedge F_0=F_m\wedge0=F_m=F_{m\wedge0}. Même chose si m=0, et si m=n c’est immédiat.

Supposons le résultat vrai pour tous les couples de somme <m+n, avec par exemple m>n\geqslant1. La question 4 appliquée à (m-n,n) donne F_m\wedge F_n=F_{m-n}\wedge F_n, et par hypothèse de récurrence F_{m-n}\wedge F_n=F_{(m-n)\wedge n}=F_{m\wedge n}.

C’est l’algorithme d’Euclide « par soustractions », appliqué simultanément aux indices et aux nombres de Fibonacci. Exemple : F_{12}\wedge F_{18}=F_6=8.

Partie III – Conséquences

6 ▷ Montrer que si n divise m, alors F_n divise F_m. Montrer que si n\geqslant5 et F_n est premier, alors n est premier. La réciproque est-elle vraie ? On pourra calculer F_{19} et vérifier que 4181=37\times113.

Indication

Si n\mid m, alors m\wedge n=n. Pour la deuxième partie, écrire n=ab avec 2\leqslant a\leqslant b et justifier que b\geqslant3.

Corrigé

Si n\mid m, alors F_m\wedge F_n=F_n, donc F_n\mid F_m. Par exemple F_3=2, F_4=3 et F_6=8 divisent F_{12}=144.

Soit n\geqslant5 non premier : n=ab avec 2\leqslant a\leqslant b<n. Si b=2, alors n=4, exclu ; donc b\geqslant3. Alors F_b\mid F_n, et 2\leqslant F_b<F_n car la suite (F_k)_{k\geqslant2} est strictement croissante. Donc F_n n’est pas premier. Par contraposée, si F_n est premier, n est premier.

La réciproque est fausse : 19 est premier, mais F_{19}=4181=37\times113. (L’hypothèse n\geqslant5 est nécessaire : F_4=3 est premier.)

7 ▷ (Python) Vérifier numériquement la question 5 pour tous m,n\leqslant60 à l’aide de math.gcd.

Indication

Construire la liste des F_k, puis tester toutes les paires.

Corrigé
import math

F = [0, 1]
for k in range(2, 61):
    F.append(F[-1] + F[-2])

ok = all(math.gcd(F[m], F[n]) == F[math.gcd(m, n)]
         for m in range(61) for n in range(61))
print(ok)

Le programme affiche True : les 61^2 égalités sont vérifiées.


Pour aller plus loin

Pr. Elakili, agrégé de mathématiques et professeur en classes préparatoires depuis 25 ans, accompagne aussi quelques étudiants vers les écoles d’ingénieurs, à Casablanca et à distance. En savoir plus

Publications similaires