Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
add comment

2 Answers 2

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|improve this answer
    
thanks ! that makes more sense.. didn't think to look at it like that –  lsf456 Jan 10 '13 at 0:23
add comment

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|improve this answer
    
Nice one. I would however swap $|$ for $:$ –  Git Gud Jan 10 '13 at 0:28
add comment

Your Answer

 
discard

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.