Prove that any two consecutive terms of the Fibonacci sequence are relatively prime 
Prove that any two consecutive terms of the Fibonacci sequence are relatively prime.

My attempt:  
We have $f_1 = 1, f_2 = 1, f_3 = 2, \dots$, so obviously $\gcd(f_1, f_2) = 1$.
Suppose that $\gcd(f_n, f_{n+1}) = 1$; we will show that $\gcd(f_{n+1}, f_{n+2}) = 1$.
Consider $\gcd(f_{n+1}, f_{n+2}) = \gcd(f_{n+1}, f_{n+1} + f_n)$
because $f_{n+2} = f_{n+1} + f_n.$
Then $\gcd(f_{n+1}, f_{n+1} + f_n) = \gcd(f_{n+1}, f_{n}) = 1$ (gcd property).
Hence, $\gcd(f_n, f_{n+1}) = 1$ for all $n > 0$.
Am I on the right track?
Any feedback would be greatly appreciated.
Thanks,
 A: Your proof is good.  For reference, I have a proof without induction that uses Cassini's identity,
$$f_{n-1}f_{n+1} - f_nf_n = (-1)^n,$$
which is proved directly at that Wikipedia page and in another direct way at Show $F_{n+1} \cdot F_{n-1} = F_n^2 + (-1)^n$ for all $n \in \mathbb{N}$.
According to whether $n$ is even or odd, we have
$$f_{n-1}f_{n+1} - f_nf_n = 1 \qquad \text{or} \qquad f_nf_n - f_{n-1}f_{n+1} = 1.$$
Now, the gcd of $f_n$ and $f_{n+1}$ may be defined alternatively and equivalently as the least positive integer that can be written in the form $pf_n + qf_{n+1}$ where $p$ and $q$ are integers.  Because the coefficients of $f_n$ and $f_{n+1}$ in that pair of equations are Fibonacci numbers, hence integers, and because there is no positive integer less than $1$, gcd$(f_n, f_{n+1}) = 1$.  Thus, any two consecutive terms of the Fibonacci sequence are relatively prime.
A: Congratulations, you have solved it.
You have used the fact that $\gcd(a+b,b)=\gcd(a,b)$
A: Another approach. 
suppose $gcd(f_{n+1}, f_{n}) = d$. Then since $f_{n+1} = f_n + f_{n-1}$, $gcd(f_n, f_{n-1}) \ne 1$ and by infinite descent we will end up with n = 4 and n = 3 where gcd(2,3) = 1. Contradiction. 
A: Your proof is good.  For reference, I have a similar proof by induction:
The claim is true for the first few pairs of consecutive Fibonacci numbers, so assume it is true up to $f_{n+1}$ so that gcd$(f_{n}, f_{n+1}) = 1$.  Then by Bézout's identity, there exist integers $x$ and $y$ such that $xf_{n} +  yf_{n+1} = 1$.  So
\begin{align}
1 & = xf_{n} +  yf_{n+1}\\
  & = x(f_{n+2} - f_{n+1}) +  yf_{n+1}\\
  & = (y - x) f_{n+1} +  xf_{n+2}.
\end{align}
Now, the gcd of $f_{n+1}$ and $f_{n+2}$ may be defined alternatively and equivalently as the least positive integer that can be written in the form $uf_{n+1} + vf_{n+2}$ where $u$ and $v$ are integers.  Because $y - x$ and $x$ are integers and there is no positive integer than $1$, gcd$(f_{n+1}, f_{n+2}) = 1$.  Hence, the claim holds for $n + 2$ whenever it holds for $n + 1$, and so the induction principle guarantees that it holds for every pair of consecutive Fibonacci numbers.
Remark: I called this proof similar to yours because Bézout's identity is used to prove the gcd property that you used.
A: Using induction/modular arithmetic:
For n = 1, we see that
$F_n$ and $F_{n+1}$ are relatively prime.
For the inductive step, we assume $F_n$ and $F_{n+1}$ are relatively prime, and show this implies $F_{n+1}$ and $F_{n+2}$ are relatively prime.
By the inductive assumption, for any prime $p$ for which $p|F_{n+1}$, $p∤F_n$.
With modular arithmetic, this statement becomes $$F_{k+1} ≡ 0⠀mod(p)$$ and $$ F_k ≢ 0⠀mod(p)$$Using the definition of the Fibonacci sequence, we can change the first congruence to $$F_{k+2} - F_k ≡ 0⠀mod(p)$$ $$F_{k+2} ≡ F_k≢ 0⠀mod(p)$$ Modular congruence is transitive (this is pretty clear, i.e. since $3≡7≡15⠀mod(4),⠀ 3≡15⠀mod (4)$.) Thus $F_{k+2} ≢0⠀mod(p)$, meaning $p∤F_{k+2}$ and $F_{n+1}$ and $F_{n+2}$  are relatively prime.
