↩ Chapitre : Arithmétique (MPSI-MP)
Introduction
La suite de Fibonacci
cache des propriétés arithmétiques surprenantes. Par exemple, le pgcd de deux nombres de Fibonacci est encore un nombre de Fibonacci :
, et
.
Le problème démontre cette propriété en passant par les puissances de la matrice
, 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
, 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
,
et
pour tout
. On note
le pgcd de deux entiers naturels, avec la convention
. On pose
.
Partie I – Matrices et identité de Cassini
1 ▷ Montrer que
pour tout
. En déduire l’identité de Cassini :
.
Indication
Récurrence en calculant
. Pour Cassini, prendre le déterminant.
Corrigé
Pour
:
car
. Si la formule est vraie au rang
:
.
et
. Par exemple, pour
:
.
2 ▷ En déduire que
pour tout
.
Indication
Écrire l’identité de Cassini comme une relation de Bézout.
Corrigé
s’écrit
avec
et
entiers. Par le théorème de Bézout,
.
Partie II – Le pgcd de deux nombres de Fibonacci
3 ▷ À l’aide de l’égalité
, montrer que pour tous
:
.
Indication
Comparer les coefficients en position
.
Corrigé
Le coefficient
de
est
. Celui de
est le produit de la première ligne
de
par la deuxième colonne
de
, soit
.
4 ▷ Montrer que
pour tous
et
.
Indication
Un diviseur commun de
et
divise
; utiliser le lemme de Gauss avec la question 2.
Corrigé
Le cas
est évident. Pour
, soit
un diviseur commun de
et de
. Par la question 3,
divise
. Comme
divise
et que
, on a
; le lemme de Gauss donne
.
Réciproquement, un diviseur commun de
et
divise
.
Les couples
et
ont les mêmes diviseurs communs, donc le même pgcd.
5 ▷ Montrer que
pour tous
.
Indication
Récurrence forte sur
. Si
, appliquer la question 4 avec
à la place de
, et utiliser
.
Corrigé
Si
:
. Même chose si
, et si
c’est immédiat.
Supposons le résultat vrai pour tous les couples de somme
, avec par exemple
. La question 4 appliquée à
donne
, et par hypothèse de récurrence
.
C’est l’algorithme d’Euclide « par soustractions », appliqué simultanément aux indices et aux nombres de Fibonacci. Exemple :
.
Partie III – Conséquences
6 ▷ Montrer que si
divise
, alors
divise
. Montrer que si
et
est premier, alors
est premier. La réciproque est-elle vraie ? On pourra calculer
et vérifier que
.
Indication
Si
, alors
. Pour la deuxième partie, écrire
avec
et justifier que
.
Corrigé
Si
, alors
, donc
. Par exemple
,
et
divisent
.
Soit
non premier :
avec
. Si
, alors
, exclu ; donc
. Alors
, et
car la suite
est strictement croissante. Donc
n’est pas premier. Par contraposée, si
est premier,
est premier.
La réciproque est fausse :
est premier, mais
. (L’hypothèse
est nécessaire :
est premier.)
7 ▷ (Python) Vérifier numériquement la question 5 pour tous
à l’aide de math.gcd.
Indication
Construire la liste des
, 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
égalités sont vérifiées.
