A DISTRIBUIÇÃO DOS NÚMEROS PRIMOS E O CRIVO DE ERATÓSTHENES

Sabemos que existe um número infinito de números primos e que todo número inteiro, diferente de zero, se expressa como um produto de números primos. O número 12 se expressa como 2².3, o produto dos primos 2, 2 e 3. Como podemos saber se um número é primo? Será que existe um algoritmo, ou seja, um processo com um número finito de passos para decidirmos se um número é primo ou composto como o 12?

Essa questão já apaixonava a mente dos matemáticos gregos da antiguidade clássica e a resposta é positiva. Se quisermos saber se o inteiro positivo n >1 é primo, basta verificar se n é divisível por inteiros m menores que n. Contudo, essa idéia pode ser refinada, pois se demonstra que é suficiente verificar a divisibilidade de n pelos primos menores ou iguais a Ön. Ou seja, afirmamos que, se n é não é um número primo, então existe um primo p tal que p divide n  e p <= Ön. De fato, como estamos assumindo que n não é um número primo, n é então um número composto e, portanto, pode ser decomposto como n = ab. Se a > Ön e b > Ön, então n = ab > (Ön) (Ön) = n, uma contradição. Portanto, temos  a <= Ön e b <= Ön, e todo primo p que divide a satisfaz p <= a <= Ön.  Assim, os inteiros primos x, tais que x <= Ön, são os únicos que precisamos testar para acharmos os divisores de n. Ou seja,  basta dividirmos n por 2, 3, 5, ... , até encontrarmos o maior inteiro menor que Ön.

Por exemplo, gostaríamos de saber se o número 107 é primo. A raiz quadrada de 107 está entre 10 e 11, isto é, 10 < Ö107 < 11. Então, testamos se 107 é divisível por 2, 3, 5, 7. Mas 107 não é divisível por esses primos. Concluímos que o número 107 é primo. Por outro lado, o mesmo processo nos permite determinar os fatores primos de um número composto. Como um outro exemplo, se n = 319, então sua raiz quadrada Ö319 está entre 17 e 18 e, portanto, testamos sua divisibilidade pelos primos menores ou iguais a 17. Constatamos que 319 = 11.29, isto é, 319 é o produto de 11 por 29.  Para decompor 29 em fatores primos, testamos a sua divisibilidade pelos primos menores ou iguais a 5, pois a raiz quadrada de 29 está entre 5 e 6. Como 29 não é divisível por 2, 3 e 5, concluímos que 29 é primo e, portanto, 319 = 11.29 é a decomposição de 319 em fatores primos.

Observemos que esse algoritmo é baseado na divisão e, apesar de o algoritmo funcionar, se considerarmos números altos teremos de empreender um número enorme de divisões, o que consumiria muito tempo. O matemático Eratóstenes de Cirene, contemporâneo de Arquimedes e Aristarco, autor do mais célebre cálculo da Antiguidade para o raio da Terra, desenvolveu um método sistemático para obtenção dos primos menores que um dado número, utilizando a  multiplicação ao invés de a operação de divisão, o que torna o algoritmo mais fácil de ser implementado. Esse algoritmo é conhecido como crivo de Eratóstenes, ou método do crivo. Eratóstenes nasceu em 276 a.C., faleceu em 196 a.C., estudou filosofia em Atenas e foi diretor da famosa biblioteca de Alexandria, além de ser um eminente matemático, geógrafo, historiador, filólogo e poeta. O crivo de Eratóstenes determina todos os números primos inferiores a um certo número x dado. Portanto, ele determina os fatores primos de números compostos inferiores a x.

Observemos que todo número composto n possui um divisor menor ou igual à sua raiz quadrada Ön. Isso sugere um procedimento para se construir a lista de todos os números primos que não excedem um número inteiro x, se os primos menores que Öx já são conhecidos. Consideremos os inteiros, de 2 até x, listados em ordem crescente. Vamos manter os primos de 2, 3, 5, ..., até Öx, e descartar todos os seus múltiplos.

