Difference between revisions of "Divisibility of Fibonacci numbers"
m |
m |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 22: | Line 22: | ||
<math> F_{m+n} = F_{m-1} F_n + F_{m} F_{n+1}. </math> | <math> F_{m+n} = F_{m-1} F_n + F_{m} F_{n+1}. </math> | ||
| − | Recalling that two consecutive Fibonacci numbers are always relatively prime, we can establish the property of the Euclidean Algorithm, | + | Assuming <math> m=nk </math>, induction and the use of the previous formula imply that <math> F_{nk} </math> is divisible by <math> F_n </math>. |
| + | |||
| + | Interestingly, the same formula allows us to prove the following statement. | ||
| + | |||
| + | ''' <math> F_n </math> does not divide <math> F_k </math>, <math> k>n </math>, unless <math> n </math> divides <math> k </math>.''' | ||
| + | |||
| + | Recalling that two consecutive Fibonacci numbers are always relatively prime, we can establish the property of the Euclidean Algorithm. Indeed, if <math> m>n </math> are two integers such that <math> m=qn+r </math>, <math> 0<r<n-1 </math> , then | ||
| + | |||
| + | <math>F_m = F_{qn+r} = F_{qn-1} F_{r}+ F_{qn} F_{r+1},</math> | ||
| + | |||
| + | and therefore | ||
| + | |||
| + | <math> {\rm gcd} (F_m,F_n)= {\rm gcd}(F_n,F_r). </math> | ||
| + | |||
| + | Therefore, the Euclidean Algorithm on the pair <math> (F_m,F_n)</math> has the same run as the Euclidean Algorithm on their indices <math> (m,n)</math> and | ||
| + | |||
| + | <math> {\rm gcd}(F_m,F_n)=F_{{\rm gcd}(m,n)}.</math> | ||
Latest revision as of 21:45, 20 December 2021
Recall that Fibonacci numbers are the members of the sequence 1, 1, 2, 3, 5, 8, ..., so that every next number is the sum of two previous numbers. It is a part of the mathematical folklore that every 5th Fibonacci number is divisible by 5. It also happens that 5 is the 5th Fibonacci number. In fact, a more general statement is true:
Every n-th Fibonacci number (i.e. number [math]\displaystyle{ F_{nk} }[/math] for some k) is divisible by [math]\displaystyle{ F_n }[/math], the n-th Fibonacci number.
Among the different ways to prove that is to use the matrix
[math]\displaystyle{ A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} }[/math]
It is easy to verify by induction on [math]\displaystyle{ n }[/math] that
[math]\displaystyle{ A^n = \begin{bmatrix} F_{n-1} & F_n \\ F_n & F_{n+1} \end{bmatrix} }[/math]
Using the fact that [math]\displaystyle{ A^{m+n} = A^m \times A^n }[/math] and comparing the (1,2)-entries of the two matrices, we obtain a helpful representation of [math]\displaystyle{ F_{m+n} }[/math]:
[math]\displaystyle{ F_{m+n} = F_{m-1} F_n + F_{m} F_{n+1}. }[/math]
Assuming [math]\displaystyle{ m=nk }[/math], induction and the use of the previous formula imply that [math]\displaystyle{ F_{nk} }[/math] is divisible by [math]\displaystyle{ F_n }[/math].
Interestingly, the same formula allows us to prove the following statement.
[math]\displaystyle{ F_n }[/math] does not divide [math]\displaystyle{ F_k }[/math], [math]\displaystyle{ k\gt n }[/math], unless [math]\displaystyle{ n }[/math] divides [math]\displaystyle{ k }[/math].
Recalling that two consecutive Fibonacci numbers are always relatively prime, we can establish the property of the Euclidean Algorithm. Indeed, if [math]\displaystyle{ m\gt n }[/math] are two integers such that [math]\displaystyle{ m=qn+r }[/math], [math]\displaystyle{ 0\lt r\lt n-1 }[/math] , then
[math]\displaystyle{ F_m = F_{qn+r} = F_{qn-1} F_{r}+ F_{qn} F_{r+1}, }[/math]
and therefore
[math]\displaystyle{ {\rm gcd} (F_m,F_n)= {\rm gcd}(F_n,F_r). }[/math]
Therefore, the Euclidean Algorithm on the pair [math]\displaystyle{ (F_m,F_n) }[/math] has the same run as the Euclidean Algorithm on their indices [math]\displaystyle{ (m,n) }[/math] and
[math]\displaystyle{ {\rm gcd}(F_m,F_n)=F_{{\rm gcd}(m,n)}. }[/math]