Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 not sure where to start with this..

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?

share|cite|improve this question
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$$

share|cite|improve this answer
thanks ! that makes more sense.. didn't think to look at it like that – lsf456 Jan 10 '13 at 0:23

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$.

share|cite|improve this answer
Nice one. I would however swap $|$ for $:$ – Git Gud Jan 10 '13 at 0:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.