# number theory fibonacci

Using facts of the Fibonacci sequence, I need to show that if $m,n$ are natural numbers that satisfy $m \mid F_n$ and $m \mid F_{n+1}$, then $m=1$.

I am thinking since $m$ divides $F_n$ and $m$ divides $F_{n+1}$ I could somehow use $F_n = mx$ and $F_{n+1} = my\,$ for some integers $x,y$.

Could anyone help me start with this idea or is this not the right idea at all?

-
Hint: If $m$ divides two numbers, does it divide their sum? Their difference? – KReiser Jan 10 '13 at 0:13
Are you familiar with proof by induction (in this case, on two consecutive Fibonnaci numbers), and how it might apply here? – amWhy Jan 10 '13 at 0:23
yeah I am going to use induction now thanks! – lsf456 Jan 10 '13 at 0:24

Note that $$F_{n+1} = F_n + F_{n-1}$$ Hence, we have that $\gcd(F_{n+1},F_n) = \gcd(F_n,F_{n-1})$. Hence (by induction), we get that $$\gcd(F_{n+1},F_n) = \gcd(F_1,F_0) = 1$$
Assume $m|F_n$ and $m | F_{n + 1}$. Then, $\{k\,:\, m|F_k, \, m|F_{k + 1} \}$ is nonempty. Also note that $m|F_k$ and $m | F_{k + 1}$ implies $m | F_{k - 1}$ if $k > 0$. Since $\mathbb{N}$ is well-ordered, $\{k\,:\, m|F_k, \, m|F_{k + 1} \}$ has a least element and this element must be $0$ by the previous observation. Therefore, $m | F_0 =1$ and this implies $m = 1$.
Nice one. I would however swap $|$ for $:$ – Git Gud Jan 10 '13 at 0:28