Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
  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.

share|improve this question
4  
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$. –  François Brunault Nov 29 '12 at 8:24
    
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. –  Joe Silverman Nov 29 '12 at 19:09
    
No, François, you didn't miss anything. It was me that was missing something. –  David Callan Nov 29 '12 at 21:35
add comment

1 Answer

up vote 10 down vote accepted

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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