Números primos: crivo, espiral e contagem

Números primos: crivo, espiral e contagem

Um número primo é um inteiro maior que 1 cujos únicos divisores positivos são 1 e ele mesmo. Os primeiros são 2, 3, 5, 7, 11, 13… O número 1 não é primo, e o 2 é o único primo par. Todo inteiro maior que 1 se escreve de forma única como produto de primos (o teorema fundamental da aritmética).

O crivo de Eratóstenes

Escreva os números de 2 até N. Comece pelo 2 e risque todos os seus múltiplos a partir de 4. Passe para o próximo número que sobrou, que é primo, e risque os múltiplos dele a partir do quadrado. Repita até passar de √N. O que sobrou são os primos.

Por que basta ir até √N? Se um composto n = a · b tem os dois fatores maiores que √n, então a · b > n. Logo, todo composto tem um fator primo menor ou igual a √n, e esse fator já riscou o número. Começar no quadrado do primo é a mesma ideia: os múltiplos menores, como 2p, 3p, já foram riscados por primos menores.

A aula anima os passos. Cada passo mostra o primo atual, em destaque, e os números que ele risca nesse momento.

Testar e fatorar um número

Para saber se n é primo, basta testar divisores até √n. Se nenhum divide n, ele é primo. Para fatorar, divida pelo menor primo possível enquanto der e repita com o quociente. Para 600 851 475 143, o menor fator é 71, e a fatoração completa é 71 · 839 · 1 471 · 6 857.

Esse método é simples e rápido para números de até uns quinze dígitos, mas fica inviável para números com centenas de dígitos. É justamente essa dificuldade que protege a criptografia RSA, tema de outra aula.

A espiral de Ulam

Em 1963, o matemático Stanisław Ulam, enquanto rabiscava durante uma apresentação entediante, começou a escrever os inteiros numa espiral a partir do centro. Os primos formaram alinhamentos diagonais e colunas, que não são óbvios. A aula desenha a espiral com os primos marcados.

Os alinhamentos ainda não são totalmente explicados. Polinômios como n² + n + 41 geram primos para n de 0 a 39, o que mostra por que padrões quadráticos podem aparecer.

Quantos primos existem?

Euclides demonstrou, por volta de 300 a.C., que há infinitos primos: se houvesse uma lista finita, o produto de todos eles mais 1 teria um divisor primo que não está na lista.

Os primos ficam mais raros à medida que os números crescem. O teorema dos números primos diz que a quantidade π(n) de primos até n é aproximadamente n ÷ ln n, com erro relativo que tende a zero. A aula compara as duas curvas: π(n) em linha contínua e n ÷ ln n tracejada.

Aplicações

• Criptografia: o RSA depende da dificuldade de fatorar o produto de dois primos grandes; o Diffie–Hellman usa primos grandes e a dificuldade do logaritmo discreto.
• Geradores de números pseudoaleatórios e tabelas de dispersão (hash) usam tamanhos primos para espalhar os valores.
• Códigos corretores de erro usam corpos finitos, cuja quantidade de elementos é potência de um primo.

Curiosidades

• Os maiores primos conhecidos são primos de Mersenne, da forma 2^p − 1, com milhões de dígitos; as buscas usam computação distribuída.
• 2³¹ − 1 = 2 147 483 647 é primo, e foi usado como módulo em geradores de números aleatórios clássicos.
• Goldbach escreveu a Euler em 1742 propondo que todo número par maior que 2 é soma de dois primos. Essa conjectura continua sem demonstração.