Número primo

Origem: Wikipédia, a enciclopédia livre.

Número primo é um 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 3 é um número primo pois seus únicos divisores naturais são 1 e 3. 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

[editar] 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:

O conjunto dos números primos seria finito ou infinito?
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 \ne\ 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.

[editar] 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

)

(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)

[editar] 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$ , em que $p$ é primo, chamados primos de Mersenne. Este último primo encontrado é o primo de Mersenne de número 44 e tem 9.808.358 dígitos.