Aufgabe:
Es sei \( F_{1}, F_{2}, \ldots \) die Folge der Fibonacci-Zahlen definiert durch \( F_{1}=1, \quad F_{2}=1 \) und \( F_{n}=F_{n-1}+F_{n-2} \) für \( n \geq 3 \).
Zeigen Sie: Für jedes \( n \in \mathbb{N} \) terminiert der Euklidische Algorithmus bei Eingabe der Zahlen \( a=F_{n+2} \) und \( b=F_{n+1} \) nach genau \( n \) Schritten.
