Fibonacci Divisors

We claim that for any odd prime $p \ne 5$ , $p \nmid u_{p}$ . Recall Binet's formula $u_p = (\alpha^p - \beta^p)/ \sqrt{5}$ , where $\alpha = (1+\sqrt{5})/2$ and $\beta = (1-\sqrt{5})/2$ . Since $p$ is odd, we are free to multiply by powers of two, so it suffices to consider

$\displaystyle 2^{p-1} u_p = \frac{(1 + \sqrt{5})^p - (1 - \sqrt{5})^p}{2\sqrt{5}}$ .

Writing out each power by binomial expansion, we see that every other term cancels with the other expansion, so the RHS simplifies to the integer expression

$\displaystyle \sum_{k=0}^{(p-1)/2} 5^k {p \choose 2k+1}$ .

By elementary properties of $p\choose r$ , every binomial coefficient is divisible by $p$ except for the last term, ${p \choose p} = 1$ , so modulo $p$ we get

$2^{p-1} u_p \equiv 5^{(p-1)/2} \not\equiv 0 \pmod p$ .

In fact, by Euler's criterion (and little Fermat) we actually have something more precise: $u_p \equiv (5/p) \pmod p$ , where $(5/p) = \pm 1$ is the Legendre symbol.

This analysis also showed that $5 \mid u_5$ (which is trivial to verify in any case), and the only prime remaining is 2, which doesn't divide $u_2$ . Therefore the only prime to be summed is $5$ .

Solution 1: We know that $p=2$ doesn't work. Let $p$ be an odd prime. Solving the recurrence relation, we have that $u_n=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$ . If $u_p$ is a multiple of $p$ , then so is $2^p u_p$ , which is $\frac{(1+\sqrt{5})^p-(1-\sqrt{5})^p}{\sqrt{5}}$ . Consider the Binomial expansion. The even powers of $\sqrt{5}$ will cancel with their conjugate, while the odd powers of $\sqrt{5}$ will double (and cancel with the denominator leaving an integer). Note that $p \choose k$ is a multiple of $p$ for all $k \neq 0, p$ , since the numerator has a prime $p$ . Looking at $u_p 2^p$ modulo $p$ , we obtain $2 \times \sqrt{5} ^{p-1} \equiv 0 \pmod{p}$ . Since $p$ is an odd prime, this holds true only for $p=5$ . A quick check shows that $u_5 = 5$ , so $p=5$ is the only valid solution.

Hence, the sum of all primes $p$ that divide $u_p$ is 5.

Solution 2: First, we note that $5$ divides $u_5$ and $2$ does not divide $u_2$ . Suppose $p$ is an odd prime, different from $5$ .

Consider the Fibonacci sequence modulo $p$ . For convenience, we will use the equality symbol to mean congruence modulo $p$ . Consider a set $S$ that consists of residues modulo $p$ and a symbol $\infty.$ A ratio of two consecutive Fibonacci numbers, $\frac{u_n}{u_{n-1}}$ modulo $p$ naturally belongs to the set $S$ . Indeed, it is easy to see by induction that two consecutive numbers cannot be both $0$ modulo $p$ . We say that $\frac{u_n}{u_{n-1}}=\infty$ if $u_{n-1} =0$ . The recursive formula for the Fibonacci numbers implies that if $\frac{u_n}{u_{n-1}}=x,$ then $\frac{u_{n+1}}{u_n}=f(x),$ where $f(x)=\begin{cases} \frac{x+1}{x}, \ &\mbox{if}\ x\neq 0, \infty\\ \infty, \ &\mbox{if}\ x=0\\ 1, \ &\mbox{if}\ x=\infty \end{cases}$ Note that $f$ is one-to-one. Consider the sequence of elements of $S$ that corresponds to ratios $\frac{u_n}{u_{n-1}}$ of Fibonacci numbers: $\infty, f(\infty),f(f(\infty)),...$ Because $S$ is finite, we cannot go on forever without repetition. Suppose the $(k+1)$ st element of the sequence is the first element that appeared before. Because $f$ is one-to-one, it must equal $\infty$ , otherwise we will have two different elements mapped to the same one by $f$ . This implies that the $k$ -th element is $0$ , and this is the first time a zero appeared in the sequence. It follows that $\frac{a_n}{a_{n-1}}=0$ if and only if $k$ divides $n$ . Since $a_p=0$ , this implies that $k=p$ . This means that our sequence covers exactly $p$ elements of $S$ , so one is missing. Consider the equation $f(x)=x$ . Clearly, it is equivalent to $\frac{x+1}{x}=x,$ which is equivalent to $x^2-x-1=0.$ Because $p\neq 5$ , this equation either has two roots or no roots, depending on whether $5$ is quadratic residue modulo $p$ or not. Because $f$ is one-to-one, the element of $S$ not in our sequence must be sent by $f$ to itself. So the above equation has at least one, therefore two solutions. The second solution must be an element of our sequence of ratios, which is impossible because $p>1$ . Thus, the answer is $5$ .

