# Fibonacci Numbers $F_n$ and $F_{n + 1}$ are relatively prime for all $n \geq 0$.

I have looked a bunch of solutions of this problem on the web. But I want to know that whether my solution is correct or not. My solution is as follows

## Proof(By Induction)

$P(n)$:The Fibonacci numbers $F_n$ and $F_{n + 1}$ are relatively prime.

Base Case: $P(0)$ is true because $F_0 = 0$ and $F_1 = 1$ are relatively prime.

Inductive Step: Assume $P(n)$ to be true. Now to show that for $n \geq 0$, $P(n) \implies P(n + 1)$

$\implies \gcd(F_n, F_{n + 1}) = 1$

$\implies s(F_n) + t(F_{n + 1}) = 1$

$\implies s(F_{n + 2} - F_{n + 1}) + t(F_{n + 1}) = 1$

$\implies (t - s)(F_{n + 1}) + s(F_{n + 2}) = 1$

$\implies \gcd(F_{n + 1}, F_{n + 2}) = 1$

$\implies P(n + 1)$ is true

Thus, by induction $P(n)$ is true for all $n \geq 0$.

• The basic idea is fine. You should say that there exist integers $s$ and $t$ such that $\dots$. – André Nicolas Jan 10 '15 at 3:14
• You don't even need the $s$-$t$ argument for this, incidentally, if you have the basic fact (key to the Euclidean algorithm) that $\gcd(a,b)=\gcd(a,a+b)$. You can just say $\gcd(F_n, F_{n-1})=\gcd(F_n, F_n+F_{n-1})=\gcd(F_n, F_{n+1})$. – Steven Stadnicki Jan 10 '15 at 3:46
• Here is an easier argument. Assume $F_{n}$ and $F_{n+1}$ are relatively prime. (This is clear when $n=0$, so we can take $n\geq 1$.) Let $d\geq 1$ be a common factor of $F_{n+1}$ and $F_{n+2}$. Then $d$ is a factor of $F_{n+2}-F_{n+1}=F_{n}$, so $d$ is a common factor of $F_{n}$ and $F_{n+1}$, which by the inductive hypothesis implies $d=1$. Thus $F_{n+1}$ and $F_{n+2}$ are relatively prime. (A more general result to prove: $\gcd(F_m,F_n) = F_{\gcd(m,n)}$.) – KCd Jan 10 '15 at 3:47
• As others said, you must say “There exist integers $s$ and $t$ for which ...” You can’t conclude that $s(F_n) + t(F_{n + 1}) = 1$ otherwise, because $s$ and $t$ are meaningless symbols. You should also not simply connect everything with $\implies$ symbols. For example, you say $\implies\gcd(F_n,F_{n+1})=1$. What exactly implies what? You also need to conclude $P(n+1)$ or (better) conclude that $P(n)\implies P(n+1)$ in the inductive step. You have convinced the reader, but you should say it more clearly. You have a valid mathematical argument, but you need to present it a little bit better. – Steve Kass Jan 10 '15 at 4:24

Assume as induction hypothesis that $\gcd(F_n,F_{n+1})=1$. Then there are integers $s$ and $t$ such that
\begin{align*} 1&=sF_n+tF_{n+1}\\ &=s(F_{n+2}-F_{n+1})+tF_{n+1}\\ &=sF_{n+2}+(t-s)F_{n+1}\;, \end{align*}
and it follows that $\gcd(F_{n+1},F_{n+2})=1$ as well. The result now follows by induction.