Provando várias vezes para se ter certeza.

Se Euclides sabia, então você certamente também sabe que 

Existe uma infinidade de números primos.

O primeiro a provar esta afirmação foi Euclides (figura abaixo). Eis a sua prova:

Prova 1. (Euclides) Suponha que há somente uma quantidade finita de primos. Temos, então, todos os $k$ números primos $p_1 = 2, p_2=3,\ldots,p_k$. Considere o inteiro $P = p_1 p_2 \cdots p_k + 1$. Seja $p$ um divisor primo de $P$. Então $p$ deve ser igual a algum $p_r$. Mas então $p$ é um divisor de $P$ e do produto $ p_1 p_2 \cdots p_k$, logo é um divisor da diferença destes dois números $P -  p_1 p_2 \cdots p_k = 1$. Um absurdo. Portanto deve haver uma quantidade infinita de números primos. $\square$

Neste post, veremos várias outras provas tão memoráveis quanto àquela de Euclides. Tem para todos os gostos. Espero que tomem alguma como sua favorita.

Uma tão elementar quanto a de Euclides:

Prova 2. (Métrod) Suponha a existência de somente $k$ números primos $p_1 < p_2 <\cdots < p_k$. Seja $N = p_1 \cdots p_k$. Para cada $i =1,\ldots,k$, considere $Q_i = N/p_i$. Observe que $p_i$ não divide $Q_i$, mas divide $Q_j$, para $j\neq i$. Seja 

$$S = \sum_{j=1}^{k} Q_j .$$

Ora, existe um primo $p$ divisor de $S$ e devemos ter $p = p_i$, para algum $i \in\{1,\ldots,k\}$. Mas como $p_i$ divide cada um dos $Q_j$, para $j\neq i$, então $p_i$ divide $Q_i$, pois

$$ p_i \Big| \left( S - \sum_{j\neq i} Q_j \right) \Leftrightarrow p_i | Q_i.$$

Uma contradição. $\square$

Uma extravagante; a minha favorita:

Prova 3. (Mixon) Suponha que exista um total de $n$ primos $p_1=2,p_2,\ldots,p_n$. Tome $k$ suficientemente grande tal que $2^{k} > (k+1)^{n}$.

Considere a seguinte função $f:\{1,\ldots,2^{k}\} \longrightarrow \{0,\ldots,k\}^{n}$ definida por $f(x) := (e_1,\ldots,e_n)$, onde $x = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_n}^{e_n}$. Observe que pelo teorema fundamental da aritmética, a função está bem definida, exceto pelo fato ainda não garantido de que $f(x) \in \{0,\ldots,k\}^{n}$. Vejamos porque isto é verdade. Uma vez que $x \leq 2^k$, temos que

$$k = \log(2^{k}) \geq \log(x) = e_1 \log(p_1) + e_2 \log(p_2) + \cdots + e_n\log(p_n)$$ 

$$\geq e_1 + e_2 +\cdots + e_n \geq \max\{e_1,\ldots,e_n\},$$
onde o logaritmo acima é tomado na base 2. Logo $f(x) \in \{0,\ldots,k\}^{n}$. Por fim, o teorema fundamental da aritmética também garante que $f$ é injetiva. Mas isto induz uma contradição, pois $f$ é uma função injetiva de um conjunto de cardinalidade $2^k$ em um conjunto de cardinalidade $(k+1)^n$, o que implica em $2^k \leq (k+1)^n$. $\square$

Uma algébrica:

Prova 4. (?) Dado um primo $p$, mostraremos a existência de outro primo $q$ maior do que $p$. Considere $n = 2^{p}-1$ e seja $q$ um fator primo de $n$. Ora, como $q|2^{p}-1$, temos que  $2^{p} \equiv 1\;(\mathrm{mod}\;q)$. E uma vez que $p$ é primo, segue que $2$ possui ordem $p$ no grupo multiplicativo $\mathbb{Z}_{q}^{\ast}$. Agora o teorema de Lagrange garante que a ordem de um elemento de um grupo divide a ordem do grupo; portanto $p|(q-1)$, logo $q>p$. $\square$

