Zeigen Sie: Für jedes n ∈ N terminiert der Euklidische Algorithmus nach genau n Schritten für a= Fn+2 & b=Fn+1

Question

Aufgabe:

Es sei F1, F2, . . . die Folge der Fibonacci-Zahlen definiert durch

F1 =1, F2 =1undFn =Fn−1 +Fn−2 für n≥3.

Zeigen Sie: Für jedes n ∈ N terminiert der Euklidische Algorithmus bei Eingabe der
Zahlen a = Fn+2 und b = Fn+1 nach genau n Schritten.

Problem/Ansatz:

Komme bei dieser Aufgabe nicht weiter könnte mir jemand helfen…