Zależność z liczbami Fibonacciego

[studciak123]

Udowodnij indukcyjnie, że \(\displaystyle{ NWD(F_{m},F_{n})=F_{NWD(m,n)}\).

Ja to robię tak.
I Baza dla \(\displaystyle{ m=1}\):
\(\displaystyle{ NWD(F_{1},F_{n})=F_{NWD(1,n) = 1}\).
II Krok indukcyjny.
Zakłądam tezę dla \(\displaystyle{ m^{*} < m}\), pokazuję dla m. Rozbiłem to na dwa przypadki:
\(\displaystyle{ i)}\) \(\displaystyle{ F_{m} > F_{n}}\)
\(\displaystyle{ NWD(F_{m},F_{n})= NWD(F_{n},F_{m} - F_{n})}\) -- z założenia indukcyjnego zachodzi, ponieważ \(\displaystyle{ F_{m} - F_{n}}\) jest mniejsze od \(\displaystyle{ F_{m}}\)
\(\displaystyle{ ii)}\) \(\displaystyle{ F_{m} < F_{n}}\)
No i tutaj mam mały problem bo nwm jak to zrobić.

[arek1357]

Masz tu rozwiązanie tego problemu, jest to bardzo popularna własność ciągu Fibonacciego znajdująca się w prawie każdym szkolnym podręczniku od pierwszej podstawówki do studiów doktoranckich...