Seja
e
, para
, a sequência de Fibonacci. Prove que quaisquer dois termos consecutivos dessa sequência são sempre primos entre si, ou seja,
.
Passo 1
Beleza, o enunciado diz que a sequência de Fibonacci é definida por
e a gente precisa provar que quaisquer dois termos consecutivos são primos entre si, ou seja
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
,
é o maior inteiro que divide ambos.
Uma ferramenta chave é o algoritmo de Euclides, que usa a propriedade
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 (
):
Então a propriedade segura para
.
Passo 4
Passo de indução. Suponha que para um
qualquer valha
Queremos mostrar que
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
vale