a) I would use the algorithm to state:
Thus, iterating the algorithm times, we will find .
b) The first subtraction gives:
now using the result from part a) we then find:
Let be the Fibonacci numbers, defined by
a) Prove that for all we have
b) Prove that for all we also have
(Check what Euclid's algorithm would do if you started to compute or .)
Any help would be greatly appreciated!