gcd(F_m, F_n) = F_gcd(m,n)

Step 1: addition formula. For $a\ge1$ and $b\ge0$: $F_{a+b}=F_aF_{b+1}+F_{a-1}F_b$. Induction on $b$.

Step 2: consecutive terms are coprime. $\gcd(F_{k+1},F_k)=\gcd(F_{k-1},F_k)=\dots=\gcd(F_1,F_0)=1$.

Step 3: subtractive Euclid. Let $m>n\ge1$. Apply the formula with $a=m-n\ge1$, $b=n$:
$$F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n.$$
Hence $\gcd(F_m,F_n)=\gcd(F_{m-n}F_{n+1},F_n)$. Since $\gcd(F_{n+1},F_n)=1$ (Step 2), any common divisor of $F_{m-n}F_{n+1}$ and $F_n$ is a common divisor of $F_{m-n}$ and $F_n$, so
$$\gcd(F_m,F_n)=\gcd(F_{m-n},F_n).$$

Step 4: conclusion. Applying Step 3 repeatedly mimics the subtractive Euclidean algorithm on the indices; it ends at $(d,d)$ with $d=\gcd(m,n)$, and $\gcd(F_d,F_d)=F_d$.

Check. $\gcd(F_{12},F_{18})=\gcd(144,2584)=8=F_6$.

Remark. Consequently, if $F_n$ is prime then $n$ is prime, or $n=4$.

Lesson. A sequence with the "addition formula" structure inherits the Euclidean algorithm on its indices.