I'm having trouble with a problem I encountered while studying Number Theory. This problem comes from the book Number Theory by George E. Andrews.

It defines a generalized Fibonacci sequence $F_1$, $F_2$, $...$ by selecting four integers $a,b,c,e$ and defining $F_1 = a$, $F_2 = b$, and for all $n > 2$, $F_n = cF_{n-1} + eF_{n-2}$.

Define $d = \gcd(a,b)$ and $f = \gcd(F_m, F_{m-1})$.

It asks to prove that if $\gcd(f,e) = 1$, then $f | d$.

I appreciate your help.


Since $F_n=cF_{n-1}+eF_{n-2}$, if the greatest common divisor of $F_n$ and $F_{n-1}$ does not divide $e$, it must divide $F_{n-2}$. So $f$ divides both $F_{n-1}$ and $F_{n-2}$ but not $e$, hence it must divide $F_{n-3}$. By going backwards, $f$ must divide both $F_1$ and $F_2$, hence it must divide their greatest common divisor. This proves $f|d$.

  • $\begingroup$ You might want to use some kind of induction to make it formal. $\endgroup$ – BeaumontTaz Jul 27 '14 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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