Entonces, lo primero que debemos observar es el divisor común mayor de dos números de Fibonacci, que notaremos [matemática] f_n [/ matemática] y [matemática] f_m [/ matemática], [matemática] (n, m) \ in \ mathbb N ^ 2, n gt m [/ math]
Para hacer eso, lo primero que debes tener en cuenta es que
[matemáticas] \ existe (k, l, p) \ in \ mathbb N ^ {* 3}, kl = n, kp = m \ Leftrightarrow nm = kl-kp = k (lp) [/ math]
- ¿Por qué los polinomios hacen las formas que hacen?
- ¿Cuál es el significado de una razón en un modelo discreto?
- ¿Qué es la división limitada de overs en el cricket?
- ¿Por qué la raíz cúbica de 64 es igual a 4.000000000000001 en mi calculadora cuando 4 ^ 3 = 64 en la misma calculadora?
- ¿Cómo es la especialización en ACME en BYU?
Y
[matemática] \ existe (k, l, p) \ in \ mathbb N ^ {* 3}, kl = n, kp = m \ Leftrightarrow n + m = kl + kp = k (l + p) [/ math]
En otros términos, todos los divisores comunes de [matemática] m [/ matemática] y [matemática] n [/ matemática] también son divisores de [matemática] nm [/ matemática] y [matemática] n + m [/ matemática] y
[matemáticas] mcd (n, m) = mcd (m, n + m) = mcd (m, nm) = mcd (n, n + m) = mcd (n, nm) \ etiqueta 1 [/ matemática]
Ahora, tenga en cuenta que
[matemática] mcd (f_1, f_2) = mcd (1,1) = 1 [/ matemática]
Supongamos que [math] mcd (f_n, f_ {n + 1}) = 1 [/ math]
Luego
[matemáticas] mcd (f_ {n + 1}, f_ {n + 2}) = gcd (f_ {n + 1}, f_n + f_ {n + 1}) = gcd (f_n, f_ {n + 1}) = 1 [/ matemáticas]
Por lo tanto, por inducción
[matemáticas] \ forall n \ in \ mathbb N ^ *, mcd (f_n, f_ {n + 1}) = 1 \ etiqueta 2 [/ matemáticas]
En tercer lugar,
[math] \ forall (k, m, n) \ in \ mathbb N ^ *, gcd (m, n) = 1 \ Rightarrow gcd (m, kn) = gcd (m, k) \ tag 3 [/ math]
Ahora, veamos la matriz
[matemáticas] A = \ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} [/ math]
Tenemos
[matemática] A ^ {1 + 1} = \ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} = \ begin {pmatrix} 1 & 1 \\ 1 & 2 \ end {pmatrix} = \ begin {pmatrix} f_1 & f_2 \\ f_2 & f_3 \ end {pmatrix} [/ math]
Asumamos que
[matemáticas] A ^ {k + 1} = \ begin {pmatrix} f_ {k} & f_ {k + 1} \\ f_ {k + 1} & f_ {k + 2} \ end {pmatrix} [/ math ]
Luego
[matemáticas] A ^ {k + 2} = \ begin {pmatrix} f_ {k} & f_ {k + 1} \\ f_ {k + 1} & f_ {k + 2} \ end {pmatrix} \ begin { pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} = \ begin {pmatrix} f_ {k + 1} & f_ {k} + f_ {k + 1} \\ f_ {k + 2} & f_ { k + 1} + f_ {k + 2} \ end {pmatrix} = \ begin {pmatrix} f_ {k + 1} & f_ {k + 2} \\ f_ {k + 2} & f_ {k + 3} \ end {pmatrix} [/ math]
Entonces, por inducción
[matemáticas] \ forall k \ in \ mathbb N ^ * \ setminus {1} [/ matemáticas]
[matemáticas] A ^ k = \ begin {pmatrix} f_ {k-1} & f_k \\ f_k & f_ {k + 1} \ end {pmatrix} [/ math]
Como consecuencia
[math] \ forall (m, n) \ in \ mathbb N ^ * A ^ {m + n} = A ^ mA ^ n \ Leftrightarrow \ begin {pmatrix} f_ {m + n-1} & f_ {m + n} \\ f_ {m + n} & f_ {m + n + 1} \ end {pmatrix} = \ begin {pmatrix} f_ {m} f_ {n} + f_ {m-1} f_ {n-1 } & f_mf_ {n + 1} + f_ {m-1} f_n \\ f_ {m + 1} f_n + f_mf_ {n-1} y f_ {m + 1} f_ {n + 1} + f_mf_n \ end { pmatrix} [/ math]
Y
[matemáticas] f_ {m + n} = f_mf_ {n + 1} + f_ {m-1} f_n \ tag 4 [/ matemáticas]
Ahora, supongamos que
[matemáticas] \ existe (k, r) \ en \ mathbb N, n = km + r, 0 \ le r \ lt m [/ matemáticas]
Tenemos
[matemática] mcd (f_m, f_n) = mcd (f_m, f_ {mk + 1} f_r + f_ {mk} f_ {r-1}) (4) [/ matemática]
Pero como [math] f_m \ pipe f_ {mk} [/ math]
[matemática] mcd (f_m, f_n) = mcd (f_m, f_ {mk + 1} f_r) [/ matemática]
Sin embargo, sabemos que
[matemáticas] mcd (f_ {mk}, f_ {mk + 1}) = 1 [/ matemáticas]
Entonces
[matemática] mcd (f_m, f_ {mk + 1}) = 1 [/ matemática]
[matemática] mcd (f_m, f_n) = mcd (f_m, f_r) (3) [/ matemática]
Por iteración, y mediante el uso del algoritmo euclidiano – Wikipedia, obtendremos, suponiendo que [math] gcd (m, n) = s [/ math]
[matemática] mcd (f_m, f_n) = mcd (f_s, 0) = f_s [/ matemática]
Ahora tenga en cuenta que
[matemáticas] f_1 = 1 [/ matemáticas]
[matemáticas] f_2 = 1 [/ matemáticas]
[matemáticas] f_3 = 2 [/ matemáticas]
[matemáticas] f_4 = 3 [/ matemáticas]
[matemáticas] f_5 = 5 [/ matemáticas]
[matemáticas] f_6 = 8 [/ matemáticas]
Entonces, [matemáticas] \ forall n \ gt 6 [/ matemáticas]
[matemática] \ begin {align} \ exist k \ in \ mathbb N, f_n = 2 ^ k & \ Rightarrow gcd (f_6, f_n) = f_6 \\ & \ Rightarrow gcd (f_6, f_n) = f_6 \\ & \ Rightarrow mcd (6, n) = 6 \\ & \ Rightarrow \ exist p \ in \ mathbb N ^ * \ setminus \ {1 \}, n = 6 ^ p \\ & \ Rightarrow gcd (36, n) = 36 \\ & \ Rightarrow gcd (9, n) = 9 \\ & \ Rightarrow gcd (f_9, f_n) = f_9 \ end {align} [/ math]
Pero
[matemáticas] f_7 = 13 [/ matemáticas]
[matemáticas] f_8 = 21 [/ matemáticas]
[matemáticas] f_9 = 34 [/ matemáticas]
Entonces
[matemática] \ existe k \ en \ mathbb N, f_n = 2 ^ k \ Rightarrow mcd (f_9, f_n) = 34 [/ matemática]
Lo cual es una contradicción.
Entonces, todos los poderes de [math] 2 [/ math] en la secuencia de Fibonacci son
[matemáticas] 2 [/ matemáticas] y [matemáticas] 8 [/ matemáticas]
