Euklid's algortime

Der er et spørgsmål om det samme her:
https://www.studieportalen.dk/Forums/Thread.aspx?id=387146

Det forstår jeg simpelthen ikke, kan godt bruge et uddybende svar, hvis nogen kan hjælpe.

a1 = ca 10^100. a(2n) < 10^100*½^n. Den må senest stoppe når et a bliver 1, så der stoppes senest for et N givet ved 1 = 10^100*½^(2N), hvilket så vidt jeg husker er et sted mellem 600 og 700.

Supplement:

Givet a >= b > 0 forløber Euklids' algoritme til bestemmelse af sfd(a,b) som

a = q_1*b + r_1

b = q_2*r_1 + r_2

r_1 = q_3*r_2 + r_3

:

r_(n-1) = q_(n+1)*r_n

Antallet af divisor bliver størst muligt såfremt q_i = 1 i alle skridt og sfd(a,b) = 1. Startende bagfra i algoritmen med disse betingelser ses r_i'erne - inklusive a og b - at være successive Fibonaccital.

Det værst tænkelige input til Euklids algoritme med hensyn til antal divisioner er derfor to på hinanden følgende Fibonaccital f_(n+1) og f_(n+2) og algoritmen kræver da n skridt.

Med udgangspunkt i dette kan det vises at det maksimale antal divisioner Euklids algoritme kræver til beregning af sfd(a,b) er 5 gange antallet af cifre i det mindste af tallene a og b.