A demonstração de Euclides sobre a existência de infinitos números primos

O grande matemático Húngaro George Pólya $(1887 – 1985)$, recomendava um jeito divertido de se habituar aos fundamentos da matemática e de passar o tempo numa sala de espera de aeroporto ou de consultório médico: relembrar uma prova matemática já conhecida.

Vamos ver aqui, em notação moderna, a demonstração de Euclides sobre a existência de infinitos números primos, há cerca de $300$ anos antes de Cristo, em sua obra Os Elementos.

 [GIMPS: Great Internet Mersenne Prime Search]

Números primos são maiores do que $1$ e só tem dois divisores: eles mesmos e o $1$. Por exemplo, o $19$ é primo, já o $60$ não é, pois é divisível por $12$ números inteiros.

Suponha um conjunto $A$ de número primos quaisquer:
$$\begin{equation*} A={p_1, p_2, p_3, \cdots , p_n} \end{equation*}$$
Suponha que o número $n$ seja o produto de todos os números primos do conjunto $A$:
$$\begin{equation*} n = p_1 \cdot p_2 \cdot p_3 \cdot \cdots \cdot p_n \end{equation*}$$
Suponha o número $q$ composto pelo número $n$ mais $1$:
$$\begin{equation*} q = n+1 \end{equation*}$$
Se $q$ é um número primo, então existe um número primo fora do conjunto $A$. Se $q$ não é um número primo, então $q$ é divisível por um número primo $P_K$, já que todo número composto pode ser reduzido a um produto de números primos. Por exemplo:
$$\begin{equation*} 69 = 2^2 \cdot 3 \cdot 5 \end{equation*}$$
Se todo número composto é produto de números primos, então é divisível por qualquer um deles. Euclides disse que $P_K$ não pode estar dentro do conjunto $A$. Se estivesse, $P_K$ seria divisor de $n$ e de $q$ (que é $n + 1$).

Supondo que $P_K$ fosse divisor de $n$ e de $q$, teríamos:
$$\begin{gather} q = n+1\\ \frac{n}{P_K} = i_1 \Longrightarrow n = P_K \cdot i_1\\ \frac{q}{P_K} = i_2 \Longrightarrow q = P_K \cdot i_2 \end{gather}$$
Nas relações $(2)$ e $(3)$, $i_1$ e $i_2$ são números inteiros e distintos um do outro. Substituindo $(1)$ na relação $(3)$, obtemos:
$$\begin{equation} n+1 = P_K \cdot i_2 \end{equation}$$
E agora, substituímos $(2)$ na relação $(4)$:
$$\begin{equation*} (P_K \cdot i_1) + 1 = P_K \cdot i_2\\ \ \\ i_2 = \frac{P_K \cdot i_1}{P_K} + \frac{1}{P_K} \end{equation*}$$
$$\begin{equation} i_2 = i_1 + \frac{1}{P_K} \end{equation}$$
Se $q$ e $n$ são divisíveis por $P_K$, então $n$ dividido por $P_K$ dará o número inteiro $i_1$ e $q$ dividido por $P_K$ dará o número inteiro $i_2$. A relação $(5)$ diz que, para que o número $i_2$ seja inteiro é preciso que $1$ também seja divisível por $P_K$. Mas $1$ não é divisível por nenhum número primo, somente é divisível por si mesmo, caindo numa contradição.

Se $q$ não é um número primo, então, obrigatoriamente, $P_K$ está fora do conjunto $A$. A prova vale para qualquer conjunto de números primos, por mais completo que aparente ser: sempre haverá um número primo que não estará dentro do conjunto. Portanto, há infinitos números primos.

Poucas pessoas sabem de cor os números primos entre $1$ e $100$, e menos pessoas ainda sabem que o maior número primo atualmente conhecido foi descoberto em janeiro de $2013$ e possui $17$ milhões de algarismos:
$$\begin{equation*} 2^{57.885.161}-1 \end{equation*}$$
Mas mesmo sabendo tão pouco, graças a Euclides, podemos ter a certeza de que existem infinitos número primos

Veja mais:

Os Elementos de Euclides
Um Diamante em Números
Dirichlet e os Números Primos de uma Progressão Aritmética
Construindo uma Sequência de Números Não-Primos