Demuestra que dos términos consecutivos cualesquiera de la sucesión de Fibonacci son relativamente primos

Question

Demuestra que dos términos consecutivos cualesquiera de la sucesión de Fibonacci son relativamente primos.

Mi intento:

Tenemos $f_1 = 1, f_2 = 1, f_3 = 2, \dots$ , así que obviamente $\gcd(f_1, f_2) = 1$ .
Supongamos que $\gcd(f_n, f_{n+1}) = 1$ demostraremos que $\gcd(f_{n+1}, f_{n+2}) = 1$ . Considere $\gcd(f_{n+1}, f_{n+2}) = \gcd(f_{n+1}, f_{n+1} + f_n)$ porque $f_{n+2} = f_{n+1} + f_n.$
Entonces $\gcd(f_{n+1}, f_{n+1} + f_n) = \gcd(f_{n+1}, f_{n}) = 1$ (propiedad gcd).

Por lo tanto, $\gcd(f_n, f_{n+1}) = 1$ para todos $n > 0$ .

¿Estoy en el camino correcto?
Cualquier comentario será muy apreciado.

Gracias,

Answer 1

Enhorabuena, lo has resuelto. Has utilizado el hecho de que gcd(a+b,b)=gcd(a,b)

Answer 2

Su prueba es buena. Como referencia, tengo una prueba sin inducción que utiliza La identidad de Cassini , $$f_{n-1}f_{n+1} - f_nf_n = (-1)^n,$$ que se demuestra directamente en esa página de Wikipedia y de otra manera directa en Mostrar $F_{n+1} \cdot F_{n-1} = F_n^2 + (-1)^n$ para todos $n \in \mathbb{N}$ .

Según si $n$ es par o impar, tenemos $$f_{n-1}f_{n+1} - f_nf_n = 1 \qquad \text{or} \qquad f_nf_n - f_{n-1}f_{n+1} = 1.$$

Ahora, el gcd de $f_n$ y $f_{n+1}$ puede definirse alternativa y equivalentemente como el menor número entero positivo que puede escribirse de la forma $pf_n + qf_{n+1}$ donde $p$ y $q$ son números enteros . Porque los coeficientes de $f_n$ y $f_{n+1}$ en ese par de ecuaciones son números de Fibonacci, por lo tanto enteros, y como no hay ningún entero positivo menor que $1$ , gcd $(f_n, f_{n+1}) = 1$ . Así, dos términos consecutivos cualesquiera de la sucesión de Fibonacci son relativamente primos.

Answer 3

Otro enfoque. Supongamos que $gcd(f_{n+1}, f_{n}) = d$ . Entonces, como $f_{n+1} = f_n + f_{n-1}$ , $gcd(f_n, f_{n-1}) \ne 1$ y por descenso infinito acabaremos con n = 4 y n = 3 donde gcd(2,3) = 1. Contradicción.

Answer 4

Su prueba es buena. Como referencia, tengo una prueba similar por inducción:

La afirmación es cierta para los primeros pares de números de Fibonacci consecutivos, así que supongamos que es cierta hasta $f_{n+1}$ para que gcd $(f_{n}, f_{n+1}) = 1$ . Entonces, por La identidad de Bézout existen números enteros $x$ y $y$ tal que $xf_{n} + yf_{n+1} = 1$ . Así que \begin {align} 1 & = xf_{n} + yf_{n+1} \\ & = x(f_{n+2} - f_{n+1}) + yf_{n+1} \\ & = (y - x) f_{n+1} + xf_{n+2}. \end {align} Ahora, el gcd de $f_{n+1}$ y $f_{n+2}$ puede definirse alternativa y equivalentemente como el menor número entero positivo que puede escribirse de la forma $uf_{n+1} + vf_{n+2}$ donde $u$ y $v$ son números enteros . Porque $y - x$ y $x$ son números enteros y no hay ningún número entero positivo que $1$ , gcd $(f_{n+1}, f_{n+2}) = 1$ . Por lo tanto, la afirmación es válida para $n + 2$ siempre que se mantenga para $n + 1$ y, por tanto, el principio de inducción garantiza que se cumple para cada par de números de Fibonacci consecutivos.

Observación: He llamado a esta prueba similar a la tuya porque la identidad de Bézout se utiliza para demostrar la propiedad gcd que tú has utilizado.

Answer 5

Utilizando la inducción/aritmética modular:

Para n = 1, vemos que $F_n$ y $F_{n+1}$ son relativamente primos.

Para el paso inductivo, suponemos $F_n$ y $F_{n+1}$ son relativamente primos, y demostrar que esto implica $F_{n+1}$ y $F_{n+2}$ son relativamente primos.

Por la suposición inductiva, para cualquier primo $p$ para lo cual $p|F_{n+1}$ , $p∤F_n$ . Con la aritmética modular, esta afirmación se convierte en $$F_{k+1} ≡ 0⠀mod(p)$$ y $$ F_k ≢ 0⠀mod(p)$$ Usando la definición de la secuencia de Fibonacci, podemos cambiar la primera congruencia a $$F_{k+2} - F_k ≡ 0⠀mod(p)$$ $$F_{k+2} ≡ F_k≢ 0⠀mod(p)$$ La congruencia modular es transitiva (esto es bastante claro, ya que $3≡7≡15⠀mod(4),⠀ 3≡15⠀mod (4)$ .) Así, $F_{k+2} ≢0⠀mod(p)$ , lo que significa $p∤F_{k+2}$ y $F_{n+1}$ y $F_{n+2}$ son relativamente primos.