Ciąg Fibonacciego

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
naturaMF
Rozkręcam się
Rozkręcam się
Posty: 32
Rejestracja: 02 sty 2017, 15:21
Podziękowania: 29 razy

Ciąg Fibonacciego

Post autor: naturaMF » 23 maja 2017, 09:00

Wykaż że dwa kolejne wyrazy ciągu Fibonacciego są względnie pierwsze.

Sciurius
Rozkręcam się
Rozkręcam się
Posty: 49
Rejestracja: 05 maja 2020, 16:38
Podziękowania: 4 razy
Otrzymane podziękowania: 9 razy
Płeć:

Re: Ciąg Fibonacciego

Post autor: Sciurius » 05 maja 2020, 18:16

1. Zauważmy że dla dowolnych względnie pierwszych \(a_1 , a_2\) liczby \(a_1 + a_2\) i \(a_2\) są względnie pierwsze

Dowód:
Załóżmy że \(a_2\) i \(a_1 + a_2\) nie są względnie pierwsze.
Jeśli \(a_2\) i \(a_1 + a_2\) nie są względnie pierwsze to istnieje takie \(k \in Z_+ , k \neq 1\) że \(k|a_2 \) oraz \(k|a_1 + a_2 \)
Zatem możemy zapisać że:
\(a_2 = lk\)
\(a_1 + a_2 = mk\)
gdzie \(m \in Z_+ , m \neq 1\), \(l \in Z_+ , l \neq 1\)
Zatem:
\(a_1 + a_2 = mk\)
\(a_1 + l * k = mk\)
\(a_1 = mk-lk = k(m-l) \to k|a_1\)
Więc \(NWD(a_1 , a_2 ) \neq 1\) a zatem \(a_1\) i \(a_2 \) nie są względnie pierwsze

2. Określmy ciąg Fibonnaciego jako:
\(a_1 = 1\)
\(a_2 = 1\)
\( a_{n+2}=a_{n+1}+a_{n}\)
Oczywiście \(NWD(a_1 , a_2 ) = 1\) więc \(a_1\), \(a_2\) są względnie pierwsze a co za tym idzie poprzez indukcje wszystkie pozostałe wyrazy ciągu Fibonnacciego
Pozdrawiam

Sciurius