# Prime power divisors of the fibonacci numbers

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.

-
@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: oeis.org/A000045 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 math.ucsd.edu/~erickson/research/pdf/fibonacci3.pdf – Gerry Myerson Jun 7 '11 at 6:05

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.