Archives de catégorie : Algèbre

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 🙂

Un reste, loin dans la suite de Fibonacci

Épisode 1 : ça parle de quoi cet article ?

Le plus simple est que je vous le raconte en vidéo 😉

Petite remarque: dans cette vidéo je donne un ordre de grandeur du nombre de chiffres de F_N. Mais en fait en notant r=\frac{\ln\phi}{\ln10}, en majorant \ln(1+x) par x (pour x>0), on obtient assez facilement

    \[nr-\frac{\ln5}{2\ln10}-2^{-n}<x<nr-\frac{\ln5}{2\ln10}+2^{-n}\]


Pour n=N=10^{18} on obtient au dixième près

    \[x\sim208987640249978733,8\]


ce qui montre que F_{N} possède exactement 208987640249978734 chiffres.

Épisode 2 : si on essayait …

…malgré tout de coder le calcul des termes dans un langage compilé ? (ou encore: si je trouvais un prétexte pour jouer avec le langage Ada ?)

Première partie :

Deuxième partie :

Troisième épisode : les maths à la rescousse !

Un peu d’algèbre linéaire et la fameuse « exponentiation rapide ». Un algorithme qui décoiffe 🙂

Quatrième épisode : encore des maths !

Mais là, on part dans le monde de l’arithmétique modulaire pour appliquer l’algorithme d’exponentiation rapide

Épilogue

On implémente tout ce qu’on a vu en Ada pour donner une réponse instantanée à notre problème

Erratum: il s’agit de monsieur Daniel Feneuille (et non David) dont je voulais parler. Au passage, ses cours sont disponibles ici : https://ada.developpez.com/cours/iut/

Je vous parlais aussi d’un papier que j’ai rédigé sur les suites récurrentes linéaires d’ordre 2 (pour un public averti) :

Matrices génériques et Théorème de Hamilton Cayley

Voilà un objet dont j’ai appris l’existence en parcourant l’excellent forum http://www.les-mathematiques.net/phorum/ . À la recherche d’une démonstration élégante du théorème de Hamilton-Cayley, je découvre un objet qui a véritablement modifié ma conception de l’algèbre.

Alors je ne vais pas faire durer le suspens plus longtemps et fabriquer la bébête. On se donne

    \[A=\mathbb{Z}\left[\left(x_{i,j}\rigtht)_{(i,j)\in n^2}\right]\]

n est un entier naturel non nul, l’anneau des polynômes à coefficients entiers à n^2 indéterminées. Ce que l’on appelle la « matrice générique G d’ordre n » est la matrice G\in M_n(A) de terme générique

    \[G_{i,j}=x_{i,j}\]

Voilà ! À ce stade, on se demande bien ce qu’on pourrait en faire ! Pour exciter la curiosité que peut susciter cet objet, considérons un instant le polynôme caractéristique \chi de cette matrice. C’est à dire

    \[\chi=\det (G- x I_n)\in A[x]\]

Comme A est intègre unitaire commutatif (vu que \mathbb{Z} l’est), A se plonge dans son corps des fractions \overline{A} et donc

    \[\chi\in \overline{A}[x]\]

Soit k un corps de décomposition de \chi. Alors le polynôme caractéristique de G\in M_n(k) est scindé sur k. Et c’est là que la magie opère: ses racines sont simples !

En effet, son discriminant \Delta (à savoir le résultant de \chi et de \chi') est un polynôme dans A. Si celui-ci était nul, alors en l’évaluant par exemple via x_{i,j} \to i \delta_{i,j}, c’est à dire en créant une instance de G égale à la matrice diagonale D\left((i)_{i\in n}\right), on obtiendrait le résultant de \prod_{i\in n} x-i qui serait nul. Ce qui est absurde car toutes les racines de ce dernier sont simples et qu’il est à coefficients dans un anneau factoriel.

La conclusion de tout ceci est que si maintenant f est un endomorphisme d’un espace vectoriel E de dimension finie sur un corps quelconque K, alors \chi_f annule f. En effet, si on note M la matrice de f (dans une base quelconque fixée de E) alors le morphisme d’anneaux envoyant G sur M envoie \chi sur \chi_f et comme \chi(G) est nulle il en est de même de \chi_f(M) donc de \chi_f(f).

Certes, cette preuve ne semble pas plus courte que celles qu’on trouve un peu partout. Mais elle est de loin plus riche d’enseignements et ne recourt à aucun calcul astucieux basé sur des manipulations de lignes / colonnes de matrices. Elle est surtout très féconde, comme on le verra dans d’autres articles où il sera question de résoudre des problèmes classiques d’algèbre linéaire.