La suite de Fibonacci

La suite de Fibonacci — bien connue de ceux qui la connaissent bien, comme dirait un célèbre collègue New-Yorkais — commence ainsi :

\[ 0,\, 1,\, 1,\, 2,\, 3,\, 5,\, 8,\, 13,\, 21,\, 34,\, 55,\, 89,\, 144,\, 233,\, ... \]

Ses deux premiers termes sont $0$ et $1$, et ensuite, chaque terme successif est la somme des deux termes précédents. Ainsi $0+1=1$, $1+1 = 2$, $1 + 2 = 3$, $2 + 3 = 5$, $3 + 5 = 8$, etc.

Comme c’est la coutume, nous dénoterons par $F_n$ le $n$-ème terme de cette suite, en commençant par $n = 0$. Ainsi donc, la suite de Fibonacci $F_0$, $F_1$, $F_2$, $\dots$ peut être entièrement définie par les formules suivantes :
\[ \begin{eqnarray*} F_0 & = & 0 \\ F_1 & = & 1 \\ F_n & = & F_{n-2}+F_{n-1} \,\,\, \text{ pour } n \ge 2. \end{eqnarray*} \]

Son inventeur est Léonard de Pise (1175 $-$ v.1250), aussi connu sous le nom de Leonardo Fibonacci, qui a rapporté d’Orient la notation numérique indo-arabe et a écrit et traduit des livres influents de mathématiques.

Introduite comme problème récréatif dans son fameux ouvrage Liber Abaci, la suite de Fibonacci peut être considérée comme le tout premier modèle mathématique en dynamique des populations ! En effet, elle y décrit la croissance d’une population de lapins sous des hypothèses très simplifiées, à savoir : chaque couple de lapins, dès son troisième mois d’existence, engendre chaque mois un nouveau couple de lapins, et ce indéfiniment.

Partons donc d’un couple de lapins le premier mois. Le deuxième mois, on n’a toujours que ce même couple, mais le troisième mois on a déjà $2$ couples, puis $3$ couples le quatrième mois, $5$ couples le cinquième mois, etc. La croissance de cette population est bel et bien décrite par la suite de Fibonacci.

Les nombres premiers

Rappelons qu’un nombre premier est un nombre entier naturel possédant exactement deux diviseurs entiers naturels, à savoir 1 et lui-même — ce qui exclut 1 comme nombre premier. La suite des nombres premiers commence ainsi :

\[ 2,\, 3,\, 5,\, 7,\, 11,\, 13,\, 17,\, 19,\, 23,\, 29,\, 31,\, \dots . \]
Ces nombres sont les briques fondamentales à partir desquelles on peut obtenir, par multiplication, tous les autres nombres entiers positifs. Par exemple, $24$ s’obtient en multipliant entre eux les nombres premiers $2$ (répété trois fois) et $3$ :
\[ 24 \,=\, 2 \times 2 \times 2 \times 3. \]

Une première question

L’un des premiers mystères arithmétiques de la suite de Fibonacci est le suivant :

Question. La suite de Fibonacci contient-elle une infinité de nombres premiers ?

On l’ignore ! On sait seulement que si $F_n$ est premier, alors $n$ est lui-même premier. Mais la réciproque n’est pas vraie ; par exemple, $n=19$ est premier alors que $F_{19}$ ne l’est pas, puisque
\[F_{19} \, = \, 4\:181\, =\, 37 \times 113.\]

Plus généralement, on aimerait beaucoup comprendre les propriétés arithmétiques des nombres de Fibonacci $F_n$. Par exemple, si l’on se donne un nombre premier $p$, quels sont tous les $F_n$ qui sont divisibles par $p$ ? Y en a-t-il une infinité ? Et parmi eux, quels sont ceux qui sont divisibles par $p^2$ ? La conjecture qui nous occupera ici concerne précisément ces questions.

La conjecture

Voici donc la conjecture principale de cet article. Elle pourra paraître un peu mystérieuse de prime abord, mais on verra plus loin qu’elle a une très intéressante interprétation en termes de longueurs de certaines périodes.

