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 🙂

LibreMaths

Le conte de Fibonacci démystifié

Laisser un commentaire Annuler la réponse

Mathématiques et infomatique (la plus libre possible)