# Fibonacci Divisibility Burton's Corollary: $u_m \mid u_n$ if and only if $m \mid n$

Reading an old edition of Burton's number theory text, I come to this corollary in chapter 13:

In the Fibonacci sequence, $u_m \mid u_n$ if and only if $m \mid n$ for $m \ge 2$

The proof seems to be:

$u_m \mid u_n \implies \gcd(u_m,u_n)=u_m=u_d$ with $d=\gcd(m,n)$ by Theorem 13-3. Thus $m=d=gcd(m,n)$ and $m\mid n$

Conversely, $m|n \implies u_m | u_n$ by Theorem 13-2

This seems valid to me. However, If true, it seems

$1 | 2 \implies u_2 | u_3 \implies 2|3$ which is absurd.

I'm not sure where the mistake is. Should it perhaps be $m > 2$ in the corollary but then why?

• $$u_0=0, u_1=u_2=1, u_3=u_1+u_2=?$$ – lab bhattacharjee Mar 12 '16 at 3:03
• $u_3 = 2$, I am confused by this comment – topoquestion Mar 12 '16 at 12:33
• – lab bhattacharjee Mar 12 '16 at 12:40

It should be $m,n>2$ in the corollary.
If you are wonderng why so, consider that the solution used $$gcd(u_m,u_n)=u_{\gcd(m,n)}=u_{m} \Rightarrow m=\gcd(m,n)$$ However, note that $u_{gcd(m,n)}=u_{m} \Leftrightarrow \gcd(m,n)=m$ is not true when $\gcd(m,n)=1$, since $u_1=u_2$ but $1 \neq 2$. To avoid this and assume that all elements in the Fibonacci sequence are distinct, it is necessary that $m,n>2$
For example, in your example, note that $\gcd(u_2, u_3)=u_1 =u_2$. So $u_2$ divides $u_3$.