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

Step 1: addition formula. For $b\ge1$: $F_{a+b}=F_{a+1}F_b+F_aF_{b-1}$. Proven by induction on $b$ (both sides satisfy the Fibonacci recurrence in $b$).

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

Step 3: the key reduction. By Step 1, $F_{a+b}=F_{a+1}F_b+F_aF_{b-1}$, so
$$\gcd(F_{a+b},F_b)=\gcd(F_aF_{b-1},F_b)=\gcd(F_a,F_b),$$
where the last equality holds because $F_{b-1}$ and $F_b$ are coprime (Step 2).

Step 4: Euclid on the indices. By Step 3, $\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)$ for $m>n$. This is the subtraction form of the Euclidean algorithm, applied to the indices, which ends at $\gcd(F_g,F_0)=F_g$ with $g=\gcd(m,n)$. Hence $\gcd(F_m,F_n)=F_{\gcd(m,n)}$. $\blacksquare$

Consequence. Let $n>4$ be composite, $n=ab$ with $2\le a\le b$. Since $n\ne4$, $b\ge3$, and $b<n$. By the formula, $\gcd(F_b,F_n)=F_{\gcd(b,n)}=F_b$, i.e. $F_b\mid F_n$. Here $F_b\ge F_3=2$ and $F_b<F_n$, so $F_n$ has a proper divisor $F_b>1$ and is composite. Hence if $F_n$ is prime and $n>4$, then $n$ is prime.

Remark. The converse fails: $F_{19}=4181=37\cdot113$.

Lesson. A divisibility property that is "Euclid-like" (gcd of values equals value at the gcd) is proved by showing $\gcd(f(a+b),f(b))=\gcd(f(a),f(b))$.