Solution 3: First, we note that $5$ divides $u_5$ and $2$ does not divide $u_2$ . Suppose $p$ is an odd prime, different from $5$ . The well-known formula for Fibonacci numbers states the following:

$u_n=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$

This formula works for Fibonacci numbers modulo $p$ , that is in $F_p={\mathbb Z}/p{\mathbb Z}$ , with $s=\sqrt{5}$ being either an element of $F_p$ or its quadratic extension. Note that there are two square roots of $5$ , but changing from one to the other changes signs of both numerator and denominator.

For $u_p$ to be zero in $F_p,$ we must have $(1+\sqrt{5})^p-(1-\sqrt{5})^p=0,$ which can be rewritten as $\left( \frac{1+\sqrt{5}}{1-\sqrt{5}} \right)^p=1$ The order of the multiplicative group of $F_p$ and of its quadratic extension are $p-1$ and $p^2-1$ respectively. By the corollary of the Lagrange theorem, the order of $\frac{1+\sqrt{5}}{1-\sqrt{5}}$ divides that. But from the above formula this order must divide $p$ , so it equals $1$ . This implies that $\frac{1+\sqrt{5}}{1-\sqrt{5}} =1,$ so $1+\sqrt{5} =1-\sqrt{5},$ which is impossible. Thus, the answer is $5$ .

By the fact that p|u p−1 or u p+1, if p is a prime >5, and GCD(u p−1,u p)=1, for all p∈N, so if p>5 is a prime, then p∤u p, since if p∣u p, then GCD(u p−1,u p) or GCD(u p+1,u p)≥p>1, a contradiction. Therefore,we just need to check p=2,3,5, and it is easy to check that only 5∣u_5, satisfies the condition and thus the answer is 5.