Uma clássica; analítica:

Prova 5. (Euler) Esta prova se baseia na famosa identidade de Euler:

$$\sum_{n=1}^{\infty} \frac{1}{n} = \prod_{i=1}^{\infty}\left( \sum_{k=0}^{\infty} \frac{1}{p_{i}^{k}} \right),$$

onde $p_i$ é o $i$-ésimo primo.

Suponha que tenhamos apenas um número finito de primos $2 = p_1< p_2 < \cdots < p_r$. Então a identidade de Euler toma a forma

$$\sum_{n=1}^{\infty} \frac{1}{n} = \prod_{i=1}^{r}\left( \sum_{k=0}^{\infty} \frac{1}{p_{i}^{k}} \right).$$

Agora a série $\sum \frac{1}{p_{i}^{k}}$ converge, pois trata-se de uma série geométrica. A saber, vale que

$$  \sum_{k=0}^{\infty} \frac{1}{p_{i}^{k}} = \frac{1}{1-p_i^{-1}}.$$

Voltando para a identidade de Euler, temos

$$\sum_{n=1}^{\infty} \frac{1}{n} = \prod_{i=1}^{r}\left( \sum_{k=0}^{\infty} \frac{1}{p_{i}^{k}} \right) = \prod_{i=1}^{r}\frac{1}{1-p_i^{-1}} < +\infty.$$

Portanto a série harmônica converge. O que é um absurdo. $\square$

Uma combinatória:

Prova 6. (Pinasco) Suponha existência de apenas uma quantidade finitas de números primos $2=p_1 < \cdots < p_N$. Para $x\geq1$ dado, e para $i = 1,\ldots,N$, seja $A_i$ o conjunto dos inteiros em $[1,x]$ que são múltiplos de $p_i$. E seja $A$ o conjunto dos inteiros em $[1,x]$ que são múltiplos de algum primo. Devemos ter $A = \cup A_i$ e $A = \{1,\ldots,\lfloor x \rfloor\}$, portanto $|A| = \lfloor x \rfloor$. Pelo princípio da inclusão-exclusão, temos
$$\left| \bigcup_{i} A_i \right| = \sum_{i=1}^{N} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{N+1}|A_1\cap \cdots \cap A_N|.$$

Portanto, 

$$\lfloor x \rfloor= \sum_{i} \Big\lfloor\frac{x}{p_i} \Big\rfloor - \sum_{i < j} \Big\lfloor\frac{x}{p_i p_j} \Big\rfloor + \sum_{i<j<k}\Big\lfloor\frac{x}{p_i p_j p_k} \Big\rfloor - \cdots + (-1)^{N+1}\Big\lfloor\frac{x}{p_1 \cdots p_N} \Big\rfloor.$$

Uma vez que $$\lim_{x\to\infty} \frac{1}{x} \Big\lfloor \frac{x}{t}\Big\rfloor = \frac{1}{t},$$ temos que, dividindo a penúltima expressão por $x$ e tomando $x \to\infty$,
$$\sum_{i} \frac{1}{p_i}  - \sum_{i < j} \frac{1}{p_i p_j}  + \sum_{i<j<k}\frac{1}{p_i p_j p_k} - \cdots + (-1)^{N+1}\frac{1}{p_1 \cdots p_N} = 1.$$

Contudo, podemos reescrever a soma no lado esquerdo da expressão acima como
$$\sum_{i} \frac{1}{p_i}  - \sum_{i < j} \frac{1}{p_i p_j}  + \sum_{i<j<k}\frac{1}{p_i p_j p_k} - \cdots + (-1)^{N+1}\frac{1}{p_1 \cdots p_N} = 1 - \prod_{i=1}^{N}\left( 1 - \frac{1}{p_i}\right) < 1.$$
O leitor pode verificar a última igualdade. A última desigualdade é óbvia, uma vez observado que o produtório acima é positivo. Portanto chegamos numa contradição, pois temos 1 < 1. $\square$

Uma topológica(!):

