Archives de catégorie : Algèbre

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 🙂

Ada, Algèbre, Contes numériques

Un reste, loin dans la suite de Fibonacci

mai 4, 2020 Libremaths Laisser un commentaire

É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) :

Algèbre

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

mars 28, 2020 Libremaths Laisser un commentaire

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]$

où $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.

LibreMaths