Seja F1=F2=1 e Fn+2=Fn+1+Fn, para n >= 1, a sequência de Fibonacci. Prove que quaisquer dois termos consecutivos dessa sequência são sempre primos entre si, ou seja, gcd(Fk, Fk+1)=1, forall k in N.

Passo 1

Beleza, o enunciado diz que a sequência de Fibonacci é definida por
F1 = F2 = 1, Fn+2 = Fn+1 + Fn;(n>=1),
e a gente precisa provar que quaisquer dois termos consecutivos são primos entre si, ou seja
gcd(Fk, Fk+1) = 1forall kinN
O conteúdo aqui é teoria dos números: definição de máximo divisor comum (gcd), o algoritmo de Euclides e indução.

Passo 2

Primeiro, o que é gcd? Para dois inteiros gcd(a,b) ;=;gcd(a,,b - a)(quando (b>a)), , é o maior inteiro que divide ambos.
Uma ferramenta chave é o algoritmo de Euclides, que usa a propriedade
porque qualquer divisor comum de e também divide , e vice-versa. Repetindo isso até um número virar zero, sobra justamente o gcd.

Passo 3

Caso base ( F1 = 1, F2 = 1 Longrightarrow gcd(F1,F2) = gcd(1,1) = 1 ):
Então a propriedade segura para .

Passo 4

Passo de indução. Suponha que para um gcd(Fk, Fk+1) = 1 qualquer valha
gcd(Fk+1, Fk+2) = 1
Queremos mostrar que
gcd(Fk+1, Fk+2) = gcdl(Fk+1,,Fk+1+Fkr) = gcdl(Fk+1,,Fkr) = gcd(Fk, Fk+1),
Como , aplicamos o algoritmo de Euclides:
e essa última é pela hipótese de indução.

Passo 5

Como o caso base funciona e o passo de indução mantém a propriedade, concluímos que para todo gcd(Fk, Fk+1) = 1 vale

Resposta

boxedgcd(Fk, Fk+1) = 1forall kinN

Exercícios relacionados