A prova de Euclides de que existem infinitos números primos
Por volta de 300 a.C., Euclides escreveu um argumento curto o bastante para caber em um único parágrafo. Ele nunca foi melhorado, porque não dá para melhorar. A afirmação é que os números primos seguem para sempre, e a prova é uma construção: me dê qualquer lista finita de primos e eu lhe entrego um primo que não está nela.
Dois mil anos depois, o argumento ainda tem a qualidade de um bom truque de mágica. Você vê cada passo com clareza. Você sabe exatamente como ele termina. E ele continua funcionando.
O que é um primo e por que a pergunta importa
Um número primo é um número inteiro maior que 1 cujos únicos divisores são 1 e ele mesmo. Os primeiros são 2, 3, 5, 7, 11, 13. Eles ficam dentro dos números inteiros como átomos: todo outro número inteiro é construído multiplicando primos. O número 30, por exemplo, se decompõe como 2 vezes 3 vezes 5, e existe essencialmente uma única maneira de fazer essa fatoração.
Dado que os primos são os blocos de construção de todos os números inteiros, é natural perguntar: eles acabam? Existe um maior primo, além do qual o poço seca? A resposta de Euclides é não, e o caminho que ele toma é elegante o bastante para ser acompanhado em uma sentada só.
O ponto de partida: suponha que a lista está completa
O argumento é uma prova por contradição. Você começa concedendo ao adversário tudo o que ele quer.
Suponha que existem apenas finitos primos
Suponha, para efeito de argumentação, que a coleção completa de todos os primos é uma lista finita: p1, p2, p3, até pk. Nenhum primo existe fora dessa lista. Essa é a suposição que vamos destruir.
Agora, tendo reunido nessa lista todos os primos existentes, construa um novo número a partir deles.
Construindo o número que quebra a lista
Forme N multiplicando todos os primos listados e somando 1
Seja N = (p1 vezes p2 vezes p3 vezes ... vezes pk) + 1. Ou seja: pegue o produto de todos os primos da lista supostamente completa e some 1.
Esse é o movimento central, e vale a pena desacelerar para ver o que ele faz. Multiplicar todos os primos listados dá um número que todo primo da lista divide de forma exata. Somar 1 desarruma todos eles de uma vez.
Quando você divide N por p1, o resto é 1, porque o produto (p1 vezes p2 vezes ... vezes pk) é divisível por p1, e somar 1 desloca o resto para 1. A mesma lógica vale para p2, para p3, para todo primo da lista. Nenhum deles divide N de forma exata.
A contradição
N tem um fator primo, mas esse fator não pode estar na lista
Todo inteiro maior que 1 tem pelo menos um fator primo. Isso é consequência do teorema fundamental da aritmética: continue fatorando até não dar mais, e o que sobra são primos. Então N tem um fator primo. Chame-o de q.
Acabamos de mostrar que nenhum primo da lista divide N. Portanto q não está na lista. Mas supusemos que a lista continha todos os primos. Essa é a contradição: encontramos um primo, q, que não está na lista supostamente completa.
A suposição precisa ser falsa
Como a suposição de que existem apenas finitos primos leva diretamente a uma contradição, a suposição é falsa. Não existe lista finita que contenha todos os primos. Os primos seguem para sempre.
O contraexemplo que mantém a prova honesta
É aqui que muitos relatos populares da prova de Euclides se perdem. Eles afirmam que o próprio N é sempre primo. Não é, e a distinção importa.
Tome a lista {2, 3, 5, 7, 11, 13}. O produto é 2 vezes 3 vezes 5 vezes 7 vezes 11 vezes 13, que dá 30030. Some 1 e você tem N = 30031.
30031 é primo? Não.
30031 = 59 vezes 509.
Tanto 59 quanto 509 são primos, e nenhum dos dois aparece na lista {2, 3, 5, 7, 11, 13}. É exatamente o que a prova prevê: não que N seja primo, mas que os fatores primos de N estejam ausentes da lista. Neste caso os fatores primos são 59 e 509, dois primos que ficaram de fora da lista finita. O argumento se confirma, mas a confirmação vem dos fatores, não do próprio N.
O que a prova realmente diz
Vale a pena parar no formato do argumento, porque ele é excepcionalmente limpo.
Você não constrói explicitamente o primo que falta. Você não sai procurando por ele. Você prova que ele precisa existir mostrando que supor o contrário leva a um beco sem saída lógico. O primo q escondido nos fatores de N pode ser fácil de achar (como 59 e 509 são, se você testar alguns divisores pequenos de 30031) ou pode ser enorme. A prova não se importa. A força dela vem da inevitabilidade: seja qual for a lista entregue, a construção encontra uma brecha.
Isso se conecta naturalmente a outras provas que seguem o mesmo espírito de "suponha o contrário e veja tudo desabar". O argumento diagonal de Cantor usa a mesma estrutura em escala maior: suponha que existe uma lista completa dos números reais e então construa um número real comprovadamente ausente dela. O eco de Euclides é inconfundível.
Por que os primos nunca rareiam por completo
Uma coisa que a prova não conta é a que distância os primos podem ficar uns dos outros, nem quão grande pode ser o próximo primo depois de um primo dado. O argumento de Euclides garante apenas existência: em algum lugar além de qualquer coleção finita, vive outro primo. A distribuição dos primos ao longo da reta numérica é uma questão bem mais difícil e continua sendo uma das áreas em aberto mais profundas da matemática.
O que a prova conta é estrutural. Os números primos não podem ser esgotados por nenhum meio finito. Você poderia dedicar a vida inteira a listar primos e estaria sempre listando dentro de um resto infinito. Todo primo que você encontrou era real, mas os que estavam à sua frente eram igualmente reais, igualmente numerosos e igualmente inalcançáveis por uma lista finita.
Para ter uma noção de quão rápido os números crescem quando você constrói com multiplicação e expoentes, o artigo sobre entender os expoentes de forma intuitiva é um companheiro natural: o produto p1 vezes p2 vezes ... vezes pk cresce mais rápido do que se imagina, e esse crescimento é parte do motivo de N ficar tão grande tão depressa.
O zen da coisa
A prova de Euclides tem mais de dois milênios, e os matemáticos já encontraram centenas de demonstrações do mesmo resultado desde então. Nenhuma delas tornou esta aqui obsoleta. Ela mantém seu lugar não por ser a mais engenhosa nem a mais geral, mas por ser a mais transparente.
Você vê o argumento inteiro em uma passada só. A construção é natural. A contradição é afiada. Não existe passo em que você precise aceitar algo por fé ou confiar que uma máquina complicada está fazendo o que promete.
O que a prova pede que você guarde na cabeça é uma ideia só: qualquer lista finita de primos já está incompleta. Não porque a lista foi mal escolhida, mas porque os primos são o tipo de coisa que não cabe em nenhuma contagem finita. Eles pertencem ao infinito do mesmo jeito que os inteiros pertencem, ou as frações, ou os pontos de uma reta. A prova não diz onde está o próximo primo. Ela diz que o próximo primo está sempre lá.
Isso basta. Isso sempre bastou.
Para outros resultados que compartilham esse espírito de inevitabilidade, o teorema de Goodstein mostra uma sequência que sempre volta a zero apesar de crescer além de qualquer coisa escrevível, usando a mesma lógica de "algo precisa acontecer porque a alternativa é impossível". Vale a pena conhecer essa família de argumentos. Cada um é um ângulo diferente sobre o mesmo fato de fundo: a matemática não tem saída de emergência. A estrutura se sustenta.
Perguntas frequentes
- Existem infinitos números primos?
- Sim. Euclides provou isso por volta de 300 a.C. Não importa quantos primos você reúna em uma lista, o argumento constrói um número cujos fatores primos ficam todos fora dessa lista, então pelo menos um primo novo precisa existir.
- A prova de Euclides mostra que N = (p1 x p2 x ... x pk) + 1 é sempre primo?
- Não, e esse é o erro mais comum ao contar a prova. N só precisa ter um fator primo que não esteja na lista, e esse fator pode ser o próprio N ou pode ser um número menor. Por exemplo, 2x3x5x7x11x13 + 1 = 30031, que NÃO é primo: 30031 = 59 x 509. Tanto 59 quanto 509 são primos ausentes da lista {2,3,5,7,11,13}, então a prova continua funcionando perfeitamente.
- Que tipo de prova é o argumento de Euclides?
- É uma prova por contradição (reductio ad absurdum). Você supõe o contrário do que quer provar, ou seja, que existem apenas finitos primos, e então mostra que essa suposição leva a uma contradição.
- Como a prova garante que existe um primo fora da lista?
- O número N construído deixa resto 1 quando dividido por qualquer primo da lista, então nenhum dos primos listados divide N. Mas todo inteiro maior que 1 tem pelo menos um fator primo. Portanto N tem um fator primo, e esse fator não pode estar na lista. Um primo fora da lista está garantido.
- Isso tem relação com o argumento diagonal de Cantor ou com o teorema de Goodstein?
- Os três estão na mesma família de resultados em que uma construção simples derrota qualquer tentativa de descrição finita (ou enumerável) completa. Euclides derrota qualquer lista finita de primos, Cantor derrota qualquer lista enumerável de números reais, e Goodstein produz uma sequência que derrota o poder de demonstração da aritmética de Peano.
Coloque em prática
Gostou de pensar sobre isso?
O Math Zen transforma esse tipo de intuição em prática diária, com exercícios adaptativos em 24 temas de matemática.
