Zbiór zadań, (zadania różne)
Zadanie 249
Znajdź największy wspólny dzielnik wyrazów 100-ego i 110-ego ciągu Fibonacciego.
Rozwiązanie
Mamy dany ciąg Fibonacciego: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
$F_{0} = 0, F_{1} = 1, F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5$, itd.
Prawdziwe są twierdzenia:
1. Dla dowolnych $i, j$, zachodzi: $F_{i+j} = F_{i-1}F_{j} + F_{i}F_{j+1}$
2. Dla dowolnych $i$ i $j = ki$, dla $k$ naturalnego, liczba $F_{j}$ jest podzielna przez $F_{i}$.
3. Dwa sąsiednie wyrazy ciągu Fibonacciego są liczbami względnie pierwszymi.
Na podstawie (1) wynika, że NWD$(F_{i+j}, F_{j})$ jest dzielnikiem $F_{i-1}F_{j}$ oraz, ponieważ $F_{i}$ i $F_{i-1}$ są względnie pierwsze, jest dzielnikiem liczby $F_{j}$.
Stąd prawdziwe jest NWD$(F_{i}, F_{j})$ = NWD$(F_{i+j}, F_{j})$.
Jeśli $j=ki+r$, dla pewnego $r$, to NWD$(F_i,F_j) = $NWD$(F_{i-j}, F_j) =$ NWD$(F_{i-2j},F_j) = \ldots =$ NWD$(F_{i-kj},F_j) = $ NWD$(F_j,F_r)$.
Stosując algorytm Euklidesa stwierdzamy, że NWD$(F_{i}, F_{j}) = F_{NWD(i, j)}$.
Dla przykładu z zadania otrzymujemy NWD$(F_{100}, F_{110}) = F_{NWD(100, 110)} = F_{10} = 55$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>