Proof of the gcd formula for Fibonacci numbers by the Euclidean algorithm

Proof

We show that $\gcd(F_a, F_b)$ obeys the subtraction step of the Euclidean algorithm, and argue by strong induction.

1. Let $F_k$ be the Fibonacci numbers. They are natural numbers. Two pairs of integers with the same common divisors have the same greatest common divisor.
2. For integers $x, y, t$, the pairs $(x, y)$ and $(x, y + t x)$ have the same common divisors. Indeed, $d \mid x$ and $d \mid y$ imply $d \mid y + tx$, and conversely $d \mid x$ and $d \mid y + tx$ imply $d \mid y$.
3. Let $x, y, c$ be integers with $\gcd(x, y) = 1$. We claim that $(x, yc)$ and $(x, c)$ have the same common divisors.
4. A common divisor of $x$ and $c$ divides $yc$. Conversely, let $d \mid x$ and $d \mid yc$. A common divisor of $d$ and $y$ divides $x$ and $y$, so it is $\pm 1$. Also $d$ and $y$ are not both $0$, since otherwise $x = 0 = y$ and $\gcd(x, y) = 0$. Thus $d$ and $y$ are coprime.
5. By the generalized Euclid's lemma, $d \mid c$. This proves the claim of step 3.
6. Let $a \ge 1$ and $c \ge 0$. The addition formula with $m = a - 1$ and $n = c$ gives $F_{a+c} = F_{a-1} F_c + F_a F_{c+1}$.
7. By step 2 with $t = -F_{c+1}$, $\gcd(F_a, F_{a+c}) = \gcd(F_a, F_{a-1} F_c)$.
8. By consecutive Fibonacci numbers are coprime, $\gcd(F_a, F_{a-1}) = 1$. By step 3, $\gcd(F_a, F_{a-1} F_c) = \gcd(F_a, F_c)$.
9. So $\gcd(F_a, F_b) = \gcd(F_a, F_{b-a})$ whenever $1 \le a \le b$, and also $\gcd(a, b) = \gcd(a, b - a)$ by step 2.
10. For a natural number $x$, $\gcd(x, 0) = x$. For $x > 0$ the largest divisor of $x$ is $x$, and $\gcd(0, 0) = 0$ by convention.
11. Let $Q(s)$ be the claim that $\gcd(F_a, F_b) = F_{\gcd(a, b)}$ for all natural numbers $a, b$ with $a + b = s$. We prove $Q(s)$ for all $s$ by strong induction.
12. Fix $s$ and assume $Q(s')$ for all $s' < s$. Let $a + b = s$.
13. If $a = 0$, then by step 10, $\gcd(F_0, F_b) = \gcd(0, F_b) = F_b = F_{\gcd(0, b)}$. The case $b = 0$ is the same with the roles exchanged.
14. If $1 \le a \le b$, then $a + (b - a) = b < s$. By step 9 and $Q(b)$, $\gcd(F_a, F_b) = \gcd(F_a, F_{b-a}) = F_{\gcd(a, b-a)} = F_{\gcd(a, b)}$.
15. If $1 \le b < a$, the same argument with $a$ and $b$ exchanged applies, since $\gcd$ is symmetric in its two arguments.
16. So $Q(s)$ holds. By strong induction, $\gcd(F_m, F_n) = F_{\gcd(m, n)}$ for all natural numbers $m$ and $n$.