Números primos: de Euclides ao GIMPS

Sabe-se desde os Elementos de Euclides (300 a.c.) que existem infinitos números primos. Mas descobrir uma fórmula simples que os forneça de forma sistemática é um dos Santos Graals da Matemática, e as muitas tentativas falhadas de o alcançar criaram, ao longo dos séculos, um verdadeiro folklore em torno deste problema.

Em 1772, Leonard Euler observava que f(n)=n²+n+41 é, para qualquer inteiro n entre 0 e 39, um número primo. No entanto, f(40)=1681=41x41 e f(41)=1763=41x43 não o são. Na realidade, é fácil demonstrar que não existe nenhuma função polinomial não constante de coeficientes inteiros que apenas assuma valores primos.

Uma outra fórmula famosa deve-se a Pierre de Fermat, que em 1640 afirmava que todos os números da forma 2²ⁿ +1 são primos. De facto, para n=0,1,2,3,4 obtêm-se cinco números primos: 3, 5, 17, 257 e 65537. Cerca de um século depois, Euler, um pouco agastado pelo legado matemático de Fermat, em parte especulativo e pouco rigoroso, deu-se ao trabalho de estudar o caso n=5. De forma extremamente elegante, observou que os possíveis divisores de 2²ⁿ +1 tinham obrigatoriamente uma determinada forma, o que lhe permitiu constatar que

2²⁵ +1=4 294 967 297=641x67000417,

pelo que o sexto número de Fermat não é primo. Hoje sabe-se que a fórmula proposta por Fermat não fornece qualquer número primo para valores de n entre 5 e 20, não estando afastada a hipótese de não fornecer mesmo mais nenhum para além dos cinco primeiros valores.

Em 1947, Williams Mills provava a existência de uma constante real A tal que, para todo o inteiro n, o arredondamento à unidade (por defeito) de A³ⁿ é primo. Apesar do grande interesse teórico deste resultado, este processo não tem grande utilidade para o cálculo prático de números primos, uma vez que muito pouco se sabe sobre a constante A. Calculá-la é, de um ponto de vista computacional, menos eficiente do que usar o crivo de Eratóstenes para determinar os n primeiros números primos.

Como temos então vindo a descobrir números primos cada vez maiores? Para responder a esta pergunta temos de seguir uma outra pista. No século XVII, Marin Mersenne observou que para p=2,3,5,7,13,17,19,31,67,127,257 o número 2^p-1 é igualmente um número primo. Na realidade enganou-se ligeiramente nos cálculos, uma vez que, sabe-se hoje, 2^p-1 não é primo para p=67 nem para p=257. Por outro lado, 2^p-1 é primo para p=61, 89 e 107. Seja como for, tem-se vindo a verificar que muitos dos números da forma 2^p-1, ditos números de Mersenne, são de facto números primos. Aliando alguns resultados teóricos como o teste de primalidade de Lucas-Lehmer à potência de cálculo dos computadores de hoje, foi possível determinar, em Abril de 2009 que o número 2^43112609-1 é primo. Quantos algarismos tem este número? Basta calcularmos o seguinte logaritmo de base 10:

log( 2^43112609)=43112609xlog(2)=12978188,5 (aprox).

Este primo tem portanto exactamente 12 978 189 algarismos, sejam cerca de 13000 páginas de 20 linhas e 50 caracteres cada uma! Trata-se do maior número primo conhecido hoje.

E o leitor poderá participar activamente na descoberta do próximo, e até ganhar algum dinheiro com isso! De facto, este número foi obtido no âmbito do programa Great Internet Mersenne Prime Search (GIMPS). Depois de criar gratuitamente uma conta em http://www.mersenne.org/, poderá descarregar um pequeno programa, o Prime95. Sempre que o activar, estará a emprestar um pouco da capacidade de cálculo do seu computador ao projecto, que lhe transmitirá um número de Mersenne ainda não verificado. Os números identificados como primos são depois transmitidos de volta ao servidor para verificações redundantes em várias máquinas. Assim, enquanto lê tranquilamente o De Rerum Natura, poderá ter o seu computador a trabalhar em subrotina numa aventura que dura há dois mil e quinhentos anos. Estará ainda habilitado a ganhar os seguintes prémios: 50.000 dólares para o primeiro número primo com mais de 100 milhões de algarismos e 3.000 dólares para qualquer outro actualmente desconhecido.