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.

Teorema de Dirichlet.

Ontem assisti uma palestra que o professor Carlos Gustavo (Gugu), do IMPA, apresentou na minha universidade. O tema era "Números Típicos e Aproximações Diofantinas". O ponto de partida da palestra foi o famoso teorema de Dirichlet sobre aproximações diofantinas e o teorema de Hurwitz, que é uma versão mais forte do teorema de Dirichlet. Naquele momento, me lembrei de como uma das provas do teorema de Dirichlet tratava-se de uma das mais belas aplicações do princípio da casa dos pombos que eu já tinha visto. Aliás, costuma-se dizer que foi Dirichlet quem primeiro aplicou o princípio da casa dos pombos de maneira eficiente (seja lá o que isto significa).

Neste post, veremos a prova via princípio da casa dos pombos do teorema de Dirichlet:

Teorema de Dirichlet. Seja $\alpha$ um número irracional. Existem infinitos números racionais $p/q$ tais que
$$\left| \alpha - \frac{p}{q} \right| < \frac{1}{q^2}.$$

Em particular, temos que o conjunto dos números racionais $\mathbb{Q}$ é denso na reta bem como o conjunto $\mathbb{Z}[\alpha]$ dos números do tipo $m + n\alpha$, com $m,n$ inteiros, para qualquer $\alpha$ irracional (isto deverá seguir da prova do teorema).

Teorema de Monsky.

Você sabe como dividir um quadrado em dois triângulos de mesma área? Claro que sabe! Dividir um quadrado em três triângulos de mesma área também não deve ser difícil, certo? Espero que você não tenha tentado fazer isto, pois isso não só é difícil como é impossível! Tente dividir o quadrado em quatro triângulos de mesma área. Novamente, isto não parece ser desafiante. Mas tente em cinco pedaços... Em seis... Ok. Você já deve ter chegado a conclusão que em partes pares, o problema não é difícil (veja a figura abaixo), mas em partes ímpares, talvez seja impossível.

De fato, não existe maneira de dividir o quadrado numa quantidade ímpar de triângulos de mesma área. A primeira pessoa a observar isto foi Fred  Richman (1965)[1]. Ele estava preparando um exame de mestrado e queria incluir este problema, mas ele não pode resolvê-lo. Ele então propôs este problema na American Mathematical Monthly. Cinco anos depois, o matemático americano Paul Monsky (foto abaixo) publicou uma prova. Hoje, conhecemos este resultado como Teorema de Monsky.

Teorema de Monsky. Não existe maneira de particionar um quadrado em uma quantidade ímpar de triângulos todos de mesma área.

A prova deste teorema é única. Não se conhece nenhuma outra prova. O mais incrível é que a prova deste teorema de caráter geométrico reúne ideias de teoria dos números, álgebra abstrata e combinatória. De fato, uma das ferramentas chave na prova deste teorema é o conceito de valor $p$-ádico e uma versão da prova do lema de Sperner.  Neste post, veremos tal prova.

O amigo dos números.

Feliz Natal!

