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.

Improve this question
$\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$
    – François Brunault
    Commented 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$
    – Joe Silverman
    Commented Nov 29, 2012 at 19:09
  • $\begingroup$ No, François, you didn't miss anything. It was me that was missing something. $\endgroup$
    – David Callan
    Commented Nov 29, 2012 at 21:35

1 Answer 1

Reset to default
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!

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .