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.
Prime power divisors of the fibonacci numbers
2
$\begingroup$
number-theory
prime-numbers
fibonacci-numbers
divisibility
-
2@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: http://oeis.org/A000045 then to compute ;) – 2011-06-07
-
1What 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? – 2011-06-07
-
3Seems to be a homework problem on page 49 at http://math.ucsd.edu/~erickson/research/pdf/fibonacci3.pdf – 2011-06-07
1 Answers
5
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.