Os números primos são mais do que qualquer quantidade proposta de números primos.

— Euclides, Elementos, Proposição IX.20

Um número primo é um inteiro maior que 1 que só pode ser dividido por 1 e por ele mesmo: 2, 3, 5, 7, 11, 13, … Todos os outros, como $12=2\cdot2\cdot3$, são produtos de primos. Os primos são os átomos da aritmética.

Quanto mais se avança, mais raros eles ficam. Entre 1 e 100 há 25 primos; entre 1 000 001 e 1 000 100, só 6. Será que, a partir de algum ponto, eles acabam? Euclides mostrou que não, com um argumento de quatro linhas que o matemático inglês G. H. Hardy considerava um dos mais belos de toda a matemática.

A prova

Suponha que alguém lhe dê uma lista finita de primos, $p_1,p_2,\ldots,p_n$. Euclides mostra que existe pelo menos um primo fora da lista. Multiplique todos e some 1:

$$N=p_1\cdot p_2\cdots p_n+1.$$

Agora divida $N$ por qualquer primo da lista. O produto $p_1p_2\cdots p_n$ é divisível por ele, então o resto da divisão de $N$ é 1. Nenhum primo da lista divide $N$.

Mas $N$ é maior que 1, então tem pelo menos um divisor primo $q$. Por quê? Tome o menor divisor de $N$ maior que 1. Se ele não fosse primo, teria um divisor menor, que também dividiria $N$, contradizendo a escolha. Então o menor divisor é primo.

Esse primo $q$ divide $N$, e nenhum primo da lista divide $N$. Logo $q$ não está na lista. Nenhuma lista finita contém todos os primos:

$$\boxed{\text{existem infinitos números primos.}}$$

Euclides não fala em “infinito”, palavra que os gregos evitavam. Ele diz que, dada qualquer quantidade de primos, há mais. É a mesma coisa, dita com cuidado.

O número construído nem sempre é primo

Um erro comum é achar que $N$ é sempre primo. Veja:

Lista $N$ $N$ é primo?
2 3 sim
2, 3 7 sim
2, 3, 5 31 sim
2, 3, 5, 7 211 sim
2, 3, 5, 7, 11 2 311 sim
2, 3, 5, 7, 11, 13 30 031 não: $30\,031=59\cdot509$

Na sexta linha, $N$ é composto. Mas os seus fatores, 59 e 509, são primos que não estão na lista. A prova nunca disse que $N$ é primo; disse só que algum primo novo divide $N$. Ainda hoje não se sabe se a lista da tabela produz infinitos primos ou não.

Uma prova parecida, para os quadrados

O mesmo estilo de argumento, supor uma coisa e chegar a uma contradição, prova que $\sqrt2$ não é uma fração, outro resultado que os Elementos discutem no Livro X. Se $\sqrt2=\frac pq$ com a fração simplificada, então $p^2=2q^2$; $p^2$ é par, então $p$ é par, $p=2k$; daí $4k^2=2q^2$, $q^2=2k^2$, e $q$ também é par. Mas a fração estava simplificada. Contradição.

Exercício: comece pela lista 3, 5. Que número a construção produz, e que primo novo ele revela?

$N=3\cdot5+1=16=2^4$. O número é composto, e o seu único fator primo, $2$, não está na lista. A prova funciona com qualquer lista, mesmo que não comece por 2.

Exercício: mostre que há sequências de 5 números seguidos sem nenhum primo.

Tome $6!=720$. Os números $720+2$, $720+3$, $720+4$, $720+5$ e $720+6$ são divisíveis por 2, 3, 4, 5 e 6, respectivamente. Nenhum é primo. Com $(n+1)!$ obtém-se, do mesmo jeito, $n$ números seguidos compostos. Os primos não acabam, mas podem ficar tão espaçados quanto se queira.

Fontes: Elementos, Proposição IX.20, edição de D. E. Joyce · G. H. Hardy, Em defesa de um matemático (Martins Fontes, 2000) · GIMPS, Great Internet Mersenne Prime Search.

Todos os tópicos de Euclides · ← O algoritmo de Euclides: o máximo divisor comum · O quinto postulado e as outras geometrias →

Créditos das imagens.