ciag Fibonacciego, nwd

[Pumba]

Wykazac ze dla ciagu Fibonacciego \(\displaystyle{ F_{n}}\) zachodzi rownosc
\(\displaystyle{ NWD( F_{n},F_{m})=F_{NWD(n,m)}}\)

[juzef]

Wystarczy zauważyć, że każde dwie kolejne liczby liczby Fibonacciego są względnie pierwsze (bo w przeciwnym razie wszystkie miałyby wspólny dzielnik, a \(\displaystyle{ F_1=1}\)) oraz skorzystać z tożsamości \(\displaystyle{ F_{m+n}=F_{n+1}F_{m} + F_n F_{m-1}}\).