If
\[F_n, \; F_m\]
are terms in the Fibonacci sequence, then \[F_n\]
divides \[F_m\]
if and only if \[n\]
divides \[m\]
, .Proof
Consider the terms
\[F_n, \; F_{nk}\]
. If \[k=1\]
the result is trivially true. The proof is by induction.\[P(1)\]
by the above argument. Let \[P(r)\]
be true for \[r=2, \; 3,..., \; k\]
, and prove \[P(k+1)\]
.Use the identity
\[F{m+n}=F_{m-1}F_n+F_mF_{n+1}\]
.\[F_{n(k+1)}=F_{nk+n}=F_{nk}F_n+F_{nk}F_{n+1}\]
(1)By the induction hypothesis,
\[F_n\]
divides \[F_{nk}\]
so \[F_n\]
divides each term on the right hand side of (1).Conversely, suppose
\[F_n\]
divides \[F_m\]
. Suppose \[m=nq+r, \; 1 \le r \lt n\]
.\[F_m=F_{nq+r}=F_{nq-1}F_r+F_{nq}F_{r+1}\]
\[F_m, F_{nq}\]
are both divisible by \[F_n\]
, so \[F_{nq-1}F_r\]
must also be. but \[r \lt n \rightarrow F_r \lt F_n\]
, so \[F_n\]
divides \[F_{nq-1}\]
.Let
\[d\]
be the greatest common factor of \[F_n, \; F_{nq-1}\]
then \[d\]
also divides \[F_{nq}\]
since \[F_n\]
divides \[F_{nq}\]
.But the greatest common factor of consecutive terms in the Fibonacci sequence is 1, so
\[d=1\]
.