Primos e Pombos

O objetivo desta postagem é apresentar uma aplicação do Princípio das Casas dos Pombos.

Princípio das casas dos pombos: se $n$ pombos devem ser postos em $m$ casas, e se $n > m$, então pelo menos uma casa irá conter mais de um pombo.

Em termos matemáticos:

Princípio das casas dos pombos: se o número de elementos de um conjunto finito $X$ é maior do que o número de elementos de um outro conjunto $Y$, então uma função de $X$ em $Y$ não pode ser injetiva.

Utilizaremos este princípio para provar a infinitude dos números primos. Ou seja, demonstraremos o seguinte

Teorema: existem infinitos números primos.

O resultado acima enunciado já foi demonstrado, há mais de dois mil anos, por Euclides de Alexandria na célebre obra Os Elementos. A demonstração aqui apresentado é um pouco mais recente, data de novembro de 2012 e é devida a Dustin G. Mixon.

A rigor, demonstraremos que a quantidade de números primos não pode ser igual a três. Com isso (que parece ser uma meta bastante boba, visto que todos sabemos que existem mais do que três números primos), nosso objetivo é deixar mais clara as ideias empregadas. Esperamos, então, que após compreender o argumento o leitor generalize a demonstração (substituindo $3$ por um número finito arbitrário $n$ e fazendo as demais adaptações necessárias como, por exemplo, mantendo $k$ em vez de usar $11$).

Vamos, enfim, para a prova:

Suponha que exista apenas uma quantidade finita de números primos, digamos igual a $3$:

$$p_1<p_2<p_3$$

onde $p_1=2$. Tome um número natural $k$ tal que

$$2^k>(k+1)^3$$

Por exemplo, podemos tomar $k=11$, pois

$$2^{11}=2048>1728=(11+1)^3$$

Como escolhemos $k=11$, vamos considerar o seguinte conjunto:

$$X=\{1,2,3,...,2^{11}\}=\{1,2,3,...,2047,2048\}$$

Agora, vamos definir uma função $f$ cujo domínio seja o conjunto $X$. Para tanto, observemos que como consequência do Teorema Fundamental da Aritmética, cada inteiro positivo $x$ pode ser escrito, de forma única, como

$$x=p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}$$

onde $k_1,k_2,k_3$ são números naturais (aqui, estamos admitindo que o zero é natural). Assim, podemos definir $f:X\rightarrow \mathbb{N}^3$ colocando,

$$f(x)=f\left (p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}\right )=(k_1,k_2,k_3)\;\;\;\forall x\in X$$

Observe que $f$ é injetiva, pois se tivermos $x_1=p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}$ e $x_2=p_1^{m_1}\cdot p_2^{m_2} \cdot p_3^{m_3}$, então

$$\begin{aligned}
f(x_1)=f(x_2)\quad &\Rightarrow\quad (k_1,k_2,k_3)=(m_1,m_2,m_3)\\\\
&\Rightarrow\quad k_1=m_1,\;k_2=m_2,\;k_3=m_3\\\\
&\Rightarrow \quad p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}=p_1^{m_1}\cdot p_2^{m_2} \cdot p_3^{m_3}\\\\
&\Rightarrow\quad x_1=x_2
\end{aligned}$$
Note que, para cada $x\in X$, temos $2^{11}\geq x$ e, portanto, 

$$\log_2{2^{11}}\geq \log_2{x}$$

Além disso, para cada $i=1,2,3$, temos $p_i\geq 2$ e, portanto,

$$\log_2{p_i}\geq 1$$

Segue deste último fato que $k_i\log_2{p_i}\geq k_i$ para todos os índices $i=1,2,3$. Utilizando estas desigualdades (e as propriedades dos logaritmos) podemos escrever

$$\begin{aligned}
11&=\log_2{2^{11}}\\\\&\geq \log_2{x}\\\\&= \log_2{(p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3})}\\\\
&=\log_2{p_1^{k_1}}+\log_2{p_2^{k_2}}+\log_2{p_3^{k_3}}\\\\
&= k_1\log_2{p_1} + k_2\log_2{p_2}+k_3\log_2{p_3}\\\\
&\geq k_1+k_2+k_3\\\\&\geq\max\{k_1,k_2,k_3\}\end{aligned}$$

Isso mostra que $k_1$, $k_2$ e $k_3$ nunca são maiores do que $11$, qualquer que seja $x\in X$. Deste modo, a imagem de $X$ pela função $f$ está contida no conjunto

$$Y=\{(k_1,k_2,k_3)\in\mathbb{N}^3; \;k_1,k_2,k_3\leq 11\}$$

Isto significa que nada nos impede de tomar o contradomínio da função $f$ como sendo o conjunto $Y\subset\mathbb{R}^3$. Mas isso viola o princípio das casas dos pombos, pois não é possível acomodar $2048$ pombos em apenas $1728$ casas (ou seja, o domínio da função $f$ tem $2^{11}=2048$ elementos enquanto que sua imagem tem, no máximo, $12^3=1728$. Portanto, $f$ não poderia ser injetiva).  Logo, a quantidade de números primos não pode ser $3$. Na generalização (obtida quando argumentamos com $n$ em vez de $3$), concluímos que a quantidade não pode ser número finito algum, donde segue que existem infinitos números primos.

Desafio para o leitor: como sabemos que um número $k$ com a propriedade mencionada sempre existe? Ou seja, como sabemos que, para qualquer natural $n$, sempre existe um número natural $k$ tal que $2^k>(k+1)^n$?

Referência: Another simple proof of infinitude of primes.
Erros podem ser relatados aqui.