Applying the Euclidean Algorithm to the Fibonacci Sequence. The Fibonacci sequence is the sequence $0$

$,1$

$,2$

$,...$ defined by

$0=1$

$1=2$

$=1+2$ for $>=2$

$($a$)$ Show that for all $$ in $,$ we have $>$ whenever $>>=0.$

$($b$)$ Show that if the Euclidean algorithm is run on input $=$

$,=1$ for some $$ in $,$ it

will require exactly $$ steps to terminate.