Número primo

Generalidades

Número primo é o número natural maior do que 1 cujos únicos divisores naturais são 1 e o próprio número.

Por exemplo, o número 2 é primo, pois admite apenas 1 e 2 como seus divisores naturais.

Também o número 3 é primo pois seus únicos divisores naturais são 1 e 3.

Contudo, o número 4 não é primo, pelo fato de admitir como divisores naturais 1, 2 e 4.

Já o número 5 também é primo, como é fácil constatar.

E assim por diante, até o infinito primo, que, naturalmente, é uma indefinição matemática.

Há uma tendência de se confundir número primo com número ímpar. São conceitos inteiramente diversos.

Excetuado o número 2 (primo singular), todos os demais números primos são ímpares. Porém a inversa não é necessariamente verdadeira, vale dizer: nem todo número ímpar é primo. Isso também é de imediata constatação.

O número 2 é, pois, o único número que é par e primo, simultanemante.

Se um número natural é maior que 1 e não é primo, diz-se que ele é composto. Os números 0 e 1 não são considerados primos nem compostos.

O conceito de número primo é muito importante na teoria dos números. Um dos resultados da teoria dos números é o Teorema Fundamental da Aritmética, que afirma que qualquer número natural pode ser escrito de forma única (desconsiderando a ordem) como um produto números primos (chamados fatores primos): este processo chama-se decomposição em fatores primos (fatoração).

Os primeiros números primos são:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...

Exemplos de decomposições:

• 4 = 2 × 2
• 6 = 2 × 3
• 8 = 2 × 2 × 2
• 9 = 3 × 3
• 10 = 2 × 5
• 472342734872390487 = 3 × 7 × 827 × 978491 × 27795571

Matemática dos números primos

Teoremas dos números primos

Sabe-se que, à medida que avançamos na seqüência dos números inteiros, os primos tornam-se cada vez mais raros. Isto levanta duas questões:

1. O conjunto dos números primos seria finito ou infinito?
2. Dado um número natural $n$, qual é a proporção de números primos entre os números menores que $n$?

A resposta à primeira questão é que o conjunto dos primos é infinito, um resultado conhecido desde a época do matemático grego Euclides. Podemos demonstrar da seguinte forma:

Suponha, por absurdo, que o número de primos seja finito e sejam $p_{1},p_{2},p_{3},...,p_{n}$ os primos. Seja $P$ o número tal que

$P$ = $\prod _{i=1}^{n}p_{i}+1$ onde $\prod$ denota o produtório.

Se $P$ é um número primo, é necessariamente diferente dos primos $p_{1},p_{2},p_{3},...,p_{n}$, pois sua divisão por qualquer um deles tem um resto de 1.

Por outro lado, se $P$ é composto, existe um número primo $q$ tal que $q\mid \ P$. Mas obviamente $q\neq \ p_{1},p_{2},...p_{n}$.Logo existe um novo número primo.

Há um novo número primo, seja $P$ primo ou composto; este processo pode ser repetido indefinidamente, logo há um número infinito de números primos.

Uma outra prova envolve considerar um número inteiro $n>1$. Temos $n+1$ que, necessariamente, é coprimo de $n$ (números coprimos são os que não têm nenhum fator comum maior do que 1). Provamos isto imaginando que a divisão do menor pelo maior tem resultado 0 e resto $n$ e do maior pelo menor tem resultado 1 e resto 1. Assim, $n(n+1)$ tem, necessariamente, ao menos dois fatores primos.

Tomemos o sucessor deste, que representamos como $n(n+1)+1$. Pelo mesmo raciocínio, ele é coprimo a $n(n+1)$. Ao multiplicar os dois números, temos $[n(n+1)]*[n+(n+1)+1]$. Como um de seus fatores tem pelo menos dois fatores primos diferentes e é coprimo ao outro, o resultado da multiplicação tem pelo menos três fatores primos distintos. Este raciocínio também pode ser infinitamente estendido.

A resposta para a segunda pergunta acima é que essa proporção é aproximadamente $1:\ln(n)$, onde $\ln$ é o logaritmo natural.

Grupos e sequências de números primos

São conhecidos dois grupos de números primos:

do tipo:

(4n+1) - podem sempre ser escritos na forma ($x^{2}+y^{2}$)

e

(4n-1) - nunca podem ser escritos na forma ($x^{2}+y^{2}$)

Tratando-se de números primos é perigoso fazer uma generalização apenas com base numa observação, não solidamente comprovada matematicamente. Vejamos o exemplo:

31, 331, 3.331, 33.331, 333.331, 3.333.331 e 33.333.331 são primos

mas

333.333.331 não é: (333.333.331 = 17 x 19.607.843)

Curiosidade: maior número primo

Atualmente o maior número primo encontrado é $2^{32.582.657}-1$ descoberto pelo time de colaboradores formado pelos doutores Curtis Cooper e Steven Boone no dia 4 de setembro de 2006, num projeto de computação distribuida pela Internet, que usa o tempo ocioso do processador de computadores pessoais, procurando por números primos específicos, do tipo $2^{p}-1$, chamados primos de Mersenne. Este último primo encontrado é o primo de Mersenne de número 44 e tem 9.808.358 dígitos.

Ligações externas

• Primos de Mersenne de maneira didática
• Prime curios at the prime pages
• The prime pages -- http://www.utm.edu/research/primes/
• MacTutor history of prime numbers
• The "PRIMES is in P" FAQ
• The first 20,000 primes (through 224737) at Wikisource
• Lista dos maiores números provavelmente primos
• The prime puzzles
• The Prime Project gera um número primo cada vez que a página é acessada
• Uma tradução para o inglês da demonstração de Euclides da infinitude dos primos
• Primes from WIMS is an online prime generator.
• Prime Factorization Worksheet generates new questions every time the page is loaded
• Prime Spiral pattern
• 12 digit primes Known 12-digit prime factors of Googolplex - 1
• An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier
• Primos de Mersenne - Os maiores primos já encontrados