NÚMEROS PRIMOS

Números Primos


Números primos são os números naturais que têm apenas dois divisores diferentes: o 1 e ele mesmo.
Exemplos:
1) 2 tem apenas os divisores 1 e 2, portanto 2 é um número primo.
2) 17 tem apenas os divisores 1 e 17, portanto 17 é um número primo.
3) 10 tem os divisores 1, 2, 5 e 10, portanto 10 não é um número primo.
Observações:
=> 1 não é um número primo, porque ele tem apenas um divisor que é ele mesmo.
=> 2 é o único número primo que é par.
Os números que têm mais de dois divisores são chamados números compostos.
Exemplo: 15 tem mais de dois divisores => 15 é um número composto.
· Reconhecimento de um número primo
Para saber se um número é primo, dividimos esse número pelos números primos 2, 3, 5, 7, 11 etc. até que tenhamos:
=> ou uma divisão com resto zero e neste caso o número não é primo,
=> ou uma divisão com quociente menor que o divisor e o resto diferente de zero. Neste caso o número é primo.
Exemplos:
1) O número 161:
· não é par, portanto não é divisível por 2;
· 1+6+1 = 8, portanto não é divisível por 3;
· não termina em 0 nem em 5, portanto não é divisível por 5;
· por 7: 161 / 7 = 23, com resto zero, logo 161 é divisível por 7, e portanto não é um número primo.
2) O número 113:
· não é par, portanto não é divisível por 2;
· 1+1+3 = 5, portanto não é divisível por 3;
· não termina em 0 nem em 5, portanto não é divisível por 5;
· por 7: 113 / 7 = 16, com resto 1. O quociente (16) ainda é maior que o divisor (7).
· por 11: 113 / 11 = 10, com resto 3. O quociente (10) é menor que o divisor (11), e além disso o resto é diferente de zero (o resto vale 3), portanto 113 é um número primo.
----------------------------------------------------------------------





As informações abaixo foram extraídas do site:
http://www.mundovestibular.com.br/articles/465/1/NUMEROS-PRIMOS/Paacutegina1.html
NÚMEROS PRIMOS
Os livrões nos dizem que um NÚMERO PRIMO é um número natural maior do que 1 cujos únicos divisores positivos são 1 e ele mesmo. Todos os outros são chamados de números compostos. É preciso destacar que o número zero não é primo e nem composto.
Neste caso, um número inteiro maior do que 1 é chamado de primo se seus únicos divisores (fatores) positivos forem 1 e ele próprio. Os primeiros números primos são 2, 3, 5, 7, 11 e 13. O único número primo par é o 2, todos os outros são ímpares.
O Teorema Fundamental da Aritmética diz que todos os números inteiros positivos podem ser fatorados (divididos) em um produto único de números primos. Por exemplo, os divisores primos de 10 são 2 e 5. Isto é o mesmo que dizer que todos os números compostos são compostos por uma múltiplicação única de números primários, os números primos.
· 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 ap - a é divisível por p. Este é o Pequeno Teorema de Fermat. Por exemplo, 63 - 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.

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 2n - 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 22n + 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 p2 divide 2p - 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 p2 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
Primo Nro. de Dígitos Tipo Data Descobridor
225964951 - 1 7.816.230 Mersenne 18.02.2005 Martin Nowak
224036583 - 1 7.235.733 Mersenne 15.05.2004 Josh Findley
220996011 - 1 6.320.430 Mersenne 17.11.2003 Michael Schafer

Primo Dígitos Ano
1 361 84665536+1 402 007 2002
1 266 06265536+1 399 931 2002
5 x 21320487+1 397 507 2002
1 057 47665536+1 394 807 2002
857 67865536+1 388 847 2002
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).


As informações abaixo foram extraídas do site:
http://educacao.uol.com.br/matematica/ult1692u20.jhtm

Números primos
VEJA ALGORITMO PARA ENCONTRÁ-LOS
Maria Ângela de Camargo
*Maria Ângela de Camargo é professora de matemática do Colégio Ítaca.
Um número natural é primo se ele possui apenas dois divisores positivos e distintos. Ou seja, um número natural é primo se ele é maior que 1 e é divisível apenas por si próprio e por 1.

Um exemplo: o número 2. Ele só é divisível por ele mesmo, e por 1. O mesmo vale para 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... Como se pôde observar, com exceção do 2, todos os demais números primos são ímpares. Observe também que essa definição exclui o 1 como primo.