Em geral, como removemos os múltiplos de algum primo p_r dessa lista, o primeiro inteiro remanescente, maior que p_r, também é um número primo, digamos p_r+1. De fato, caso contrário ele seria divisível por algum primo menor (na verdade, menor que sua raiz quadrada) e já teria sido removido. Observe também que não precisamos nos preocupar com os inteiros menores que (p_r+1)², pois os números compostos menores que (p_r+1)² já foram removidos, pois todos possuíam um fator primo menor que p_r+1. Sendo assim, é suficiente iniciar-se cada etapa removendo os múltiplos de p_r+1 e descartando (p_r+1)².

Como exemplo, vamos determinar todos os números primos inferiores a 23 utilizando o método do crivo. Na lista abaixo, a representação do número em negrito significa que ele foi descartado em uma etapa do algoritmo. Por exemplo, 6 é descartado por ser múltiplo do primo 2.

Temos: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23. Portanto 2, 3, 5, 7, 11, 13, 17,19 são os inteiros primos menores que 23.

O método do crivo é eficiente para se obter uma lista dos primos menores que um inteiro não muito alto e, desde a época de Eratóstenes, o método tem sido utilizado para estimar o número de primos em um intervalo. Contudo, se tentarmos obter uma lista de inteiros que foram descartados, para se obter uma fórmula para o número exato, ou aproximado, de primos p x, teremos sérias dificuldades. O método do crivo tem sofrido uma série de aperfeiçoamentos ao longo do tempo. Os matemáticos Brun, Rademacher, Meissel, e especialmente Selberg, generalizaram o método do Crivo e, dessa forma, muitos problemas clássicos da Teoria dos Números foram reestudados com sucesso.

Dois números primos se dizem primos gêmeos se a diferença entre ambos é 2. Alguns exemplos de pares de primos gêmeos são: 3 e 5, 5 e 7, 11 e 13, 17 e 29, 29 e 31, 41 e 43. Os estudiosos de Teoria dos Números conjeturam, mas não sabem demonstrar, que existem infinitos primos gêmeos. O matemático norueguês Brun, em 1919, desenvolveu o método do crivo duplo e conseguiu algumas estimativas quanto ao número de primos gêmeos.

Em 1950 o matemático norueguês A. Selberg ganhou  a Medalha Fields (a maior distinção para um matemático), por ter desenvolvido um método extraordinariamente eficiente de estimar a distribuição dos números primos. Essa premiação representa um marco, pois foi a primeira vez que um matemático ganhou uma Medalha Fields com um trabalho em Teoria dos Números. Selberg obteve estimativas muito mais precisas  utilizando seu refinamento do método do crivo e assim resolveu muitos problemas clássicos em Teoria dos Números. Selberg deu uma demonstração elementar da lei assintótica da distribuição dos números primos, ou seja, do Teorema do Número Primo. Os matemáticos Hadamard e de la Vallée-Poussin deram, em 1897, a primeira demonstração desse teorema utilizando análise matemática, mais precisamente,  Teoria das Funções Complexas. O Teorema do Número Primo avalia a freqüência de ocorrência dos números primos, em outras palavras, a velocidade de crescimento da quantidade de números primos na seqüência dos números inteiros positivos. Graças a Atle Selberg e Paul Erdös foi possível obter-se uma demonstração do Teorema do Número Primo, completamente baseada em estimativas, sem a utilização de Análise Complexa. As investigações de Selberg em Teoria Analítica dos Números facilitaram avanços em uma série de espinhosos problemas e revelou elos inusitados entre a Teoria dos Números e outras áreas da Matemática. Por exemplo: teoria dos grupos discretos e formas automórficas, representações de grupos de Lie semi-simples, a teoria da função Zeta de Riemann e muitas outras.