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

I came across a result that if $p^n \mid f_m$ for some $n\geq1$ then $p^{n+1} \mid f_{pm}$. I was wondering if this is true.

share|cite|improve this question
@user6312: There is a pretty universal agreement on the indexing, specifically $F_0=0$. Wikipedia even says that $F_0=0$ is the modern convention, so it must be true. But seriously, we choose $F_0=0$ so that a large number of the divisibility properties work out nicely. Also, somewhat interesting is the fact that if you take the recurrence backwards, you get the formula $F_{-k}=(-1)^k F_k$. In any case, there are a lot of arguments. Here the conjecture survives up to $m=20$, but it is faster to use: then to compute ;) – Eric Naslund Jun 7 '11 at 2:19
What does "I came across a result" mean? Did you come across it in a book? did the book give a proof, or a reference? Or did you come across it just playing with numbers on your own, so you're not sure if it's true? – Gerry Myerson Jun 7 '11 at 5:54
Seems to be a homework problem on page 49 at – Gerry Myerson Jun 7 '11 at 6:05
up vote 5 down vote accepted

Here is one way, but it uses a pretty strong result. The Fibonacci numbers satisfy a multiplication formula, specifically: $$F_{kn}=\sum_{i=1}^{k}\binom{k}{i}F_{i}F_{n}^{i}F_{n-1}^{k-i}.$$ Combining this formula with the fact that the Fibonacci number satisfy the division property $F_k|F_{nk}$, you can see why your result follows.

share|cite|improve this answer

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.