O matemático grego Euclides provou que os números primos eram infinitos. Problemas envolvendo números primos mantiveram ocupados quase todos os matemáticos desde a antigüidade: como saber se um número é primo ou não, ou prever a sua existência em um conjunto de números, ou ainda encontrar uma fórmula para defini-los?

Muitas dessas questões continuam sem resposta, mas Eratóstenes criou um método para descobrir os primos em uma seqüência de números naturais de 1 até n. Eratóstenes viveu em Alexandria algumas décadas depois de Euclides. Foi diretor da famosa Biblioteca de Alexandria e do Museu, enquanto acumulava uma série de outras atividades.
Algoritmo para definir números primos
O algoritmo se baseia numa "peneira": ele vai testando se um número é primo e, se for, elimina todos os seus múltiplos. Pode-se começar com um conjunto de números naturais não-nulos. Observe uma lista com os 50 primeiros:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

O menor número primo é o 2, mas qualquer outro que seja divisível por 2 não é primo, certo? Então, mantém-se o 2 e excluem-se todos os seus múltiplos,
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49

o que elimina metade da lista!
O próximo número primo é 3. Deve-se mantê-lo e excluir os múltiplos de 3, uma vez que um número múltiplo de 3 não pode ser primo:
2 3 5 7
11 13 17 19
23 25 29
31 35 37
41 43 47 49

E o 4? Quando se eliminam os múltiplos de 2, também se eliminaram os múltiplos de 4, 6, 8, e todos os números pares! É por esse motivo que o crivo é tão eficiente: ao excluir os múltiplos de um número primo, não há necessidade de verificar aqueles múltiplos.
Daí, pode-se passar ao próximo número da seqüência, que é exatamente o próximo primo, o 5. Removendo os múltiplos de 5 (a essa altura, só restam o 25 e o 35) e fazendo o mesmo com o próximo da seqüência que é o 7 (removendo apenas o 49), fica-se assim:
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47

Todos os números que sobraram na lista são primos!
Múltiplos de 11
Você poderia se perguntar se o correto não seria continuar com a checagem até chegar ao fim da lista. Uma análise mostra que esse trabalho não é necessário. Veja que os próximos na verificação e exclusão da seqüência seriam os múltiplos de 11, mas todos já foram excluídos previamente porque eram múltiplos de outro primo menor!
Observe o aspecto das últimas exclusões:
21 = 7x3 - 27 = 32x3 - 25 = 5x5 - 35 = 7x5 - 49 = 7x7
Qualquer outro número não-primo nessa seqüência deve ser da forma 11k, em que k é primo menor que 11, mas esses já foram excluídos! Então, os que sobraram são mesmo primos. Na verdade, basta calcular os números primos anteriores à raiz quadrada de n (você sabe dizer por quê?).
Divisão por tentativa
Para determinar se um certo número inteiro pequeno é primo, a divisão por tentativa funciona bem. Basta dividi-lo por todos os primos menores ou iguais à sua raiz quadrada. Se você estiver procurando por um primo gigantesco, com mais de 10.000 dígitos decimais, nunca poderia dividi-lo por todos os primos menores que a sua raiz quadrada.
Ainda assim, mesmo nesses casos a divisão por tentativa é utilizada, somente para fazer um rastreamento inicial. Fazem-se divisões por alguns milhões de primos pequenos e depois aplica-se um teste de primalidade. No caso de n ter 25 dígitos ou mais, a divisão por tentativa usando primos menores que sua raiz quadrada é impraticável. Se n tiver 200 dígitos, então a divisão por tentativa é impossível.
A mais importante utilização atual dos números primos é o reforço nos sistemas de segurança em criptografia, entre outras aplicações. Pode-se dizer que um sistema criptografado é tão mais seguro quanto maiores forem os primos utilizados na sua estrutura. A questão então passa por determinar se um número é primo ou não.
Mas por que o nome "primo"?
A palavra primo refere-se a idéia de primeiro, e sua origem está na concepção numérica da escola pitagórica, no século 5 a.C. Nessa época, os matemáticos gregos dividiam os números inteiros naturais em três classes:
· a monad (unidade, 1);
· os protói arithmói (números primos) ou asynthetói aritmói (números não compostos): aqueles que não podem ser gerados pelo produto de outros números além da unidade. 2, 3, 5, 7, 11, etc.;
· os deuterói arithmói (números compostos): aqueles que podem ser gerados pelo produto de outros números. 4 (=2x2), 6 (=2x3), 8, 10, 12, 14, etc.
A definição de Euclides para esses números reflete essa classificação:
"Número primo é aquele que só pode ser medido através da unidade."