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.

Demonstração. Suponha, por contradição, que existe uma quantidade finita de primos da forma $4n+3$. Sejam $p_0 = 3,p_1,\ldots,p_r$ tais primos. Considere o número

$$ P = 4p_1 p_2 \cdots p_r +3.$$

Temos que $p_i \nmid P$, para $i = 0,1,\ldots,r$, pois do contrário, teríamos

$$ p_i \mid   4p_1 p_2 \cdots p_r +3,$$

o que para $i=0$, implica em

$$3 \mid 4p_1 p_2 \cdots p_r$$

ou, para $i\neq 0$,

$$p_i \mid 3.$$

Em qualquer dos casos, temos uma contradição. Logo  $p_i \nmid P$, para $i = 0,1,\ldots,r$.

Agora, observe que um número primo ou é da forma $4n + 1$ ou da forma $4n+3$. Seja $p$ um fator primo de $P$. Como $p$ não pode ser da forma $4n+3$, já que $p \notin \{p_0,p_1,\ldots,p_r\}$, devemos ter que $p$ é da forma $4n+1$. Então todo fator primo de $P$ é da forma $4n+1$, logo $P$ é da forma $4n+1$. Mas, pela maneira que definimos $P$, ele é claramente da forma $4n + 3$. Isto contradiz a unicidade do algoritmo da divisão. E portanto, é verdade que existem infinitos primos da forma $4n+3$. $\square$

Seguindo a mesma ideia que a demonstração acima, o leitor pode tentar provar que existem infinitos primos da forma $6n+5$. Observe que o ponto crucial na demonstração acima é que um primo ou é do tipo $4n+1$ ou é do tipo $4n+3$. Isto também ocorrerá para o caso $6n+5$, já que um primo ou é do tipo $6n+1$ ou é do tipo $6n+5$. 

Agora, com uma estratégia diferente, somos capazes de mostrar que existem infinitos primos da forma $4n+1$:

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

Demonstração. Seja $N>1$ um inteiro qualquer. Mostraremos que existe primo $p>N$ da forma $4n+1$. Seja 

$$ m = (N!)^2+1.$$

Note que $m$ é ímpar e maior do que $1$. Seja $p$ um fator primo de $m$. Nenhum dos números $2,3,\ldots,N$ dividem $m$, então $p>N$. Também temos que

$$ (N!)^2 \equiv -1 (\mathrm{mod}\; p). $$

Elevando ambos os termos da expressão acima à potência $(p-1)/2$, encontramos

$$ (N!)^{(p-1)} \equiv (-1)^{(p-1)/2} (\mathrm{mod}\; p). $$

Mas, pelo Pequeno Teorema de Fermat, 

$$ (N!)^{(p-1)} \equiv 1 \equiv (-1)^{(p-1)/2} (\mathrm{mod}\; p). $$

Como $p>2$, temos que $1 \not\equiv -1 (\mathrm{mod}\; p)$. Logo $(-1)^{(p-1)/2}=1$. Daí, temos que $(p-1)/2$ é um número par. Logo existe $n\in\mathbb{Z}$ tal que

$$\frac{p-1}{2} = 2n \Leftrightarrow  p = 4n +1.$$

Como queríamos. $\square$

Neste ponto, é natural nos perguntamos para quais $a$ e $b$ naturais existem infinitos primos da forma $an+b$. Observe que uma condição necessária para que exista pelo menos um primo da forma $an+b$ é que $\mathrm{mdc}(a,b) = 1$. De fato, se $d = \mathrm{mdc}(a,b) \neq 1$, então $a = du$ e $b = dv$, com $u,v\in\mathbb{N}$ e daí teríamos $an+b = d(un+v)$, sendo $un+v>1$. Ou seja, seríamos capazes de fatorar números do tipo $an+b$.

No ano de 1837, o matemático alemão Lejeune Dirichlet (imagem abaixo) mostrou que a condição $\mathrm{mdc}(a,b) = 1$ é também suficiente. A prova dada por Dirichlet não é elementar. Mesmo após simplificações posteriores, a prova deste resultado é ainda complicada. Por isso, não daremos aqui, mas o leitor pode encontrá-la esboçada na referência [1].

Teorema 1. (Dirichlet, 1837) 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 finalizar este post, mostraremos que o Teorema de Dirichlet é equivalente a seguinte versão mais fraca:

Teorema 2. Se $a$ e $b$ são números naturais primos entre si, então existe pelo menos um número primo da forma $an+b$, onde $n$ é um número natural.

Em outras palavras, para provar o Teorema 1, é suficiente mostrarmos a existência de um número primo da forma $an+b$, quaisquer que sejam $a$ e $b$ naturais primos entre si. Vamos a demonstração disso.

Demonstração da equivalência entre os teoremas 1 e 2. É claro que o Teorema 1 implica no Teorema 2. Mostremos, portanto, a recíproca. Suponha que o Teorema 2 seja válido. Sejam $a$ e $b$ dois quaisquer números naturas primos entre si. Podemos supor que $a\geq2$, já que o caso $a = 1$ é trivial. Seja $m$ um número natural qualquer. Mostraremos que existe um número primo $p$ da forma $an+b$ o qual é maior do que $m$. Pois bem, como $a^m$ e $b$ são primos entre si, o Teorema 2 nos diz que existe um número primo $p$ tal que $p = a^m n+b$, para algum $n$ natural. Como $a \geq 2$, temos que $a^m \geq 2^m >m$, portanto $p > m$, como queríamos. $\square$

Uma observação importante: a equivalência entre os teoremas 1 e 2 não é no sentido de que, por exemplo, se eu conseguir encontrar um primo da forma $4n+1$, então eu tenho uma infinidade de primos do tipo $4n+1$. Observe que, na prova acima, usamos o fato de que o teorema 2 garante a existência de um primo  $p$ da forma $a^m n+b$ para então garantirmos que este primo, sendo da forma $an'+b$, é maior do que $m$. 

Referências.

[1] Tom M. Apostol. Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976.

[2] Sierpinski W. Elementary Theory of Numbers. North Holland, 1988.