Pensei em publicar um post sobre o tão celebrado teorema de Natal de Fermat (Fermat's Christmas Theorem, aquele sobre primos que se escrevem como somas de quadrados). Mas esse é um teorema muito bonito e merece uma preparação de minha parte. Em troca, irei postar aqui uma entrevista da revista Ciência Hoje com o especialista em teoria dos números, Paulo Ribenboim (foto abaixo), matemático brasileiro de maior renome internacional.

Compartilhando segredos com Alice e Bob.

Alice e Bob querem compartilhar segredos entre eles. Como poderão fazer isto de maneira segura? Neste post veremos um pouco sobre criptografia e mostraremos como Teoria dos Números pode nos ajudar nessa história.

Criptografia é o campo de estudo dos métodos de transmissão de informações com segurança. Ou seja, estamos interessados em enviar mensagens de maneira segura. Dizemos que uma informação é transmitida com segurança se toda fonte não autorizada é incapazes de obter acesso à informação transmitida.

Para fins técnicos, assumiremos que uma mensagem é uma sequência numérica. Emissor é aquele que está interessado em compartilhar uma mensagem e receptor é aquele que está autorizado a ter acesso ao conteúdo da mensagem. Um interlocutor é um emissor ou um receptor. No nosso caso, Alice quer enviar uma mensagem para Bob. Portanto, iremos nos referir ao emissor como Alice e ao receptor como Bob.

Um método de encriptação é uma maneira de codificar (ou criptografar) a mensagem de tal modo que seja possível reobter a mensagem original por um processo de decodificação. Num método de encriptação, o responsável pela codificação é o emissor, o qual se usa de uma chave de codificação para codificar a mensagem; enquanto o responsável pela decodificação é o receptor, o qual usa uma chave de decodificação para decodificar a mensagem. De modo geral, tal processo se dá por meio de um algoritmo, o qual chamamos de algoritmo de encriptação ou cifra. Classicamente, existem dois tipos de cifra: o de chave simétrica (ou chave privada) e o de chave assimétrica (ou chave pública).

Sobre primos em progressões aritméticas.

É um fato bem conhecido que existem infinitos números primos. Contudo, os primos parecem possuir uma distribuição bastante aleatória. Talvez por isso é que este conjunto de números tenha se tornado tão interessante, sendo fonte de diversos problemas em teoria dos números.

Um dos problemas mais celebrados sobre os números primos é o de determinar progressões aritméticas (P.A.) contendo uma infinidade de números primos. Por exemplo, a progressão aritmética dos números ímpares, i.e., o conjunto $\{2n+1;n\in\mathbb{N}\}$, contém uma infinidade de números primos. Na verdade, apenas um único número primo não pertence a esta P.A., o número 2. Uma P.A. talvez mais interessante é aquela formada por números do tipo $4n+3$, i.e., o conjunto dos números

$$\textbf{3},\textbf{7},\textbf{11},15,\textbf{19},\textbf{23},27,\textbf{31},35,39,\textbf{43}\ldots.$$

De fato, podemos provar que este conjunto possui uma infinidade de números primos:

Proposição 1. Existem infinitos primos da forma $4n+3$, onde $n$ é um número natural.

$\sqrt{2}$ é irracional.

Todo mundo já deve conhecer a prova de que $\sqrt{2}$ é irracional. Se não, deixe eu fazê-la: suponha que $\sqrt{2}$ é racional. Então existem $a$ e $b>0$ inteiros primos entre si com $$\sqrt{2}=\frac{a}{b}.$$ Elevando esta última identidade ao quadrado e multiplicando por $b^2$, temos que $$2b^2 = a^2.$$ Logo $a^2$ é par. Como a raiz quadrada de um número par ainda é par, temos que $a$ é par. Então podemos escrever $a$ como $a = 2c$. Substituindo isto na última equação destacada, temos $$2b^2= 4c^2,$$ logo $b^2 = 2c^2$. E portanto, $b^2$ é par, logo $b$ também é. Neste ponto, chegamos num absurdo! Sim, pois concluímos que se $\sqrt{2}=\frac{a}{b}$ é de fato um número racional, então $a$ e $b$ são pares, logo 2 divide tanto $a$ quanto $b$, contradizendo o fato de $a$ e $b$ serem primos entre si.

Neste post queremos dar uma outra prova de que $\sqrt{2}$ é irracional. Mas para isto iremos provar um resultado mais forte:

Teorema. Se um número real $x$ satisfaz a equação

$$x^n + c_1x^{n-1} + \cdots + c_n = 0$$

com coeficientes inteiros, então ou $x$ é inteiro ou $x$ é irracional.

Em outras palavras, não existe racional não-inteiro que seja raiz de um polinômio mônico com coeficientes inteiros.

$e$ é irracional.

Neste post, daremos um prova rápida de que $e$ é um número irracional.

Da fórmula da expansão em séries de Taylor da função $f(x) = e^x$, sabemos que

$$ e = \sum_{k = 0}^{\infty} \frac{1}{k!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \ldots$$

Suponha que $e$ seja racional, i.e., existem $a$ e $b>0$ inteiros tais que $e = \frac{a}{b}$. Seja $n\geq b$ e considere

$$ N:= n!\left(e - \sum_{k = 0}^{n} \frac{1}{k!} \right).$$

Uma vez que $n!e$ e $\frac{n!}{k!}$ (para $0 \leq k \leq n$) são inteiros, temos que $N$ é um número inteiro positivo. Por outro lado,

$$N = n!\left(e - \sum_{k = 0}^{n} \frac{1}{k!} \right) = n!\left(\sum_{k = n+1}^{\infty} \frac{1}{k!} \right) = \sum_{k = n+1}^{\infty} \frac{n!}{k!}.$$

Dado $k>n$, seja $r = n-k$. Temos que

$$\frac{n!}{k!} = \frac{n!}{(n+r)!} = \frac{n!}{n!(n+1)(n+2)\ldots (n+r)} = \frac{1}{(n+1)(n+2)\ldots (n+r)} \leq \frac{1}{(n+1)^{r}}.$$

Daí,

$$N = \sum_{r = 1}^{\infty} \frac{n!}{(n+r)!} \leq \sum_{r=1}^{\infty} \frac{1}{(n+1)^{r}}.$$

Mas sendo o somatório no lado direito da desigualdade acima uma série geométrica, temos que

$$ \sum_{r=1}^{\infty} \frac{1}{(n+1)^{r}} = \frac{1}{n}.$$

Portanto, $N \leq \frac{1}{n}$, para todo $n\geq b \geq 1$, contradizendo o fato de $N$ ser inteiro positivo.

$\square$

Referências:

[1] Martin Aigner, Günter M. Ziegler; As porvas estão n'O LIVRO. Editora Edgard Blücher, 2002.