Prove that $\forall p \in \Bbb P,n \in \Bbb Z^+;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$ and $F_{5^n} \equiv 0 \mod 5^n$, where $\left(\dfrac{5}p\right)$ is the Legendre symbol and $F_m$ is the $m$th Fibonacci number, with $F_1=F_2=1$. This is a generalization of the identity $F_{p-\left(\frac{5}p\right)} \equiv 0 \mod p$. Is the generalization well-known? I was trying to find an upper bound on the index of the first Fibonacci number dividing any integer $m$, which would then be the product of the indices associated with the largest power of each prime dividing $m$.

  • 2
    $\begingroup$ I would guess that in the case $p\neq5$ a formula like this can be proven by studying the Galois ring $\mathbb{Z}_{p^n}[\sqrt5]$ (so either the ring or its quadratic extension). The structure of the unit groups of those rings is known. Thinking... (this will take a while, also we have a department-wide junket today, so I won't be posting a solution any time soon). +1 to a fun question. $\endgroup$ Aug 19, 2013 at 6:54

1 Answer 1


It is known that if $p$ is an odd prime factor of $F_n$, then $\frac{F_{p n}}{F_n}$ is divisible by $p$ but not by $p^2$. For $p=2$, the situation has to be handled more carefully, but is also well known (cf. e.g. N.N. Vorobiev, Fibonacci Numbers, p. 76).

  • $\begingroup$ Thank you. I'm having difficulty finding an english version of this online. Is it worth buying? $\endgroup$ Aug 19, 2013 at 8:02
  • $\begingroup$ The result should online be available as Thm. 1 in J.H. Halton, On Divisibility Properties of Fibonacci Numbers, Fib. Quat. 4.3 (1966), 217-240. The book is nice to have, but not necessary. $\endgroup$ Aug 19, 2013 at 8:30

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.