Por que existem infinitos primos (Euclides)

Por que existem infinitos primos

Os primos ficam mais raros conforme os números crescem: há 25 primos até 100, e apenas 168 até 1000. Mas será que, em algum ponto, eles acabam? Euclides respondeu a essa pergunta com uma das provas mais elegantes da matemática, e ela continua valendo sem mudanças.

A prova por contradição

Suponha, por absurdo, que existam só finitos primos: p₁, p₂, …, pₙ. Multiplique todos eles e some 1. Chame o resultado de N.

O número N não é divisível por nenhum dos primos da lista, porque sempre sobra resto 1. Mas todo número maior que 1 tem pelo menos um fator primo. Esse fator primo novo não está na lista, o que contradiz a suposição.

Portanto a lista nunca pode ser completa. Sempre existe um primo além de qualquer limite.

Na aula, você pode montar a lista como quiser. O painel mostra o produto, N, os restos de N em cada primo (sempre 1) e a fatoração de N. Quando o fator novo aparece, a contradição está à vista.

O que a prova não diz

A prova garante que há infinitos primos, mas não diz onde eles estão nem como encontrá-los. Ela também não diz que N é primo: às vezes N é composto, como em 2·3·5·7·11·13 + 1 = 30031 = 59 · 509. O argumento só precisa de um fator primo novo, e isso sempre existe.

Também não diz que o fator novo é necessariamente grande. Com a lista 3, 5, 7, temos N = 106 = 2 · 53: o fator novo é o 2, que estava fora da lista, e o 53 também. A prova só afirma que algum primo novo existe.

Por que ela é uma contradição

A estrutura é a de uma prova por absurdo: supomos uma hipótese (a lista é completa) e chegamos a uma consequência impossível (existe um primo fora dela). Logo a hipótese é falsa. É o mesmo tipo de argumento que aparece em muitos resultados de teoria dos números.

Um pouco de história

A prova está no livro IX dos Elementos, por volta de 300 a.C. Euclides a apresenta com palavras, sem símbolos algébricos, e ela continua a ser a referência para o tema. Desde então, outras provas apareceram, como a de Euler, que usa séries, mas a de Euclides é a mais direta.

Aplicações

• Criptografia: o sistema RSA depende de números primos grandes, e a existência deles em quantidade infinita garante que sempre é possível escolher um novo.
• Fatoração: a dificuldade de fatorar números grandes, que a prova de Euclides não resolve, é o que sustenta a segurança de sistemas como o RSA.
• Teoria dos números: a distribuição dos primos (quantos há até x) é uma das questões centrais da área.

Curiosidade

Os primos de Mersenne (2ⁿ − 1 quando primo) são os maiores primos conhecidos, e a busca deles é feita por computadores em projetos voluntários. O maior conhecido tem milhões de algarismos, mas a prova de Euclides garante que sempre existirá um maior.

Perguntas de revisão

1. Por que o número N = (produto dos primos) + 1 não pode ser divisível por nenhum primo da lista?

Resposta: porque deixa sempre resto 1 ao ser dividido por cada um deles. Não é porque N é sempre primo, nem porque é sempre par.

1. O que a prova de Euclides afirma?

Resposta: que nunca existe uma lista finita com todos os primos. Não afirma que N é sempre primo.