I ran into a proof for Lamé's theorem that has confused me. The proof goes like this:
Prove: P(b): The number of recursive calls made by the Euclid-GCD algorithm when run with inputs $a ≥ b$ with $b<F_{k+1}$ is $<k$.
Basis step: the author chooses P(1) and P(2) for the base cases.
Inductive step: We will assume that $P(1) , ... , P(b − 1)$ holds for an arbitrary integer $b ≥ 3$ and then show that $P(b)$ holds.
Suppose $k$ is the smallest integer such that $b < F_{k+1}$. This means that $b ≥ F_k$. We break the analysis into the following two parts:
$a(mod b) < F_k$: In this case, after the first recursive call, the pair of numbers that is used for further recursive calls is $(b, a(mod b))$. Now since in this case, a $(mod b) < b$ and $a(mod b) < F_k$, using the induction hypothesis, we get that the number of further recursive calls is $< (k−1)$ and hence the total number of recursive calls is $< (k − 1) + 1 = k$.
$a(mod b) ≥ F_k$: In this case, the pair of numbers after the first recursive call is $(b,a (mod b))$. Let the pair after the second recursive call be $(a(mod b),d)$. Then, since $a(mod b) ≥ F_k$ and $b<F_{k+1}$, we have $d<b+1−a(modb)≤F_{k+1}−F_k = F_{k−1}$. Moreover,since $d<b$, we can apply the inductive hypothesis to conclude that the total number of recursive calls is $< (k − 2) + 2 = k$.
The above two cases shows that $P(b)$ holds. So, we conclude that $P(n)$ holds for all values of $n ≥ 1$
I have a couple of questions about this proof:
First, what is the use this statement in the proof: "This means that $b ≥ F_k$"?
Second, how does $d<b+1−a(modb)≤F_{k+1}−F_k = F_{k−1}$ follow from $a(mod b) ≥ F_k$ and $b<F_{k+1}$?
You may find this geometric description of the Euclidean algorithm helpful in getting some intuition behind the proof.
https://nrich.maths.org/1357
Note that the Euclidean algorithm, viewed in reverse, creates a rectangular spiral. The slowest-growing spiral is that in which the rectangles are Fibonacci numbers (because each new entry is the sum of the two prior entries, rather than a sum involving higher multiples of those prior entries.)
Thus when the algorithm is viewed going forward, if you start with a pair of consecutive Fibonacci numbers, the Euclidean algorithm takes the most number of steps $k$ to reduce it them the gcd.