Divisibility of Fibonacci numbers - Revision history

Alexandk at 01:45, 21 December 2021

2021-12-21T01:45:54Z

2021-12-21T01:43:35Z

2021-12-21T01:41:54Z

2021-12-21T01:37:57Z

2021-12-21T01:37:20Z

2021-12-21T01:36:50Z

2021-12-21T01:23:41Z

2021-12-21T01:21:01Z

2021-12-21T01:05:48Z

2021-12-21T01:03:44Z

← Older revision		Revision as of 01:45, 21 December 2021
Line 35:		Line 35:

	<math> {\rm gcd} (F_m,F_n)= {\rm gcd}(F_n,F_r). </math>		<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>

← Older revision		Revision as of 01:43, 21 December 2021
Line 24:		Line 24:
	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>.		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		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

← Older revision		Revision as of 01:41, 21 December 2021
Line 21:		Line 21:

	<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>
		+
		+	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>.
		+
		+

	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		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

@@ Line 24: / Line 24: @@
 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_{qn+r} = F_{qn-1} F_{r}+ F_{qn} F_{r+1},</math>
+<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>

← Older revision		Revision as of 01:37, 21 December 2021
Line 28:		Line 28:
	and therefore		and therefore

−	<math> gcd(F_m,F_n)=gcd(F_n,F_r). </math>	+	<math> {\rm gcd} (F_m,F_n)= {\rm gcd}(F_n,F_r). </math>

← Older revision		Revision as of 01:36, 21 December 2021
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, ~~namely~~ if <math> m>n </math> are two integers such that <math> m=qn+r </math>, <math> 0<r<n-1 </math> , then	+	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_{qn+r} = F_{qn-1} F_{r}+ F_{qn} F_{r+1},</math>
		+
		+	and therefore
		+
		+	<math> gcd(F_m,F_n)=gcd(F_n,F_r). </math>

← Older revision		Revision as of 01:23, 21 December 2021
Line 21:		Line 21:

	<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, namely if <math> m>n </math> are two integers such that <math> m=qn+r </math>, <math> 0<r<n-1 </math> , then

← Older revision		Revision as of 01:21, 21 December 2021
Line 19:		Line 19:

	Using the fact that <math> 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> F_{m+n} </math>:		Using the fact that <math> 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> F_{m+n} </math>:
		+
		+	<math> F_{m+n} = F_{m-1} F_n + F_{m} F_{n+1}. </math>

← Older revision		Revision as of 01:05, 21 December 2021
Line 17:		Line 17:
	F_n & F_{n+1}		F_n & F_{n+1}
	\end{bmatrix} </math>		\end{bmatrix} </math>
		+
		+	Using the fact that <math> 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> F_{m+n} </math>:

@@ Line 9: / Line 9: @@
 & 1 \\
 & 1
 \end{bmatrix} </math>