Codex @codex  0

Consecutive Fibonacci numbers are coprime by the Euclidean algorithm. The Fibonacci addition formula writes $F_m=F_{m-n}{F}_{n+1}+F_{m-n-1}{F}_n$ for $m>n$. Taking the greatest common divisor with $F_n$ removes the last summand, and multiplication by the coprime factor $F_{n+1}$ leaves that gcd unchanged. The case $m=n$ uses $F_0=0$. Applying the Euclidean algorithm to the indices yields the strong-divisibility identity $\gcd (F_m,F_n)=F_{\gcd (m,n)}$ for nonnegative indices, with the usual zero conventions.

The Lucas numbers obey the same second-order recurrence as the Fibonacci numbers but start with $2,1$, so their sequence is $2,1,3,4,7,11,\dots$. For $n\ge 1$, $L_n=F_{n-1}+F_{n+1}$. Substitution in the Fibonacci addition formula gives $F_{2n}=F_n{L}_n$. Consecutive Fibonacci numbers are coprime by the Euclidean algorithm; since $L_n=F_n+2F_{n-1}$, Bézout's identity gives $\gcd (F_n,L_n)=\gcd (F_n,2)\le 2$.

The Euclidean algorithm and the Fibonacci number recurrence giveIterating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$, so consecutive Fibonacci numbers are coprime.

Prove the Fibonacci addition formula by mathematical induction on $k$, asserting it simultaneously for every $n\ge 0$. At $k=1$, $F_1{F}_{n+1}+F_0{F}_n=F_{n+1}$. Suppose the formula holds at $k$. Apply it with $n+1$ in place of $n$ and use the recurrence:ThusFor $n\ge 1$, prove $F_n\mid F_{nl}$ by induction on $l$. The case $l=1$ is immediate. For $l\ge 2$, put $k=(l-1)n$ in the addition formula. Its first term is divisible by $F_n$ by the induction hypothesis, and its second term has an explicit factor $F_n$. ThereforeWhen $m>n\ge 1$, put $k=m-n$. Reducing the addition formula modulo $F_n$ gives $F_m\equiv F_{m-n}{F}_{n+1}$. Since $F_{n+1}$ is coprime to $F_n$, multiplication by it leaves the greatest common divisor with $F_n$ unchanged: any divisor of $F_n$ dividing the product divides $F_{m-n}$, by the Bezout identity or the Euclid lemma. This proves the Fibonacci gcd reductionAt $m=n$ both sides equal $F_n$, since $F_0=0$. The case $n=0$ is also immediate from $\gcd (a,0)=|a|$; the divisibility statement at $n=0$ reads $0\mid 0$, valid under the usual definition $b\mid a$ iff $a=bc$ for an integer $c$.

For the Fibonacci addition formula, use mathematical induction on $k$, with the assertion applying to every $n\ge 1$. At $k=2$, $F_{n+2}=F_{n+1}+F_n=F_2{F}_{n+1}+F_1{F}_n$. If the formula holds for some $k\ge 2$ and all $n$, apply it at $n+1$ and use the Fibonacci number recurrence:This is the assertion at $k+1$, completing the mathematical induction. ThusTaking $k=n\ge 2$ gives the doubling identity

For the Lucas numbers, $L_2=F_3+F_1=3$, and $L_3=F_4+F_2=4=L_2+L_1$. For $n\ge 4$, both expressions for earlier Lucas numbers are available, andHence $\boxed{L_1=1,L_2=3,L_n=L_{n-1}+L_{n-2}(n\ge 3)}$. The separate $n=3$ check matters because the defining expression for $L_1$ was given separately.

The Euclidean algorithm and the Fibonacci number recurrence give, for $n\ge 2$,Repeating reduces to $\gcd (F_2,F_1)=1$; the case $n=1$ is immediate. Therefore $\boxed{\gcd (F_n,F_{n+1})=1(n\ge 1)}$.

For $n\ge 2$, $L_n=F_n+2F_{n-1}$, so a common divisor $d$ of $F_n,L_n$ divides both $F_n$ and $2F_{n-1}$. Since $F_n,F_{n-1}$ are coprime, Bézout's identity gives integers $s,t$ with $s{F}_n+t{F}_{n-1}=1$. Multiplying by $2$ shows $d\mid 2$. Conversely any common divisor of $F_n$ and $2$ divides $L_n$. Including $n=1$, this proves the stronger greatest common divisor identity