Prova 7. (Fürstenberg) Vamos definir um topologia em $\mathbb{Z}$. Para $a,b\in\mathbb{Z},b>0$, denotaremos por $N_{b}(a)$ o conjunto $\{a+nb;\;n\in\mathbb{Z}\}$. Um conjunto $A\subseteq \mathbb{Z}$ é dito aberto se for vazio ou se para todo $a\in A$, existe $b>0$ tal que $N_{b}(a)\subseteq A$.

Verifiquemos que isto de fato define uma topologia. Primeiro, segue da definição que $\emptyset$ e $\mathbb{Z}$ são abertos. Também é claro que união de abertos é ainda um conjunto aberto. Agora se $A_1$ e $A_2$ são abertos, e se $a\in A_1 \cap A_2$, então existem $b_1,b_2>0$ tais que $N_{b_i}(a)\subseteq A_i$, para $i=1,2$. Mas então $N_{b_1 b_2}(a) \subseteq N_{b_i}(a)$, para $i=1,2$. Logo $N_{b_1 b_2}(a) \subseteq A_1 \cap A_2$. Portanto a interseção finita de abertos é ainda um aberto.

Observe que qualquer aberto não vazio nesta topologia possui infinitos elementos. Agora, podemos determinar um conjunto $N_{b}(a)$ da seguinte maneira:
$$ N_{b}(a) = \mathbb{Z} \setminus \bigcup_{i=1}^{b-1} N_{b}(a+i). $$
Portanto $N_{b}(a)$ é o complementar de um conjunto aberto, i.e., $N_{b}(a)$ é um conjunto fechado.

Agora voltemos para os números primos. Suponha que o conjunto dos números primos $\mathbb{P}$ seja finito. Então
$$\mathbb{Z} \setminus \{-1,1\} = \bigcup_{p\in\mathbb{P}} N_{p}(0) $$
é um conjunto fechado, pois é a união finita de conjuntos fechados. Portanto $\{-1,1\}$ é aberto, pois seu complementar é fechado. Mas isto é um absurdo, pois $\{-1,1\}$ é um conjunto finito. $\square$

Uma profunda:

Prova 8. (Erdős) Mostraremos algo mais forte:

A série dos recíprocos dos números primos diverge. Em outras palavras, $$\sum_{p \text{ primo}} \frac{1}{p} = \infty.$$

Seja $p_1,p_2,\ldots$ a sequência dos números primos (possivelmente finita). Suponha que a série acima convirja.  Então existe um $k$ tal que
$$\sum_{i>k} \frac{1}{p_i} < \frac{1}{2}.$$
Chamaremos os primos $p_1,\ldots,p_k$ de primos pequenos; e os demais primos, de primos grandes. Dado um número natural $N$, seja $N_{g}$ a quantidade de números naturais $n\leq N$ que são múltiplos de algum primo grande e seja $N_{p}$ quantidade de números naturais $n\leq N$ que têm somente divisores primos pequenos (isto é, que não são múltiplo de números grandes). Então devemos ter $N = N_p + N_g$. Mas mostraremos que $N> N_g + N_p$, para $N$ suficientemente grande.

Vamos primeiro estimar $N_g$. Observe que a quantidade de múltiplos de $p_i$ menores do que ou iguais a $N$ é exatamente $\Big\lfloor \frac{N}{p_i} \Big\rfloor$. Portanto,
$$N_g \leq \sum_{i >k} \Big\lfloor \frac{N}{p_i} \Big\rfloor \leq  \sum_{i >k}  \frac{N}{p_i} < \frac{N}{2}.$$

Agora estimemos $N_p$. Antes, veja que $2^k$ é quantidade de inteiros positivos que só possuem primos pequenos como fatores primos e são livres de quadrados (nenhum quadrado perfeito o divide). Agora, dado $n \leq N$, podemos escrevê-lo como $n = a_n (b_n)^2$, onde $a_n$ é livre de quadrados. Além disso, como $b_n \leq \sqrt{n} \leq \sqrt{N}$, concluímos que existem no máximo $\sqrt{N}$ candidatos a $b_n$. De modo que
$$ N_p \leq 2^{k} \sqrt{N}.$$

