Introdução

Nosso objetivo neste livro é descrever o processo utilizado para encontrar os maiores números primos conhecidos. Atualmente, os seis maiores primos conhecidos são da forma M_p = 2^p - 1para p = 3021377, 2976221, 1398269, 1257787, 859433 e 756839. Além disso, o primeiro número primo com mais de 1000000 de algarismos parece ter sido descoberto no dia 1^o de junho de 1999: este provável primo é da forma M_p para um certo valor de p > 6000000, ainda não divulgado no momento da conclusão deste livro.

Primos da forma 2^p - 1, com p primo, têm sido estudados há séculos e são conhecidos como primos de Mersenne; não é difícil demonstrar que 2^p - 1 só pode ser primo quando p é primo. Parte do interesse em primos de Mersenne deve-se à sua estreita ligação com números perfeitos. Um número perfeito é um inteiro positivo que é igual à soma de seus divisores próprios (como 6 = 1 + 2 + 3 e 28 = 1 + 2 + 4 + 7 + 14); os números perfeitos pares são precisamente os números da forma 2^p-1(2^p - 1) onde 2^p - 1 é primo (um primo de Mersenne).

Talvez o primeiro resultado não trivial sobre primos de Mersenne seja devido a Hudalricus Regius que em 1536 mostrou que 2^p - 1não precisa ser primo sempre que p for primo: $2^{11} - 1 = 2047 = 23 \cdot 89$. Em 1603, Pietro Cataldi tinha corretamente verificado a primalidade de 2¹⁷ - 1 e 2¹⁹ - 1 e afirmou (incorretamente) que 2^p - 1também era primo para p = 23, 29, 31 e 37. Em 1640, Fermat mostrou que 2²³ - 1 e 2³⁷ - 1 são compostos. Em 1644, o monge Marin Mersenne (1588-1648) afirmou por sua vez (também incorretamente) que 2^p - 1 era primo para

$$p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 \text{ e } 257$$

e composto para os demais valores de $p \le 257$. Esta afirmação demoraria séculos para ser completamente corrigida.

Em 1738, Euler mostrou que 2²⁹ - 1 é composto e em 1750, verificou que 2³¹ - 1 é primo. Lucas desenvolveu um algoritmo para testar a primalidade de números de Mersenne e em 1876 verificou que 2¹²⁷ - 1 é primo; este número permaneceria por muito tempo como o maior primo conhecido (ver [Lucas]). Só em 1947 a lista dos primos até 257 foi varrida: os valores de p nesta faixa para os quais 2^p - 1 é primo são

$$p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 \text{ e } 127.$$

O algoritmo de Lucas foi posteriormente melhorado por Lehmer para dar o seguinte critério: sejam S₀ = 4, S₁ = 4² - 2 = 14, ..., S_k+1 = S_k² - 2; dado p > 2, 2^p - 1 é primo se e somente se S_p-2 é múltiplo de 2^p - 1. Esta seqüência cresce muito rápido, mas basta fazer as contas módulo 2^p - 1: temos assim o chamado critério de Lucas-Lehmer (ver [Lehmer]).

Em 1951, computadores eletrônicos começaram a ser usados para procurar grandes números primos. Desde então foram encontrados os seguintes valores de ppara os quais M_p é primo: 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221 e 3021377. Em todos os casos foi usado o critério de Lucas-Lehmer. Os últimos três foram encontrados com a ajuda de computadores pessoais: se você tem um computador você também pode participar da busca do próximo número de Mersenne (veja as instruções em www.mersenne.org).

É interessante observar que os únicos primos de Mersenne maiores que 127 que nunca foram o maior primo conhecido em um dado momento são 2¹³-1 (descobridor anônimo, 1456), 2⁶¹-1 (Pervushin, 1883), 2⁸⁹-1 (Powers, 1911), 2¹⁰⁷-1 (Powers, 1914), 2⁴²⁵³-1(descoberto por Hurwitz em 1961 poucos minutos depois de 2⁴⁴²³-1) e 2¹¹⁰⁵⁰³-1 (Colquitt e Welsh, 1988). Veja nas tabelas no fim do capítulo 4 a lista dos maiores primos conhecidos ao longo da história.

Note que um número de Mersenne M_p é escrito na base 2 como $111\ldots 111$, com p algarismos. Uma generalização natural seriam os números escritos como $111\ldots 111$em outra base, isto é, números da forma (B^p - 1)/(B - 1), onde B é a base. É fácil ver que um tal número só pode ser primo se p for primo. No caso B = 10 estes números são conhecidos como repunits. Não se conhece um critério análogo ao de Lucas-Lehmer para testar a primalidade de números deste tipo quando B > 2. O maior primo conhecido desta forma é (1956¹⁸⁰¹ - 1)/1955, que tem apenas 5925 algarismos. Os únicos repunits conhecidos são para p = 2, 19, 23, 317, 1031e de acordo com as buscas o próximo repunit (se existir) deve ter mais de 30000 algarismos.

No primeiro capítulo veremos algumas idéias básicas de teoria dos números. Inicialmente apresentaremos a definição e as propriedades mais importantes do mdc e demonstraremos o teorema fundamental da aritmética. Depois apresentaremos a linguagem de congruências, o teorema chinês dos restos e os teoremas de Fermat, Euler e Wilson. Estudaremos a função $\varphi$ de Euler, fórmula de inversão de Möbius e bases de numeração. Veremos o teorema dos números primos (com demonstração de uma versão fraca) e comentaremos vários resultados e problemas em aberto famosos sobre primos.

O segundo capítulo, um pouco mais avançado que o primeiro, começa com um pouco de álgebra: falamos sobre corpos e polinômios. Estaremos especialmente interessados em corpos finitos e demonstraremos que em todo corpo finito existe uma raiz primitiva. Depois discutiremos a existência de soluções para a congruência $X^2 \equiv a \pmod n$ e reciprocidade quadrática.

O terceiro capítulo é de certa forma o mais importante do livro: nele discutiremos como gerar grandes primos ou testar a primalidade de grandes inteiros. Faremos inicialmente algumas considerações gerais e depois discutiremos testes de primalidade para nquando é conhecida uma fatoração de n-1 ou de n+1. Primos de Mersenne são um caso muito particular desta segunda situação. Daremos neste capítulo duas demonstrações para o critério de Lucas-Lehmer.

No quarto capítulo discutiremos aspectos computacionais de implementações de testes de primalidade, especialmente do teste de Lucas-Lehmer. Uma questão importantíssima para garantir a rapidez de uma implementação é a multiplicação rápida de inteiros grandes; discutiremos brevemente dois algoritmos: o de Karatsuba e FFT (fast Fourier transform).

Duas referências que foram muito usadas neste livro são o excelente livro de Paulo Ribenboim, Nombres premiers, mystères et records e a também excelente home page sobre primos de Chris Caldwell ¹ onde, entre outras coisas, podem ser sempre encontradas as listas atualizadas dos maiores primos conhecidos.

2^6972593 - 1 é primo

O número primo encontrado dia 1^o de junho de 1999 foi retestado e seu valor foi divulgado depois que o resto do livro já estava na gráfica. Graças à compreensão de todos, pudemos incluir esta página com o valor do primo. Este número primo tem mais de 2 milhões de algarismos.

Veja www.mersenne.org para maiores informações.

Carlos Gustavo T. de A. Moreira IMPA, Estr. D. Castorina 110 Rio de Janeiro, RJ 22460-320 gugu@impa.br, http://www.impa.br/~gugu

Nicolau C. Saldanha Depto. de Matemática, PUC-Rio R. Mq. de S. Vicente 225 Rio de Janeiro, RJ 22453-900 nicolau@mat.puc-rio.br, http://www.mat.puc-rio.br/~nicolau