Mostre que existem infinitos números primos.

Passo 1

Beleza, vamos lá. O enunciado quer que a gente prove que existem infinitos números primos. Isso cai em Teoria dos Números, mais especificamente em prova por contradição. Para resolver, a gente vai precisar entender o que é número primo e como montar uma hipótese que leve a uma contradição.

Passo 2

Primeiro, o que é um número primo? É um inteiro maior que 1 que só pode ser dividido por 1 e por ele mesmo sem resto. Exemplo: 2, 3, 5, 7, 11… Então, para provar que há infinitos primos, a gente vai supor o contrário e mostrar que isso leva a um absurdo.

Passo 3

Hipótese de contradição: suponha que só existam finitos números primos. Listamos todos eles assim:
p1, p2, p3, dots, pn
onde p1=2, p2=3, etc., até pn que seria o último primo do universo, segundo a nossa suposição.

Passo 4

Agora a sacada de Euclides: construa um número novo dividindo por nenhum desses valores, ou seja, pegue o produto de todos e some 1:
N = p1 times p2 times dots times pn + 1
Esse N é legal porque, se você dividir por qualquer pi da lista, o resto sempre vai ser 1.

Passo 5

Vamos ver por que isso é ruim para a nossa hipótese. Se todo número maior que 1 é ou primo ou composto (teorema fundamental da aritmética), então N ou é primo ou é divisível por algum primo. Mas não pode ser nenhum dos p1, p2, dots, pn, já que cada divisão desses deixa resto 1.

Passo 6

Logo, N precisa ser primo “novo” ou precisa ter um primo divisor que não está na nossa lista. De qualquer forma, encontramos um primo fora dos p1 até pn. Isso contradiz a suposição de que a lista tinha todos os primos.

Resposta

Portanto, existe sempre pelo menos mais um primo além de qualquer lista finita que você fizer. Concluímos que existem infinitos números primos.

Exercícios relacionados