Considere o n-ésimo número de Fermat \mathrm{f}_{n}=2^{2^{n}}+1.
(a) Mostre por indução que \mathrm{f}_{n}=\mathrm{f}_{0} \mathrm{f}_{1} \cdots \mathrm{f}_{n-1}+2
(b) Usando o item anterior, mostre o “Teorema de Golbach”: quaisquer dois números de Fermat são coprimos.
(sugestão: observe que se m<n então o item (a) diz que \mathrm{f}_{n}=\mathrm{f}_{0} \mathrm{f}_{1} \cdots \mathrm{f}_{m} \cdots \mathrm{f}_{n-1}+2. Agora suponha que d divide \mathrm{f}_{n} e \mathrm{f}_{m}, \ldots )

Passo 1

Resumo do que o enunciado pede e as informações dadas.
O enunciado define o n-ésimo número de Fermat por
\mathrm{f}_{n}=2^{2^{n}}+1.
As perguntas são duas:
  1. Mostrar por indução que
\mathrm{f}_{n}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}+2.
  1. Usando o item anterior, provar o “Teorema de Golbach”: quaisquer dois números de Fermat são coprimos (ou seja, se m\neq n então \gcd(\mathrm{f}_{m},\mathrm{f}_{n})=1).
Informações relevantes dadas e que vamos usar:
  • A definição explícita \mathrm{f}_{n}=2^{2^{n}}+1.
  • Para a parte (a) é exigido uso de indução matemática.
  • Para a parte (b) podemos usar a identidade da parte (a) e propriedades elementares de divisibilidade e do máximo divisor comum (gcd).

Passo 2

Entendendo a técnica que vamos usar: indução matemática (explicação didática).
Indução é um método para provar afirmações P(n) para todo n natural, em dois passos:
  • Base: provar P(0) (ou P(1) dependendo do início).
  • Passo indutivo: assumir P(k) verdadeira para um k arbitrário (hipótese indutiva) e então provar P(k+1).
Se ambos os passos são verdadeiros, então P(n) vale para todo n natural. Aqui P(n) será a afirmação
\mathrm{f}_{n}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}+2.
Vou detalhar base e passo indutivo de forma explícita.

Passo 3

Base da indução: n=0.
Calculemos \mathrm{f}_{0} pela definição:
\mathrm{f}_{0}=2^{2^{0}}+1=2^{1}+1=2+1=3.
O produto vazio (produto de \mathrm{f}_{0} até \mathrm{f}_{-1}) é, por convenção, 1. Portanto a expressão à direita para n=0 é
\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{-1}+2 = 1 + 2 = 3.
Logo a igualdade é verdadeira para n=0:
\mathrm{f}_{0}=1+2=3.
A base está provada.

Passo 4

Preparação algébrica útil (observação que será usada no passo indutivo).
Note que, pela definição,
2^{2^{n}}=\mathrm{f}_{n}-1.
Assim
\mathrm{f}_{n+1}=2^{2^{\,n+1}}+1=(2^{2^{n}})^{2}+1=(\mathrm{f}_{n}-1)^{2}+1.
Expandindo, obtemos
\mathrm{f}_{n+1}=\mathrm{f}_{n}^{2}-2\mathrm{f}_{n}+2.
Guarde esta forma, pois ela ligará \mathrm{f}_{n+1} ao quadrado de \mathrm{f}_{n}.

Passo 5

Passo indutivo: suponha a afirmação verdadeira para algum n\ge0 (hipótese indutiva) e prove para n+1.
Hipótese indutiva: suponha
\mathrm{f}_{n}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}+2.
Multiplicando os dois lados por \mathrm{f}_{n} obtemos:
\mathrm{f}_{n}\cdot\mathrm{f}_{n}=\mathrm{f}_{n}\big(\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}\big)+2\mathrm{f}_{n}.
O lado direito pode ser reescrito reconhecendo o produto completo até \mathrm{f}_{n}:
\mathrm{f}_{n}^{2}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n}+2\mathrm{f}_{n}.
Agora isole \mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n}:
\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n}=\mathrm{f}_{n}^{2}-2\mathrm{f}_{n}.

Passo 6

Concluir o passo indutivo usando a expressão para \mathrm{f}_{n+1} obtida no Passo 4.
Do Passo 4 temos
\mathrm{f}_{n+1}=\mathrm{f}_{n}^{2}-2\mathrm{f}_{n}+2.
Comparando com a expressão do Passo 5 para \mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n} (que é \mathrm{f}_{n}^{2}-2\mathrm{f}_{n}), vemos que
\mathrm{f}_{n+1}=\big(\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n}\big)+2.
Isso é exatamente a fórmula desejada para n+1. Portanto, o passo indutivo está completo: se vale para n então vale para n+1.

Passo 7

Conclusão da parte (a).
Como a base (Passo 3) foi provada e o passo indutivo (Passos 5–6) foi demonstrado, por indução a fórmula é verdadeira para todo n\ge0:
\boxed{\mathrm{f}_{n}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}+2.}
Comentário didático rápido: essa identidade também pode ser vista por uma fatoração geral
(x-1)\prod_{k=0}^{n-1}(x^{2^{k}}+1)=x^{2^{n}}-1,
avaliada em x=2, que dá a mesma relação \prod_{k=0}^{n-1}\mathrm{f}_{k}=2^{2^{n}}-1, e daí \mathrm{f}_{n}=\prod_{k=0}^{n-1}\mathrm{f}_{k}+2.

Passo 8

Preparação para a parte (b): entender o que significa serem coprimos.
Dois inteiros a e b são coprimos quando \gcd(a,b)=1, isto é, o maior divisor comum é 1. Outra forma útil: se uma d>1 divide simultaneamente a e b, então a e b não são coprimos. Vamos mostrar que isso não ocorre para dois Fermat distintos.

Passo 9

Prova do “Teorema de Golbach” (parte (b)): quaisquer dois números de Fermat são coprimos.
Sejam m e n com m<n. Suponha que existe um divisor comum d de \mathrm{f}_{m} e \mathrm{f}_{n}; ou seja, d\mid \mathrm{f}_{m} e d\mid \mathrm{f}_{n}. Pela identidade provada na parte (a) temos
\mathrm{f}_{n}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}+2.
O produto \mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1} contém o fator \mathrm{f}_{m} (já que m\le n-1). Portanto d divide esse produto. Se d divide o produto e também divide \mathrm{f}_{n}, então d divide a diferença
\mathrm{f}_{n}-\big(\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}\big)=2.
Logo d divide 2. Portanto d\in\{1,2\}.

Passo 10

Excluir a possibilidade d=2.
Observe que todo número de Fermat é ímpar, pois \mathrm{f}_{k}=2^{2^{k}}+1 é potência de 2 (par) somada de 1, logo é ímpar. Assim nenhum \mathrm{f}_{k} é divisível por 2. Portanto d não pode ser 2. A única possibilidade restante é d=1.

Passo 11

Conclusão da parte (b).
Como qualquer divisor comum d de \mathrm{f}_{m} e \mathrm{f}_{n} com m\neq n deve ser 1, concluímos que \gcd(\mathrm{f}_{m},\mathrm{f}_{n})=1. Ou seja, quaisquer dois números de Fermat são coprimos. Isso é o que o enunciado chama de “Teorema de Golbach”.

Resposta

(a) \mathrm{f}_{n}=\mathrm{f}_{0}\mathrm{f}_{1}\cdots\mathrm{f}_{n-1}+2.
(b) Para m\neq n vale \gcd(\mathrm{f}_{m},\mathrm{f}_{n})=1.

Exercícios relacionados