Pgcd et suite de Fibonacci

Discussions générales concernant les mathématiques.
[forum modéré par les modérateurs globaux du site]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
MB
Administrateur
Administrateur
Messages : 7295
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Pgcd et suite de Fibonacci

Message par MB »

En tombant sur cette anecdote mathématiques, indiquant que le pgcd de deux nombres de Fibonacci est un nombre de Fibonacci, je me suis souvenu d'une démonstration que j'avais trouvé assez jolie (et qui pourrait peut-être servir aux agrégatifs, comme application du théorème de Bézout). Il me semble que cette preuve est inspirée d'exercices du Cours d'algèbre de Demazure. On peut en trouver une autre dans ce document.
On considère la suite de Fibonacci $(F_n)$ définie récursivement par les égalités suivantes. \[ F_0 = 0 \quad\text{;}\quad F_1 = 1 \quad\text{;}\quad F_{n+1}=F_n+F_{n-1} \] Si $n$ et $m$ sont deux entiers strictement positifs, alors on a $\pgcd(F_n,F_m) = F_{\pgcd(n,m)}$.
Preuve. On considère deux entiers $n$ et $m$ strictement positifs et on pose $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, $d = \pgcd(n,m)$ et $D = \pgcd(F_n,F_m)$. L'objectif est donc de montrer que $D = F_d$.
  • Une récurrence simple sur $n \geqslant 1$ permet d'obtenir la relation suivante.
    \[ A^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} \]
  • En passant aux déterminants, on obtient l'égalité suivante.
    \[ F_{n+1}F_{n-1}-F_n^2 = (-1)^n \]
  • D'après le théorème de Bézout, l'égalité précédente permet d'affirmer que $F_{n+1}$ et $F_{n-1}$ sont premiers avec $F_n$.
Dans la suite, on notera $[x]_k$ la classe de $x$ dans l'anneau $\Z_k=\Z/k\Z$ et $[M]_k=([a_{i,j}]_k)$ avec $M=(a_{i,j})$.
  • On posant $n=kd$, on a $A^n=(A^d)^k$. La matrice $[A^d]_{F_d}$ étant diagonale, il en est de même pour $[A^n]_{F_d}$, ce qui implique que $F_d$ divise $F_n$. De la même façon, on montre que $F_d$ divise $F_m$, et donc que $F_d$ divise $D$.
  • D'après le théorème de Bézout, il existe $u,v \in \Z$ tels que $d=nu+mv$. On a donc $A^d = (A^n)^u(A^m)^v$. Puisque $D$ divise $F_n$ et $F_m$, les matrices $[A^n]_D$ et $[A^m]_D$ sont diagonales. De plus, les termes diagonaux $F_{n+1}$ et $F_{n-1}$ de $A^n$ sont premiers avec $F_n$ et donc avec $D$, ce qui implique que $[A^n]_D$ est inversible. Il en est de même pour $[A^m]_D$. Ainsi, les matrices $[(A^n)^u]_D$, $[(A^m)^v]_D$ et donc $[A^d]_D$ sont diagonales, ce qui implique que $D$ divise $F_d$.
  • On a donc bien $D = F_d$.
MB. (rejoignez pCloud afin d'obtenir 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
projetmbc
Utilisateur chevronné
Utilisateur chevronné
Messages : 1932
Inscription : samedi 29 décembre 2007, 00:58

Re: Pgcd et suite de Fibonacci

Message par projetmbc »

Super preuve modulaire ! Pour un oral, il faudrait une présentation plus "constructive".