onde Fk é o k-ésimo número de Fibonacci. Vamos usar duas propriedades clássicas dos Fibonacci:
Se amid b então Famid Fb.
gcd(Fm,Fn)=Fgcd(m,n).
Passo 2
Provar que amid bimplies Famid Fb.
Usamos a identidade de adição
Fx+y ;=; Fx,Fy+1;+;Fx-1,Fy
Seja b=k,a. Vamos por indução em k>=1:
Base (k=1): F1cdot a=Fa, claro que Famid Fa.
Passo indutivo: suponha Famid Fk,a e Famid F(k-1)a. Então F(k+1)a = Fk,a + a = Fk,a,Fa+1 + Fk,a -1,Fa Pelo passo indutivo Famid Fk,a e também Famid Fa, logo cada termo do lado direito é múltiplo de Fa. Concluímos Famid F(k+1)a.
Portanto, como mmid mn e nmid mn, temos
Fm mid Fmn e Fn mid Fmn
Passo 3
Calcular gcd(Fm,Fn).
É conhecido (ou pode-se provar por algoritmo de Euclides nos índices) que
gcdl(Fm,Fnr) ;=; Fgcd(m,n)
Como gcd(m,n)=1, segue
gcdl(Fm,Fnr) = F1 = 1,
ou seja, Fm e Fn são primos entre si.
Passo 4
Concluir que o produto divide.
Temos
Fm mid Fmn, Fn mid Fmn, gcd(Fm,Fn)=1
Pela propriedade aritmética de números inteiros, se amid k e bmid k e gcd(a,b)=1, então abmid k. Aplicando com a=Fm, b=Fn e k=Fmn, obtemos
Fm,Fn ;m|; Fmn
Resposta
Fm,Fn;m|;Fmn
Cálculo - Hygino Domingues - Fundamentos de Aritmética - 1ª Edição - Capítulo 2.Exercícios - Ex. 142