Conjecture 1. Soit $p$ un nombre premier. Alors la suite de Fibonacci contient un terme $F_n$ qui est divisible par $p$ mais pas par $p^2$.

Voyons donc ce qu’il en est sur les nombres premiers inférieurs à $10$, à savoir $p = $ $2$, $3$, $5$ et $7$.

• Pour $p=2$ : on a $F_3 = 2$, divisible par $2$ mais pas par $4$.

• Pour $p=3$ : on a $F_4 = 3$, divisible par $3$ mais pas par $9$.

• Pour $p=5$ : on a $F_5 = 5$, divisible par $5$ mais pas par $25$.

• Pour $p=7$ : on a $F_8 = 21$, divisible par $7$ mais pas par $49$.

Qu’en est-il, maintenant, des $F_n$ qui sont divisibles par les carrés de ces premiers nombres premiers ?

Le plus petit nombre de Fibonacci non-nul divisible par $4$ est $F_6 = 8$. Et pour $p = 3$, $5$ et $7$, il faut attendre jusqu’à
\[ F_{12} \,=\, 144,\quad F_{25} \,=\, 75\:025\quad \text{ et } \quad F_{56} \,=\, 225\:851\:433\:717 \,=\, 49 \times 4\:609\:212\:933 \]
pour trouver un nombre de Fibonacci divisible par $9$, $25$ et $49$ respectivement.

Comme ces observations le suggèrent, la Conjecture 1 est en fait équivalente à la formulation un peu plus précise suivante.

Conjecture 2. Soit $p$ un nombre premier. Alors le premier nombre de Fibonacci $F_n$ non-nul et divisible par $p$ n’est pas divisible par $p^2$.

Cette conjecture se prête bien à une vérification partielle par ordinateur, comme le montrera implicitement la suite de l’article. Donald D. Wall, son auteur, l’a vérifiée en 1960 pour tous les premiers $p$ jusqu’à $10^4=10\:000$ [1], et cette vérification a été étendue en 2007 à tous les premiers $p$ jusqu’à $2 \times 10^{14}$ [2]. Pourtant, depuis plus d’un demi-siècle maintenant, personne n’est en mesure d’en fournir une démonstration !

Le Nombre d’Or

Pour qui souhaiterait tester cette conjecture sans trop réfléchir au début, un obstacle apparaît aussitôt : la suite de Fibonacci croît très vite, de façon exponentielle.

Quel est son taux de croissance, justement ? Il se trouve qu’on le connaît très bien, et qu’il tend vers le Nombre d’Or. Rappelons que cette célèbre constante, généralement dénotée $\varphi$, est définie ainsi :
\[ \varphi \,=\, \frac{\sqrt{5}+1}2. \]
En voici une valeur approchée, avec ses dix premières décimales :
\[ \varphi \,\sim\, 1,6180339887\dots \]
On peut montrer que le rapport de deux nombres de Fibonacci successifs, soit $\displaystyle \frac{F_{n+1}}{F_n}$, tend effectivement vers $\varphi$ lorsque $n$ grandit. Par exemple, pour $n=20$, on a
\[ \frac{F_{21}}{F_{20}} \,=\, \frac{10\:946}{6\:765} \,\sim\, 1,\color{red}{6180339}985218033\dots, \]
concordant avec $\varphi$ sur ses 7 premières décimales. Et à partir de $n = 26$ déjà, cette concordance entre $\displaystyle \frac{F_{n+1}}{F_n}$ et $\varphi$ s’étend à leurs $10$ premières décimales, au moins.

Arithmétique modulaire

Un moyen très simple de contourner cet obstacle de croissance rapide, c’est d’utiliser la réduction modulo $m$, un outil classique en théorie des nombres.

De quoi s’agit-il ? Commençons par un exemple : la réduction de $167$ modulo $10$ vaut $7$, son dernier chiffre.

En toute généralité, donnons-nous un entier naturel $m$ non nul, le « module ». Alors, pour tout nombre entier $n$, la réduction de $n$ modulo $m$, appelée aussi la classe de $n$ modulo $m$, est définie comme étant le reste de la division euclidienne de $n$ par $m$.