Assim,
$$ N = N_p + N_g < \frac{N}{2} + 2^{k} \sqrt{N}\Leftrightarrow \frac{N}{2} < 2^{k} \sqrt{N} \Leftrightarrow N < 2^{2k+2}.$$
Tomando $N$ grande, por exemplo, $N = 2^{2k+2}$, obtemos um absurdo. $\square$

Outras provas.

A seguir, darei ideias de outras provas da infinitude dos números primos, as quais fica a cargo do leitor verificá-las por completo.

Exercício 1. (Hermite) Seja $n$ um inteiro positivo. Mostre que se $d|(n!+1)$ e $d>1$, então $d>n$. Conclua que existem infinitos números primos.

Exercício 2. (Kummer) Mostre que para todo $n>2$ inteiro positivo, $\mathrm{mdc}(n,n-1) = 1$. Em particular, se $n = p_1 p_2 \cdots p_k >2$, então deve existir $p\neq p_i$, para todo $i=1,\ldots,k$, tal que $p|(n-1)$. Use isto para mostrar que há infinitos números primos.

Exercício 3. (Goldbach)  Os número da forma $F_n = 2^{2^n}+1,$ para $n\geq0$, são chamados de números de Fermat. Mostre que a seguinte relação entre os números de Fermat é válida: $$\prod_{k=0}^{n-1} F_k = F_n - 2.$$ (Sugestão: arrisque uma indução) Conclua que os números de Fermat são dois a dois primos entre si,. Ou seja, para todo $m\neq n\geq0$, temos $\mathrm{mdc}(F_m,F_n) = 1$. Conclua que devem existir infinitos números primos.

Exercício 4. (Stieltjes) Seja $N$ um número livre de quadrados, isto é, nenhum quadrado perfeito maior do que 1 divide $N$. Suponha que $N =mn$. Mostre que se $p$ é um número primo tal que $p|N$, então $p\nmid (m+n)$. Use isto para provar a infinitude dos números primos.

Exercício 5. (Schorn) Prove que os $n$ inteiros $(n!)k+1$, com $k=1,\ldots,n$, são dois a dois primos entre si. Use isto para concluir que existem pelo menos $n$ números primos menores do que ou iguais a $(n!)n + 1$ e que, portanto, existem infinitos números primos.

Exercício 6. Seja $\alpha(p,n)$ a maior potência de $p$ que divide $n!$.
(a) Mostre que $$\alpha(p,n) = \Big\lfloor \frac{n}{p} \Big\rfloor + \Big\lfloor \frac{n}{p^2} \Big\rfloor + \Big\lfloor \frac{n}{p^3} \Big\rfloor + \cdots $$ Esta expressão é conhecida como fórmula de De Polignac, mas alguns autores atribuem esta identidade a Legendre.
(b)  Mostre que $\alpha(p,n) < \frac{n}{p-1} \leq n$.
(c) (Chebysheff)  Verifique que
$$ \sum_{p\leq n} \frac{\log{p}}{p-1}  \geq \sum_{p\leq n} \alpha(p,n) \frac{\log{p}}{n} = \frac{\log{n!}}{n} >\log{n} -1,$$
onde o somatório acima percorre o conjunto dos números primos $p\leq n$. Portanto, para $n\to\infty$, temos que
$$ \sum_{p \text{ primo}} \frac{\log{p}}{p-1} = \infty.$$
Em particular, devem existir infinitos primos.
(d) (Whang) Temos que
$$n! = \prod_{p \text{ primo}} p^{\alpha(p,n)}.$$ Mostre que se existisse apenas uma quantidade finita de números primos, então
$$\lim_{n\to\infty} \frac{ \left(\prod_{p \text{ primo}} p\right)^{n}}{n!} = 0.$$ Contudo, use o item (b) para concluir que o limite acima não pode ocorrer.

Matando uma mosca com várias balas de canhão.

Podemos provar a infinitude do números primos usando alguns resultados bem mais fortes. Mas, em geral, tais resultados não são fáceis de provar. Vou listar aqui alguns.

