domingo, 5 de dezembro de 2010

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 22n +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 22n +1 tinham obrigatoriamente uma determinada forma, o que lhe permitiu constatar que

225 +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 A3n é 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 2p-1 é igualmente um número primo. Na realidade enganou-se ligeiramente nos cálculos, uma vez que, sabe-se hoje, 2p-1 não é primo para p=67 nem para p=257. Por outro lado, 2p-1 é primo para p=61, 89 e 107. Seja como for, tem-se vindo a verificar que muitos dos números da forma 2p-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 243112609-1 é primo. Quantos algarismos tem este número? Basta calcularmos o seguinte logaritmo de base 10:

log( 243112609)=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.

4 comentários:

  1. Eu estou fora da corrida, porque sou um zero a Matemática. JCN

    ResponderEliminar
  2. Estou a acabar o meu curso de teoria de números e vou falar hoje de Mersenne, da sua lista e dos seus primos. Há coincidências...

    ResponderEliminar
  3. Na Aritmética Racional de J. Calado, antigo 7.º ano do Liceu, aparece, logo no início do capítulo Números Primos, a seguinte condição necessária para que um natural seja primo: todo o número primo p é da forma p = 4n + 1 ou p = 4n - 1, e propõe como exercício a demonstração de que qualquer primo p > 3 é da forma p = 6n + 1 ou p = 6n - 1, atendendo a que 6n, 6n +/- 2 e 6n +/- 3 não são primos. Facilmente se generaliza a p = 30n + i ou p = 30n - i, com i = 1, 7, 11, 13.

    O programa Proth.exe (*), que já utilizei, criado por Yves Gallot, gera números primos da forma p = k2^n + 1 (k ímpar); usa uma condição suficiente, o teorema de Proth, cujo enunciado é o seguinte: sejam p = k2^n + 1, k < 2^n e k ímpar. Se existir um inteiro a tal que a^((p-1)/2) = -1 (mod p), então p é primo.

    (*)http://primes.utm.edu/programs/gallot/

    Américo Tavares

    ResponderEliminar
  4. Coincidência por coincidência, tratando-se de números, aqui vai outra, a (des)propósito ou fora de contexto propriamente dito:

    SETE-ESTRELO

    Os números possuem, desde logo,
    uma certa magia; só que não
    batem certo comigo quando jogo
    no totoloto ou bingo de salão.

    Há números e números: nem todos
    têm o mesmo carisma, certamente,
    sem para nada depender dos modos
    de como os interpreta a nossa mente.

    Detesto o nove; o três, vou tolerando;
    o treze dá-me sorte, pois foi quando
    na vida me enlacei com meu amor.

    O número, porém, com mais pendor
    para o sucesso... deve ser o sete,
    pois até nas estrelas se repete!

    JOÃO DE CASTRO NUNES

    ResponderEliminar

1) Identifique-se com o seu verdadeiro nome.
2) Seja respeitoso e cordial, ainda que crítico. Argumente e pense com profundidade e seriedade e não como quem "manda bocas".
3) São bem-vindas objecções, correcções factuais, contra-exemplos e discordâncias.

Que sei eu do teu sorriso, Do teu sorriso tão sincero?! Que sei eu do que quero, Do que quero e preciso?! Com desespero, queria Qu...