Ainsi par exemple, pour le module $m=2$, la classe d’un entier $n$ modulo 2 révèle sa parité : cette classe vaut 0 si $n$ est pair, et elle vaut 1 si $n$ est impair. Et pour $m=10$, la classe de $n$ modulo $10$ donne son dernier chiffre, comme on l’a vu pour 167.

Notons que la suite des entiers naturels devient périodique lorsqu’on la réduit modulo $m$. Par exemple, voici ce que l’on obtient pour $m=3$ :
\[ \begin{eqnarray*} \text{ avant réduction : } & 0, & 1, & 2, & 3, & 4, & 5, & 6, & 7, & 8, & 9, & 10, & \dots\\ \text{ après réduction : } & \color{red}{0,} & \color{red}{1,} & \color{red}{2}, & 0, & 1, & 2, & 0, & 1, & 2, & 0, & 1, & \dots. \end{eqnarray*} \]
On obtient une suite périodique de longueur 3, avec période $\color{red}{0, 1, 2}$ se répétant indéfiniment, tout simplement.

Un avantage majeur de la réduction modulo $m$ est que, par définition même, le résultat reste confiné entre les entiers $0, 1, \dots, m-1$.

C’est un homomorphisme !

Une propriété fondamentale de la réduction modulo $m$ est sa compatibilité avec l’addition, dans le sens précisé ci-dessous.

Mais introduisons d’abord une notation utile pour la discussion. Pour tout entier $n$, notons $cl(n)$ sa réduction ou sa classe modulo $m$ [3].

Soient maintenant $a$ et $b$ deux nombres entiers. Alors, il se trouve que pour calculer la classe de $a+b$ modulo $m$, c’est-à-dire pour déterminer $cl(a+b)$, il suffit

• de déterminer $cl(a)$ et $cl(b)$,
• de calculer leur somme, c’est-à-dire $cl(a)+cl(b)$,
• puis de réduire le résultat modulo $m$.

Une courte formule le dira bien mieux :
\[ \begin{equation} cl\left(\,a+b\,\right) \,=\, cl\left(\, cl(a) + cl(b)\, \right). \end{equation} \]

Par exemple, pour $m=2$, cette formule revient à dire ce que tout lecteur de cet article sait bien, à savoir que

pair + pair = pair,

pair + impair = impair,

impair + impair = pair.

L’avantage de cette propriété est clair : pour réduire une somme modulo $m$, on peut commencer par réduire les sommants eux-mêmes modulo $m$, ce qui facilite généralement les choses en permettant de travailler avec des nombres plus petits.

Appliquée au calcul de la suite de Fibonacci réduite modulo $m$, cette propriété se révèle décisive ! Ainsi, pour $m = 3$ par exemple, et pour construire la suite de Fibonacci modulo $3$, il n’est nul besoin de calculer les vrais nombres de Fibonacci avant réduction ; il suffit de réduire modulo $3$ à chaque étape. Allons-y donc : sachant que
\[ \begin{eqnarray*} 1+1 & = 2 & \text{ modulo } 3,\\ 1+2 & = 0 & \text{ modulo } 3,\\ 2+2 & = 1 & \text{ modulo } 3, \end{eqnarray*} \]
et qu’additionner $0$ modulo $3$ ne change rien, comme pour l’addition ordinaire de $0$, la suite de Fibonacci modulo $3$ se réduit à cela :
\[ \color{red}{0,\, 1},\, 1,\, 2,\, 0,\, 2,\, 2,\, 1,\, \color{red}{0,\, 1},\, 1,\, 2,\, 0,\, 2,\, 2,\, 1,\, \color{red}{0,\, 1},\, 1, \, 2,\, 0,\, 2,\, 2,\, 1,\, \color{red}{0,\, 1},\,1, \, \dots \]
On démarre avec $0,1$ et chaque terme successif est la somme — modulo $3$, bien entendu — des deux termes précédents.

La structure obtenue est très simple : c’est une suite périodique, avec période $0,\, 1,\, 1,\, 2,\, 0,\, 2,\, 2,\, 1$ de longueur $8$, se répétant indéfiniment. Et pour la découvrir, encore une fois, il n’a nullement été besoin de calculer explicitement les vrais nombres de Fibonacci ! C’est là l’intérêt majeur du fait que la réduction modulo $3$, ou plus généralement modulo $m$, est compatible avec l’addition.

