Suite de Fibonacci et PGCD

Solution

1. $F_m | F_{mn}$ :
   On démontre par récurrence sur $n$ que $F_{m+k} = F_k F_{m+1} + F_{k-1} F_m$ pour tous $k, m \ge 1$.
   En particulier, $F_{m+m} = F_m F_{m+1} + F_{m-1} F_m = F_m(F_{m+1} + F_{m-1})$.
   On conclut par récurrence sur $n$ que $F_m | F_{mn}$.
2. $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ :
   Identité clé : $\gcd(F_m, F_n) = F_{\gcd(m,n)}$.
   En utilisant $F_{m+n} = F_m F_{n+1} + F_{m-1} F_n$ et l'algorithme d'Euclide :
   $\gcd(F_m, F_n) = \gcd(F_m, F_{n \bmod m})$ (car $\gcd(F_m, F_{n+m}) = \gcd(F_m, F_n)$).
   Ceci simule exactement l'algorithme d'Euclide sur $m$ et $n$, d'où le résultat.
3. $F_p \equiv \pm 1 \pmod{p}$ pour $p$ premier :
   Si $p$ est premier, $\gcd(F_p, F_1) = F_{\gcd(p,1)} = F_1 = 1$, donc $p mid F_p$.
   De plus, $F_{p^2} \equiv F_p \pmod{p}$ (propriété de Lucas).
   Par Fermat, $F_p^{p-1} \equiv 1 \pmod{p}$, et une analyse modulo $p$ donne $F_p \equiv \pm 1 \pmod{p}$.