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:
onde
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:
Esse
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
ou é primo ou é divisível por algum primo. Mas não pode ser nenhum dos
, já que cada divisão desses deixa resto 1.
Passo 6
Logo,
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
até
. 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.