En termes savants, on dit que la réduction modulo $m$ est un homomorphisme, justement en vertu de sa compatibilité avec l’addition telle qu’exprimée par la formule (1) ci-dessus.

Dès lors, on comprend mieux pourquoi les mathématiciens sont si friands d’homomorphismes. Comme on le voit dans cet exemple, c’est parce que ceux-ci, lorsqu’ils sont disponibles, permettent à différentes structures mathématiques d’interagir entre elles de façon cohérente [4].

Périodicité

Nous voilà confrontés à une question toute naturelle : est-il vrai que, pour toute autre valeur du module $m$, la suite de Fibonacci réduite modulo $m$ devient elle aussi périodique ?

Testons encore le cas $m=2$, pour voir. Un simple calcul montre qu’on obtient à nouveau une suite périodique, ici avec une période de longueur $3$ :

\[ \color{red}{0,\, 1},\, 1,\, \color{red}{0,\, 1}, \, 1,\, \color{red}{0,\, 1},\, 1,\, \dots . \]

Cette structure révèle d’ailleurs le fait qu’une fois sur trois, soit pour $n=0, 3, 6, 9$, etc., le nombre de Fibonacci $F_n$ est pair, et que dans les autres cas il est impair.

On peut s’en douter, ce phénomène de périodicité est tout à fait général. C’est Lagrange qui semble l’avoir observé en premier il y a plus de deux siècles.

Théorème. Pour tout entier naturel $m$, la suite de Fibonacci réduite modulo $m$ est périodique.

Une conséquence

Une conséquence intéressante de cette périodicité est que, pour tout entier naturel $m$, il existe une infinité de nombres de Fibonacci $F_n$ qui sont divisibles par $m$.

En effet, comme la suite commence par $0$, et qu’elle est périodique modulo $m$, il suit que le $0$ va se retrouver une infinité de fois dans la suite réduite modulo $m$. Or un nombre donnant $0$ modulo $m$ n’est rien d’autre qu’un multiple de $m$ [5] !

Donc, l’infinité des $0$ dans la suite de Fibonacci réduite modulo $m$ correspond à l’infinité des termes $F_n$ qui sont divisibles par $m$.

En particulier, on sait maintenant que pour tout premier $p$, il existe une infinité de termes $F_n$ qui sont divisibles par $p$. Et aussi que, parmi eux, une infinité seront divisibles par $p^2$. On sait même qu’on les retrouve périodiquement, avec une régularité d’horloge. Mais ces deux ensembles, les $F_n$ divisibles par $p$ et ceux divisibles par $p^2$, pourraient-ils coïncider, pour certains premiers $p$ exotiques ? On suspecte fortement que non. C’est d’ailleurs précisément ce que prédit la Conjecture 1.

Longueur de la période ?

On a vu que, pour un module $m$ donné, la suite de Fibonacci réduite modulo $m$ est périodique. Très bien. Mais quelle longueur de période trouve-t-on ? C’est là que l’affaire se corse. On ne connaît pas la réponse en général.

Pour un entier naturel $m$ donné, notons donc $L(m)$ la longueur de la période de la suite de Fibonacci réduite modulo $m$. Par exemple, on a vu plus haut que $L(2)=3$ et $L(3)=8$. Bien que de nombreuses propriétés de la fonction $L(m)$ soient connues, celle-ci reste encore très mystérieuse.

Voici un exemple de résultat connu, en l’occurrence dû à Donald D. Wall en 1960 [6].

Théorème. Soit $p$ un nombre premier.

• Si la classe de $p$ modulo $5$ vaut $1$ ou $4$, alors $L(p)$ divise $p-1$.
• Si la classe de $p$ modulo $5$ vaut $2$ ou $3$, alors $L(p)$ divise $2(p+1)$.

Hélas, s’il arrive souvent que $L(p)$ égale $p-1$ ou $2(p+1)$, il arrive aussi qu’il soit bien plus petit que ces valeurs maximales respectives. Quel diviseur précis de $p-1$ ou de $2(p+1)$ le nombre $L(p)$ est-il ? La réponse à cette question est inconnue en général !