First we will require a short lemma that states that $p \mid \dbinom{p}{k}$ for any $1\le k \le p-1$. If we write $\dbinom{p}{k}$ as $\frac{p!}{k!(p-k)!}$, it is not hard to see that there are no integers less than $p$ that divide $p$, given it is prime. Proceeding, it is natural to consider Binet's Formula so that we can algebraically deal with the Fibonacci numbers. Binet's Formula states that $$F n=\frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$. Factoring out the $\frac{1}{2^n}$ from each binomial expansion and simplifying, we find that $F p$ for some prime $p$ is equivalent to $$\frac{1}{2^{p-1}} \left(\sum_{n=1}^{\frac{p+1}{2}} 5^n \dbinom{p}{2n-1}$$. We are guaranteed that this value is always an integer from the nature of the Fibonacci sequence and the derivation of Binet's formula, so we need only consider the numerator of this expression. Using the previously stated lemma, we have that $p$ divides every term in the numerator, with the exception being $5^{\frac{p+1}{2}}\dbinom{p}{p}=5^{\frac{p+1}{2}}$. It follows that $p$ must divide a power of 5, and thus the only prime number with the desired property is $p=5$.

By the fact that $p | u_{p - 1}$ or $u_{p + 1}$ , if p is a prime $> 5$ , and $GCD (u_{p - 1}, u_{p}) = 1$ , for all $p \in \mathbb{N}$ , so if $p > 5$ is a prime, then $p \nmid u_{p}$ , since if $p \mid u_{p}$ , then $GCD (u_{p - 1}, u_{p})$ or $GCD (u_{p +1}, u_{p}) \ge p > 1$ , a contradiction.

Therefore,we just need to check $p = 2, 3, 5$ , and it is easy to check that only $5 \mid u_{5}$ , satisfies the condition and thus the answer is $\boxed {5}$ .

Note : See this for details on the fact.

I started by listing out Fibonacci Numbers, and I noticed that every 3rd Fibonacci Number was a multiple of the 3rd Fibonacci Number, 2. By expanding my list, I found out that every 4th Fibonacci Number is divisible by 3 (The 4th Fibonacci Number), and this pattern continued, so I made a generalization that every n-th Fibonacci Number was divisible by the nth Fibonacci Number.

With this in mind, I started inserting primes in place of the nth Fibonacci Number. I only worked with the numbers 2, 3, 5, 13, 89 because they satisfied the conditions of being prime, being a Fibonacci Number, and being relatively small so that I could detect a pattern.

Results: 2 - Every 3rd Fibonacci number is divisible by 2. (Fails) 3 - Every 4th Fibonacci number is divisible by 3. (Fails) 5 - Every 5th Fibonacci number is divisible by 5. (Works) 13 - Every 7th Fibonacci number is divisible by 13. (Fails) 89 - Every 11th Fibonacci number is divisible by 89. (Fails)

I noticed that after 5, there could be no prime where F(p) is divisible by p because the primes were growing much more rapidly than the index of the Fibonacci number; also, because we are checking for primes, we can ignore the fact that every n-th number is divisible by the prime because only the first number has the possibility of equaling the prime.

Finally, I took into account the primes that were not part of the Fibonacci List. I found that, with the exception of the prime 2, F(p) is also a prime number (a bit of a generalization, not sure if it is entirely true), I tested this on the primes 3, 5, 7, 11, 13.

Results: F(3) = 2 F(5) = 5 F(7) = 13 F(11) = 89 F(13) = 233

Similarly to before, after the prime 5, the output greatly outgrows the index, so I safely assumed that 5 would be the only solution that would work because the output would have to be equal for the output to be divisible by the input since they are both prime.

Thus, the only prime that works is 5.

Let us observe the actual sequence.

$u_{1}=1$

$u_{2}=1$

$u_{3}=2$

$u_{4}=3$

$u_{5}=5$

$u_{6}=8$

$u_{7}=13$

$u_{8}=21$

$u_{9}=34$

$u_{10}=55$

$u_{11}=89$

$u_{12}=144$

$u_{13}=233$

$u_{14}=377$

$u_{15}=610$

$\ldots$

And we see instantly that $u{5} \equiv 0 \pmod{5}$ . This means that $p=5$ is a proper divisor of $u_{5}$ .

As we continue testing the other numbers, we see none that also match this property. Interestingly enough, $u_{5}$ is the only Fibonacci number that has this property. So, $5$ is our answer.

I used a brute force method to solve for the first 15 numbers ( few steps showed that it wasn't possible prior to that ).

Binet's Formula says that the $n$ -th Fibonacci number is given by $\mu_p = \frac{\left(\phi\right)^n-\left(1-\phi\right)^n}{\sqrt{5}}$ where $\phi = \frac{1+\sqrt{5}}{2}$ .

I am gonna denote the $n^{th}$ Fibonacci number by $F_n$ , instead of $u_n$ . It's well known, from Binet's Formula that, $F_n=\dfrac{\alpha^n-\beta^n}{\sqrt{5}}$ where $\alpha=\dfrac{1+\sqrt{5}}{2},\beta=\dfrac{1-\sqrt5}{2}$ In case, the proof isn't known, we can easily prove this using induction, along with the facts that $\alpha^2=1+\alpha,\beta^2=1+\beta$ . However, we skip this part.

Next, we expand $\alpha^n$ and $\beta^n$ using Binomial theorem.

$(1+\sqrt5)^n=\sum\limits_{i=0}^p\binom pi(\sqrt5)^i$

$(1-\sqrt5)^n=\sum\limits_{i=0}^p\binom pi(-\sqrt5)^i$ Summing them, $\alpha^n-\beta^n=\dfrac{1}{2^{p-1}}\sum\limits_{i\leq p,i\mbox{ odd}}\binom pi(\sqrt{5})^i$ Since we can check manually that, $p=2$ doesn't work, we assume $p$ to be odd. We prove another lemma. Lemma: If $p$ is a prime and $i,0<i<p$ is a positive integer, then $p|\binom pi$ Proof: Note the identity: $\binom nk=\dfrac nk\binom{n-1}{k-1}$ So, $i\binom pi=p\binom{p-1}{i-1}$ Since, $\gcd(p,i)=1,$ we can say $p|\binom pi$ . $\blacksquare$ Therefore, we have, $F_p\equiv\dfrac1{2^{p-1}}5^{\frac p2}\equiv0\pmod p$ which implies $p=5$ .

It is known that Fibonacci numbers have the strange property that if F(n) gives the nth Fibonacci number, then if n is prime F(n) is prime. So, since we are trying to find all F(n) that are divisible by n when n is prime, there will be very few, since F(n) is prime. However, if we consider the first few terms:

F(1)=1 F(2)=1 F(3)=2 F(4)=3 F(5)=5

We realize that F(5) is divisible by 5, since it is 5. Since the next F(n)>n, this is the only possible case, so the answer is 5.

For those curious to why the first rule works, here's a proof:

Taking First, acknowledge gcd(F(m),F(n)) = F(gcd(m,n)). If F(n) is prime, and n>m, then gcd(F(m),F(n))=1. So, the F(gcd(m,n))=1, and gcd(m,n)= 1 or 2. Further investigation of the casework shows that our statement is true.

in general ,p th fibonacci number = sum of two fibonacci nos. preceeding it. so,by using all prime nos. and checking whether it divides that fibonacci number or not ,we can easily find that it suits only for 2 and 3 and hence their sum is 5