Teorema 1 (Teorema dos Números Primos). Seja $\pi(x)$ a quantidade de números primos menores do que ou iguais a $x$. Temos que $$\lim_{x\to\infty} \frac{\pi(x)}{x/\ln(x)} = 1.$$

Em particular, se tivéssemos uma quantidade finita de números primos, então $\pi(x)$ seria limitada e o limite acima iria para zero.

Teorema 2 (Postulado de Bertrand). Para cada $n\in\mathbb{N}$, existe algum número primo $p$ com $n<p \leq 2n$.

Em particular, podemos determinar uma sequência de números primos $p_1 < p_2 < p_3 \cdots$ tais que $$ n < p_1 \leq 2n < p_2 \leq 4n < p_2 \leq 8n <\cdots$$

Teorema 3 (Dirichlet). Se $a$ e $b$ são números naturais primos entre si, então existem infinitos números primos da forma $an+b$, onde $n$ é um número natural.

Para $(a,b)\in\{(4,1),(4,3),(6,5)\}$, não é tão difícil verificar que existem infinitos primos da forma $an+b$ (veja este post).

Teorema 4 (Green & Tao). A sequência dos números primos $p_1 < p_2 < \cdots $ contém progressões aritméticas arbitrariamente longas.

Em outras palavras, para qualquer número natural $n$, podemos encontrar uma progressão aritmética de tamanho $n$ formada somente por números primos. Observe que é impossível obtermos tal progressão aritmética de tamanho infinito.

Teorema 5 (Vinogradov). Todo número ímpar suficientemente grande pode ser escrito como soma de três números primos.

O "suficientemente grande" no teorema de Vinogradov pode ser entendido como um número maior do que $3^{3^{15}}$.  Em particular, o conjunto dos números primos é infinito, pois do contrário, teríamos apenas um número finito de números ímpares maiores do que $3^{3^{15}}$ (a quantidade de números que podem ser escrito como soma de três elementos de um conjunto de $n$ elementos é no máximo $\binom{n}{3}$).


Notas:

i. Apesar da prova 1 ser atribuída a Euclides, na verdade foi Hardy quem a elaborou da maneira que está exposta. Mas trata-se apenas de uma maneira de reescrever a ideia original de Euclides que pode ser encontrada n'Os Elementos (livro IX, proposição 20).

ii. O fato da série do recíprocos dos números primos divergir, como vimos na prova de Erdős (e que Euler já sabia), está historicamente relacionado ao teorema de Green & Tao. De fato, em 1976, Erdős & Turán conjecturam que

Se $A\subset\mathbb{N}$ é tal que $$ \sum_{n\in A} \frac{1}{n} = \infty,$$ então $A$ contém progressões aritméticas de qualquer tamanho.

O teorema de Green & Tao (demonstrado em 2004) mostra que quando $A$ é o conjunto dos números primos, a conjectura é verdadeira. Contudo esta conjectura está completamente em aberto. Não se sabe nem se tais conjuntos devem conter progressões aritméticas de comprimento 3 (veja [4] para mais detalhes). Neste ponto, gostaria de oferecer como um exercício o fato de que a recíproca da conjectura é falsa:

Exercício 7. Dê um exemplo de um conjunto $A\subseteq\mathbb{N}$ que contém progressões aritméticas de qualquer tamanho, mas que $$ \sum_{n\in A} \frac{1}{n} < \infty.$$

Poste a sua solução nos comentários.  Por hoje, fico por aqui. Até a próxima! ☺

Referências.
[1] Martin Aigner, Günter M. Ziegler, Karl H. Hofmann. Proofs from THE BOOK. Springer, 4th ed. 2009.

[2] Juan Pablo Pinasco. http://www.cs.umb.edu/~eb/458/final/pinasco

[3] Paulo Ribenboim. Números primos: mistérios e recordes. Coleção Matemática Universitária. IMPA, 2001.

[4] Alexander Arbieto, Carlos Matheus, Carlos Gustavo Moreira. Aspectos Ergódicos da Teoria dos Números. 26º Colóquio Brasileiro de Matemática. IMPA, 2007.