La Conjecture 1 revisitée

Soit $p$ un nombre premier. On vient de le voir, la valeur précise de $L(p)$ reste mystérieuse en général. Mais maintenant, si après avoir réduit la suite de Fibonacci modulo $p$, on la réduit aussi modulo $p^2$, comment se comparent les longueurs obtenues $L(p)$ et $L(p^2)$ ? Là, la situation est nettement meilleure — jusqu’à un certain point.

Pour commencer, voyons ce que l’on trouve pour $p = 2$ et pour $p=3$.

• Modulo $2$ : $\color{red}{0, 1}, 1, \color{red}{0, 1}, 1, \dots $

• Modulo $4$ : $\color{red}{0, 1}, 1, 2, 3, 1, \color{red}{0, 1}, 1, \dots$

On trouve donc :
\[ \begin{eqnarray*} L(2) & = & 3, & & \\ L(4) & = & 6 & = & 2 \times L(2). \end{eqnarray*} \]

• Modulo $3$ : $\color{red}{0, 1}, 1, 2, 0, 2, 2, 1, \color{red}{0, 1}, 1, \dots$

• Modulo $9$ : $\color{red}{0, 1}, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, \color{red}{0, 1}, 1, \dots$

Et ici, on trouve :
\[ \begin{eqnarray*} L(3) & = & 8, & & \\ L(9) & = & 24 & = & 3 \times L(3). \end{eqnarray*} \]

Ah ! Serait-on par hasard face à un comportement régulier ? Peut-on espérer une formule générale de la forme $L(p^2) \, = \, p \times L(p)$ ?

Presque ! Voici encore un résultat de Donald D. Wall, dans son même article de 1960 cité auparavant.

Théorème. Soit $p$ un nombre premier. Alors de deux choses l’une : ou bien $L(p^2)=L(p)$, ou bien $L(p^2)=p \times L(p)$. De plus, s’il existe un nombre de Fibonacci $F_n$ qui soit divisible par $p$ mais pas par $p^2$, alors c’est la deuxième alternative qui l’emporte :
\[ L(p^2) \, = \, p \times L(p). \]

En ce qui concerne la motivation principale de la Conjecture 1, tout s’éclaire ! En effet, de par le résultat ci-dessus, sa validité entraînerait que, même si les longueurs $L(p)$ et $L(p ^2)$ pour $p$ premier restent inconnues en général, leur rapport, lui, vaudrait toujours exactement $p$.

Devant l’océan des mystères arithmétiques d’une suite aussi célèbre, ce serait déjà un joli petit galet.

Travaux pratiques

Tester la Conjecture 1 à la main pour de petits nombres premiers peut être très amusant, et pourrait inspirer des ados et autres humains en quête de libération — au moins temporaire — de l’emprise de leurs smartphones.

Pour un nombre premier $p$ donné, trouver un $F_n$ divisible par $p$ mais pas par $p^2$ peut se faire en réduisant simultanément la suite de Fibonacci modulo $p$ et modulo $p^2$, et en espérant qu’au niveau du premier $0$ rencontré dans la réduction modulo $p$, le terme correspondant soit non-nul modulo $p^2$.

Illustrons cela avec le cas $p=11$.
\[ \begin{eqnarray*} \text{Modulo } 11 & & : & & 0 & & 1 & & 1 & & 2 & & 3 & & 5 & & 8 & & 2 & & 10 & & 1 & & \color{red}{0} & & \dots \\ \text{Modulo } 11^2 & & : & & 0 & & 1 & & 1 & & 2 & & 3 & & 5 & & 8 & & 13 & & 21 & & 34 & & \color{red}{55} & & \dots \end{eqnarray*} \]

La présence du $0$ en $10$ème position dans la première ligne indique que $F_{10}$ est divisible par $11$. Mais comme le terme correspondant est non nul dans la seconde ligne, on en déduit que $F_{10}$ n’est pas divisible par $11^2$ ! Voilà donc la Conjecture 1 validée dans le cas $p = 11$.

Facile, n’est-ce pas ? Alors, bon amusement !