Problem: The Fibonacci numbers $F_n$ are defined recursively via $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2} $ for $n \geq 2$. Show that $\gcd \left( F_n, F_{n+1} \right) = 1$ for all $n \in \mathbb{N} $.
Solution: For $n = 1$, $F_1 = 1$ and $F_2 = 1$ and $\gcd (F_2, F_1) = 1$. For $n > 1$, we have the following recursion to
\begin{equation}\label{eq:02Dec2023-1}
\gcd \left( F_n, F_{n+1} \right) = \gcd \left( F_n, F_n + F_{n-1} \right) = \gcd \left( F_n, F_{n-1} \right) ,
\end{equation}
where we used that $\gcd (a, a+b) = \gcd (a,b)$. This fact is not difficult to prove. For that let $d = \gcd (a, b)$. Then $d \mid a$ and $d \mid b$ implies $d \mid (a +b)$. Now if any positive integer $s \mid a$ and $s \mid (a + b)$, then $s \mid (a + b - a)$, that is, $s \mid b$. Since $d = \gcd (a,b)$, $s \leq d$. Thus, $d = \gcd (a, a + b)$.
The recursion \eqref{eq:02Dec2023-1} implies that
\[
\gcd \left( F_n, F_{n+1} \right) = \gcd \left( F_2, F_1 \right) = 1.
\]