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