Considere a seguinte sequência de inteiros positivos:
.
(a) Prove que, se
, então
.
(b) Conclua que existem infinitos primos.
(a) Prove que, se
(b) Conclua que existem infinitos primos.
Passo 1
O enunciado define a sequência de inteiros positivos pelos termos
As perguntas são:
(a) Provar que, se , então
.\n
(b) Concluir que existem infinitos primos.
(a) Provar que, se
(b) Concluir que existem infinitos primos.
As informações relevantes fornecidas são exatamente a definição recursiva acima dos termos
(cada termo é o produto de todos os anteriores mais
) e que todos os
são inteiros positivos.
Passo 2
Vamos organizar conceitos básicos que vamos usar (explico como se estivéssemos numa prova, passo a passo):
- Dizemos que um inteiro
divide outro inteiro e escrevemos se existe inteiro tal que . Por exemplo, porque . - O máximo divisor comum de dois inteiros
e é o maior inteiro positivo que divide ambos. Em notação do enunciado escrevemos . Se dizemos que e são primos entre si (ou coprimos). - Uma propriedade útil (muito usada) é: se um inteiro
divide dois inteiros e , então também divide qualquer combinação linear inteira deles, por exemplo . Isto é porque, se e , então . - Todo inteiro
tem pelo menos um divisor primo (ou seja, um primo que divide ). Isso decorre do princípio da fatoração ou do argumento de descida: se não é primo, escrevemos com e repetimos o argumento até achar um fator primo.
Vou usar essas ideias explicitamente a seguir.
Passo 3
Prova de (a). Fixe
. Defina
Pela definição do enunciado temos
Agora seja
. Pelo fato de
ser um dos fatores do produto
, se
divide
então
também divide
. Logo temos:
Como
, qualquer inteiro que divide
e
divide a diferença
. Aplicando a propriedade da combinação linear mencionada,
Se um inteiro divide
, ele só pode ser
ou
; como estamos falando de divisores positivos, segue que
. Portanto
Esse argumento vale para qualquer escolha de
, o que termina a prova de (a).
Passo 4
Vou ilustrar com um exemplo numérico curto (só para tornar a ideia mais concreta):
,
(pois
),
. Repare que
e
, exatamente como a prova geral afirma. O mecanismo é sempre o mesmo:
é sempre um número que deixa resto
quando dividido por qualquer
com
.
Passo 5
Prova de (b). Queremos concluir que existem infinitos primos usando a propriedade dada em (a). A ideia é construir uma sequência infinita de primos distintos extraindo para cada
um primo que divida
.
Primeiro, observe que para todo
temos
. Logo cada
é um inteiro maior que
, portanto possui pelo menos um divisor primo. Para cada
escolha um primo
tal que
(essa escolha é possível por causa do comentário anterior).
Agora use (a): se existissem
tais que
, então esse primo dividiria simultaneamente
e
, o que contradiz o resultado de (a) que afirma que
. Portanto, para valores diferentes de
os primos
escolhidos são distintos. Assim construímos uma sequência infinita
de primos todos diferentes.
Logo, existem infinitos primos.
Passo 6
Resumo do raciocínio final (em linguagem de prova curta): cada
tem um primo divisor
. Pelo item (a)
não divide nenhum
com
, então
é novo (diferente de todos os anteriores). Assim obtemos infinitos primos distintos, um para cada
.
Resposta
(a)
para
.\n
(b) Existem infinitos primos.
(b) Existem infinitos primos.