Le conte de Fibonacci démystifié

Si vous avez suivi le conte https://www.libremaths.fr/2020/05/04/un-reste-loin-dans-la-suite-de-fibonacci/, que vous vous êtes dit « heureusement qu’on a des ordinateurs » et que vous aimez croire qu’ils nous sont indispensables, ne lisez surtout pas la suite !

Hé oui, vous vous en doutiez peut-être, la force de la pensée humaine suffisait. Inutile d’aller chercher l’arsenal technologique pour répondre à cette fameuse question : quel est le reste par 25 du terme d’indice 10^{18} de la suite de Fibonacci ? Question dont, je le rappelle, la réponse est parfaitement inutile, et donc parfaitement indispensable à tout esthète qui se respecte 🙂

Une façon élégante (à mon goût), de voir le problème est de choisir de travailler dans un anneau bien adapté au problème. Allons-y et commençons par considérer A=\mathbb{Z}/25\mathbb{Z}, \chi=X^2-X-1\in A[X] et B=\frac{A}{(\chi)}. On note enfin \pi l’épimorphisme canonique de A sur son quotient B. Les éléments de A seront notés \overline{x} pour x\in \mathbb{Z}.

Alors B est un A module libre de base (\pi(1),\pi(X)). Par récurrence, on en déduit immédiatement que:

    \[\pi\left(X^n\right)=\overline{F_n}\pi(X)+\overline{F_{n-1}}\]

De plus,, en utilisant l’égalité \pi\left(X^{2}\right)=\pi\left(X+1\right) et le fait que \pi est un morphisme d’anneaux, on obtient :

    \[\pi\left(X^{25}\right)=\left(\overline{5}\pi\left(X\right)+\overline{3}\right)^{5}=\sum_{k=0}^{5}\overline{\binom{5}{k}}\overline{5}^{k}\pi\left(X\right)^{k}\overline{3}^{5-k}\]

Or, pour k\in\left\{ 1;\dots;5\right\}, on a \overline{5}^{k}\overline{\binom{5}{k}}=\overline{0} et donc

    \[\pi\left(X^{25}\right)=\overline{3}^{5}=\overline{3}^{3}\times\overline{3}^{2}=\overline{2}\times\overline{9}=\overline{18}\]

donc

    \[\pi\left(X^{25m}\right)=\overline{18}^{m}\]

conjointement au fait que \pi\left(X^{n}\right)=\overline{F_{n}}\pi\left(X\right)+\overline{F_{n-1}} (pour n\geqslant1) et que B est un module libre de base \left(\pi\left(1\right);\pi\left(X\right)\right) on en déduit que F_{25m} est nul modulo 25 pour tout naturel m. Comme 10^{18} est un multiple de 25, on a bien montré que F_{10^{18}} est divisible par 25.

On peut même aller plus loin (attention, on se rapproche de l’infini et l’au delà) : comme \pi\left(X^{25m}\right)=\overline{18}^{m}, et que \overline{18^4}=\overline{-7}^4=\overline{-1}^2=\overline{1}, on en déduit que

    \[\pi\left(X^{100k}\right)=\overline{1}= \overline{F_{100k}}\pi\left(X\right)+\overline{F_{100k-1}}\]

et donc, en résumé : \overline{F_{100k-1}}=\overline{1} et \overline{F_{100k}}=\overline{0} ce qui permet de retrouver la suite de Fibonacci périodiquement, modulo 25, tous les 100 termes !

Et voilà la démystification 🙂

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *