ALGUMAS PROPRIEDADES

• Um número inteiro positivo p, diferente de 1, é primo se não puder ser decomposto em fatores p=ab, nenhum dos quais sendo 1 ou -1.
• Se p é um número primo e p dividir o produto dos inteiros ab, então p divide a ou p divide b. Esta proposição é conhecida como lemma de Euclides.
• Se p é primo e a um número inteiro qualquer, então a^p - a é divisível por p. Este é o Pequeno Teorema de Fermat. Por exemplo, 6³ - 6 = 210 e 210 é divisível por 3. O interessante é que, se a potência não for um número primo, esta afirmação não necessariamente se confirma.
• Se p é um número primo diferente de 2 e 5, 1/p é sempre uma dízima periódica com um período p-1 ou um divisor de p-1. Neste caso, também entra o Pequeno Teorema de Fermat. Por exemplo, 1/7 = 0.142857 142857..., uma dízima periódica com um período de seis algarismos (142857).
• No caso da propriedade anterior, se trocarmos a base numérica decimal para outra qualquer q, se p não for um fator primo de q, a propriedade se mantém.
• Um número inteiro p > 1 é primo se, e somente se o fatorial (p - 1)! + 1 for divisível por p. Este é o Teorema de Wilson, e o inverso também é verdadeiro. Por exemplo, (5 - 1)! + 1 = (4x3x2x1) + 1 = 24 + 1 = 25. Como 25/5 = 0, então 5 é um número primo. Por outro lado, (4 - 1)! + 1 = (3x2x1) + 1 = 6 + 1 = 7. Como 7/4 = 1.75 (não é uma divisão exata), então 4 não é um número primo.
• O Postulado de Bertrand diz que, se n é um número inteiro positivo, então sempre existe um número primo p com n < p <= 2n. Por exemplo, se n = 4, então 2n = 8. No intervalo entre 4 e 8 sempre existe um número primo que, no caso, é 5.
• Para cada um dos números primos p > 2 existe sempre um número natural n de modo que p = 4n ± 1. Por exemplo, se p = 13, então existe um número n de modo que p = 4n + 1 ou que p = 4n - 1. Neste caso, n = 3 pois 13 = 4 x 3 + 1 = 12 + 1 = 13.
• Da mesma forma, para cada número primo p > 3 existe sempre um número natural n de modo que p = 6n ± 1.

É possível gerar números primos?

Existem infinitos números primos porém, até hoje, não existe uma única fórmula capaz de gerar números primos. Podemos apenas constatar se determinado número é primo ou não, ou seja, determinar a primalidade de um número.

TESTES E PROVAS DE PRIMALIDADE

A comprovação da primalidade é uma tarefa bem mais complicada do que geralmente se acredita. Tanto é que existem inúmeros testes e métodos de prova, aplicáveis de acordo com situações específicas.

À primeira vista, a importância do assunto parece ser secundária. Acontece que os números primos são de extrema importância em várias áreas, especialmente na criptologia. Se não forem corretamente identificados, tanto a criptografia quanto a criptoanálise perdem em qualidade.

Aliás, este assunto já custou muito suor e lágrimas a muitos matemáticos. É por isso que existe um texto dedicado exclusivamente à primalidade.

TIPOS DE NÚMEROS PRIMOS

Existem alguns tipos especiais de números primos, dos quais os mais conhecidos são:

• Primos de Mersenne: têm a forma 2ⁿ - 1. Observe que os últimos maiores primos encontrados são deste tipo. Isto se deve ao fato de que existe um teste de primalidade muito eficiente para este tipo de primo, o teste de Lucas-Lehmer para Primos Mersenne.
• Primos de Fermat: têm a forma 2²ⁿ + 1.
• Primos Sophie Germain: são os números primos p onde 2p + 1 também é um número primo.
• Primos de Wieferich: são números primos p onde p² divide 2^{p - 1} - 1. Foram descritos por Wieferich em 1909 e existem apenas dois conhecidos: 1093 e 3511.
• Primos de Wilson: são os primos p onde p² divide (p - 1)! + 1. Os únicos conhecidos são 5, 13 e 563.
• Primos Fatoriais: têm a forma n! ± 1. n! - 1 é primo para n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, ... e n! + 1 é primo para n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, ...

OS MAIORES NÚMEROS PRIMOS CONHECIDOS

ONDE ENCONTRAR NÚMEROS PRIMOS ENORMES

Para encontrar listas sempre atualizadas com os maiores números primos, visite o site da GIMPS - Great Internet Mersenne Prime Search, iniciado por Woltman no início de 1996.

Os números estão classificados por tipo de primo, o site está sempre atualizado e oferece um mundo de informações a respeito de números primos.

De acordo com o número de dígitos, os primos receberam nomes especiais:

Primos titânicos

Nos anos 80, Samuel Yates iniciou uma lista dos "Maiores Primos Conhecidos" e criou o nome primo titânico para designar qualquer número primo com 1.000 ou mais dígitos. Denominou também de titãs aqueles que provaram a primalidade destes números.

Hoje em dia, uma infinidade de primos titânicos são conhecidos. Entretanto, na época em que Yates definiu os primos titânicos, tinha-se conhecimento de apenas alguns poucos.

Primos gigantes

Cerca de dez anos mais tarde, Yates designou como primo gigante todo número primo que possuísse 10.000 ou mais dígitos. Nos anos 90 estes primos eram bastante raros. Atualmente, vários deles são conhecidos.

Megaprimos

Megaprimos são números primos que possuem no mínimo um milhão de dígitos. Vários são conhecidos (quando pesquisei pela primeira vez em 2002, existiam apenas dois).

APLICAÇÕES DOS NÚMEROS PRIMOS

Números primos extremamente grandes, maiores do que 10¹⁰⁰, são usados em vários algoritmos de criptografia de chave pública. Também são usados para tabelas hash e geradores de números pseudorandômicos.

NÚMEROS PRIMOS ENTRE SI

Dois números inteiros são ditos primos entre si quando não existir um divisor maior do que 1 que divida ambos. Isto significa que o máximo divisor comum (ou MDC) dos primos entre si é igual a 1.

Por exemplo, 12 e 13 são primos entre si; porém, 12 e 14 não são, porque ambos são divísiveis por 2. Na Caixa de Ferramentas da Escolinha existe uma {vicki_il}ferramenta para calcular o MDC@88@72{/vicki_il} on line. Experimente!

Um conjunto de números inteiros é chamado de mutuamente primo se não existir um inteiro que divida todos os elementos. Por exemplo, os inteiros 30, 42, 70 e 105 são mutuamente primos. Entretanto, aos pares, não são primos entre si.

Esta definição é transferida para outras áreas. Por exemplo, dois polinômios com coeficientes inteiros são primos entre si se não houver um polinômio não-constante que divida ambos.

LISTAS DE NÚMEROS PRIMOS

No site The Prime Pages você encontra várias listas de números primos para download: os primeiros 1.000, os primeiros 10.000, os primeiros 100.000, os primeiros 5.800.000 e os primeiros 98 milhões de primos!