(Fibo,nacci)

[Tino]

Ciao a tutti!

volevo rendervi partecipi di questo fatto interessante di cui da poco sono venuto a conoscenza (e che forse conoscerete già...).

Tutti conosciamo la famosa successione di Fibonacci $a_1=a_2=1,\ ...,\ a_n=a_{n-2}+a_{n-1},\ ...$. Ora indicando con $(m,n)$ il massimo comun divisore tra m e n si ha, per ogni $m,n \in \mathbb{N}^*$ che

$(a_m,a_n)=a_{(m,n)}$

In particolare, due numeri di Fibonacci successivi sono coprimi.

Che ne pensate?

Ciao

[leandro]

La dimostrazione richiede alcune altre proprieta' dei num.fib che
qui riprendo
-1) Due numeri di fib consecutivi sono coprimi
0)$a_{nq}=k*a_{n}$ cioe' se n divide nq anche
il num.fib di indice n divide il num.fib di indice nq
1)$a_{nq+r}=a_ra_{nq+1}+a_{r-1}a_{nq}$
Sia ora m=nq+r .
Se r=0 e' facile vedere che per la (0) la proprieta ' e' vera;sia quindi r>0.
Allora:
$(a_m,a_n)=(a_{nq+r},a_n)$ e per la (1):
$(a_m,a_n)=(a_ra_{nq+1}+a_{r-1}a_{nq},a_n)$
Ma per la (0) $a_n|a_{nq}$ e dunque:
$(a_m,a_n)=(a_ra_{nq+1},a_n)$

Sia ora d il MCD tra $a_{nq+1}, a_{n}$ ;poiche' $d|a_n$
per la (0) e' pure $d|a_{nq}$ e dovendo essere $d|a_{nq+1}$
per la (-1) non puo che essere d=1
Pertanto si puo' scrivere:
$(a_m,a_n)=(a_r,a_n)$
Applichiamo ora l'algoritmo di Euclide e agiamo su r ed n come su m ed n e cosi' via.
Avremo:
$(a_m,a_n)=(a_r,a_n)=(a_r,a_{r_1})=...=(a_{r_{s-1}},a_{r_s})$
dove $r_s$ e' l'ultimo resto non nullo e come tale rappresenta il MCD(m,n)
ed inoltre e' divisore di $r_{s-1}$.
Ne segue che (per la (1)):
$(a_m,a_n)=(a_{r_s},a_{r_{s-1}})=a_{r_s}=a_{(m,n)}$
Leandro
P.S.la proprieta' (-1) si puo' dimostrare indipendentemente da quella or ora
verificata.