Matemática

Primos e Pombos

Princípio das casas dos pombos - infinitude dos números primos

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

$$f(x_1)=f(x_2)\Rightarrow (k_1,k_2,k_3)=(m_1,m_2,m_3)$$

$$\Rightarrow k_1=m_1,\;k_2=m_2,\;k_3=m_3$$

$$\Rightarrow 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 x_1=x_2$$

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

$$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\}$$

Isso mostra que $$k_1, k_2, 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 quelquer nautraul $$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.

- Provando Um Limite [dúvida De Um Leitor]
A pedido de um leitor, nesta postagem apresento solução para um problema envolvendo a noção de limite. O enunciado pede para provar a seguinte igualdade: $$ \lim_{x \rightarrow 1} \frac{x^2}{3x - 4} = -1$$ De acordo com a definição...

- Especial De Natal (solução)
Na postagem ESPECIAL DE NATAL perguntamos o que nos diz a a seguinte expressão: É isto o que veremos agora: Colocando z = 0 + 1i = 1i = i e calculando a série: Aplicando a distributiva, reordenando alguns fatores e cancelando outros:...

- Um Pouco Sobre Logaritmos E Suas Propriedades Operatórias
Na antiguidade, os babilônios foram os que mais se interessaram pela Astronomia e durante séculos enfrentaram problemas com os cálculos que eram muito trabalhosos. Os logaritmos surgiram para simplificar cálculos, já que transformam multiplicação...

- Demonstração Da Derivada Da Função Exponencial
Neste artigo, veremos como encontrar a derivada da função exponencial. Para isso utilizaremos limites e o conceito de derivada. Vamos demonstrar que, se $f(x)=e^x$, então sua derivada será $f '(x)=e^x$. Demonstração:Primeiramente, vamos provar...

- Demonstração Da Derivada Da Função Produto
A derivada de uma função pode ser representada geometricamente da seguinte maneira: Se $\Delta x$ for tão pequeno quanto quisermos, a reta que passa pelos pontos $[(x,f(x)),(x+\Delta x, f(x+\Delta x))]$, se confunde com a reta tangente no ponto $x$...

Matemática