6
$\begingroup$
  1. Is it true that if a Fibonacci number $F_{n}$ divides the product of two Fibonacci numbers, then it must divide at least one of them?

  2. Is it true that for all $n \ne 1,2,6,12$, there exists a prime divisor $p$ of $F_{n}$ such that the entry point (first appearance as a divisor in the Fibonacci sequence) of $p$ is at position $n$?

I can see that the second statement implies the first (at least for $n \ne 1,2,6,12$).

Also, Carmichael's theorem says that for all $n \ne 1,2,6,12$, there exists a prime divisor $p$ of $F_{n}$ such that $p \nmid F_k$ for (positive integer) $k \lt n$, and the second statement is equivalent to a sort of counterpart going in the other direction: for all $n \ne 1,2,6,12$, there exists a prime divisor $p$ of $F_{n}$ such that $p \nmid F_k$ for $k \gt n$ save only for the obvious exceptions where $k$ is a multiple of $n$ (since $F_{n}\mid F_{k}$ when $n \mid k$).

These seem like natural questions to ask but I haven't seen them addressed.

$\endgroup$
3
  • 4
    $\begingroup$ I must be missing something. Why doesn't Carmichael's theorem already answer your question 2? What do you mean by the entry point of $p$? Furthermore, note that if $p$ is a prime divisor of $F_n$ such that $p$ does not divide $F_k$ for $k<n$, then $p | F_m$ implies $p | F_{\mathrm{gcd}(m,n)}$, thus $\mathrm{gcd}(m,n)=n$, which means that $n$ divides $m$. $\endgroup$ Nov 29, 2012 at 8:24
  • $\begingroup$ If you want further info on this sort of behavior, search on "strong divisibility sequence". These are sequences $(A_n)$ with the property that $\gcd(A_m,A_n)=A_{\gcd(m,n)}$. As Greg Martin pointed out, the Fibonacci sequence is a strong divisibility sequence, as are many other divisibility sequences arising from algebraic groups. $\endgroup$ Nov 29, 2012 at 19:09
  • $\begingroup$ No, François, you didn't miss anything. It was me that was missing something. $\endgroup$ Nov 29, 2012 at 21:35

1 Answer 1

15
$\begingroup$

As François Brunault said in his comment, your #2 is true: Carmichael's theorem, which establishes the existence of a primitive prime divisor of $F_n$ for every $n\ne1,2,6,12$, together with $\gcd(F_m,F_n) = F_{\gcd(m,n)}$, shows that no Fibonacci numbers are divisible by a primitive prime divisor of $F_n$ except $F_{kn}$.

This gives an answer to #1 as well: suppose that $F_n \mid F_a F_b$, and let $p$ be a primitive prime divisor of $F_n$. Then $p \mid F_a$ or $p\mid F_b$, and so one of $a$ or $b$ must be a multiple of $n$, so that $F_n\mid F_a$ or $F_n\mid F_b$. This proof doesn't work for $n=1,2,6,12$, but $n=1,2$ are trivial, and the cases $n=6,12$ follow by considering the (periodic) Fibonacci sequence modulo $8$ and $144$, respectively. (In the latter case it may be easier to examine the periodic sequence $\gcd(F_n,144) = F_{\gcd(n,12)}$.)

Note that this proof gives the generalization that if $F_n$ divides the product of any finite number of Fibonacci numbers, then it must divide one of them - except for $n=6$ and $n=12$ for which this is false!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.