Exercice 33

Pour $n\in\mathbb{N}$, notons $\mathcal{P}_{n}$ : « $\mathrm{PGCD}(F_{n},F_{n+1})=1$ ».

Initialisation : $\mathrm{PGCD}(F_{0},F_{1})=\mathrm{PGCD}(0,1)=1$, d'après la Proposition 1.

Hérédité : Supposons $\mathcal{P}_{n}$ vraie. Un diviseur commun de $F_{n+1}$ et $F_{n+2}$ divise $F_{n+2}-F_{n+1}=F_{n}$ ; réciproquement, un diviseur commun de $F_{n}$ et $F_{n+1}$ divise $F_{n}+F_{n+1}=F_{n+2}$. Les deux couples ont donc les mêmes diviseurs communs, d'où : $$\mathrm{PGCD}(F_{n+1},F_{n+2})=\mathrm{PGCD}(F_{n},F_{n+1})=1$$

Conclusion : Pour tout $n\in\mathbb{N}$ : $\boxed{\mathrm{PGCD}(F_{n},F_{n+1})=1}$

Deux termes consécutifs de la suite de Fibonacci sont toujours premiers entre eux. L'algorithme d'Euclide appliqué à $F_{n+1}$ et $F_{n}$ ne fait que redescendre la suite, avec des quotients tous égaux à $1$ : c'est le cas où il est le plus lent.