Ciąg Fibonacciego

[naturaMF]

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

[Sciurius]

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