miniatura|class=skin-invert-image|Os números compostos podem ser organizados em retângulos, já os números primos não. Um número primo é um número natural maior que 1 que não pode ser formado pela multiplicação de outros dois naturais menores. Um número natural maior que 1 que não é primo é chamado de número composto. Por exemplo, 5 é primo porque as únicas maneiras de escrevê-lo como um produto, ou , envolvem o próprio 5. No entanto, 4 é composto porque é um produto (2 × 2) no qual ambos os números são menores que 4. Os primos são centrais na teoria dos números devido ao teorema fundamental da aritmética: todo número natural maior que 1 ou é um primo, ou pode ser fatorado como um produto de primos de maneira única, salvo pela ordem dos fatores.
A propriedade de ser primo é chamada primalidade. Um método simples, mas lento, de verificar a primalidade de um número dado , chamado de divisão por tentativa, testa se é um múltiplo de qualquer inteiro entre 2 e . Algoritmos mais rápidos incluem o teste de primalidade de Miller–Rabin, que é rápido, mas tem uma pequena chance de erro, e o teste de primalidade AKS, que sempre produz a resposta correta em tempo polinomial, mas é muito lento para ser prático. Métodos particularmente rápidos estão disponíveis para números de formas especiais, como números de Mersenne. , o maior número primo conhecido é um número primo de Mersenne com algarismos.
Há infinitos números primos, como demonstrado por Euclides por volta de 300 a.C. Não existe uma fórmula simples conhecida que distinga números primos de números compostos. No entanto, a distribuição de números primos nos números naturais em geral pode ser modelada estatisticamente. O primeiro resultado nessa direção é o teorema dos números primos, provado no final do século XIX, que afirma que a probabilidade aproximada de um número grande escolhido aleatoriamente ser primo é inversamente proporcional ao número de seus dígitos, ou seja, ao seu logaritmo.
Várias questões históricas relacionadas a números primos continuam sem solução. Estas incluem a conjectura de Goldbach, que afirma que todo número inteiro par maior que 2 pode ser expresso como a soma de dois números primos, e a conjectura dos números primos gêmeos, que diz que existem infinitos pares de números primos cuja diferença é igual a dois. Tais questões estimularam o desenvolvimento de várias áreas da teoria dos números, concentrando-se em aspectos analíticos ou algébricos dos números. Números primos são utilizados em diversos procedimentos na tecnologia da informação, como na criptografia de chave pública, que depende da dificuldade de decompor números grandes em seus fatores primos. Na álgebra abstrata, objetos que se comportam de maneira generalizada como números primos incluem elementos primos e ideais primos.
Definição e exemplos
Um número natural (1, 2, 3, 4, 5, 6 etc.) é chamado de número primo se é maior que 1 e não pode ser escrito como o produto de dois números naturais menores. Os números maiores que 1 que não são primos são chamados de números compostos. Noutras palavras, é primo se elementos não podem ser divididos em grupos menores, porém maior que apenas um, de mesma quantidade, ou não é possível organizar pontos em uma grade retangular que possui mais de um ponto de altura ou largura. Por exemplo, entre os números de 1 a 6, os números 2, 3 e 5 são primos, visto que não há nenhum outro número que os divida igualmente (sem deixar resto). 1 não é primo, visto que é especificadamente excluído da definição. e são ambos compostos.
Os divisores de um número natural são os números naturais que dividem igualmente . Todo número natural tem tanto 1 quanto ele mesmo como divisores. Se ele possuir qualquer outro divisor além desses dois, então não será primo. Isso leva a uma definição equivalente de número primo: são os números que possuem exatamente dois divisores positivos. Esses dois números são justamente 1 e ele mesmo. Como 1 possui apenas um único divisor, ele mesmo, não é primo por definição. Ainda, outra maneira de expressar a mesma coisa, é que um número é primo se é maior que um e nenhum dos números divide igualmente .
Os primeiros 25 números primos (todos os primos menores que 100) 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
Nenhum número par maior que 2 é primo, visto que tal número pode ser expresso como o produto . Portanto, Todo número primo além do 2 é um número impar. Similarmente, quando escrito no sistema decimal usual, todos os números primos maiores que 5 terminam em 1, 3, 7 ou 9. Os números que terminam com os outros dígitos são sempre compostos: um número decimal terminado nos dígitos 0, 2, 4, 6 ou 8 são pares, e os números decimais que terminam em 0 ou 5 são divisíveis por 5.
O conjunto de todos os primos é às vezes denotado pela letra (uma letra P maiúscula em negrito) ou por (uma letra P maiúscula em blackboard bold)
História right|thumb|class=skin-invert-image|upright=1.25|Terceira coluna do osso de Ishango, que contém os números primos entre 10 e 20. thumb|O Papiro de Rhind|alt=Consultar legenda.
A origem do conceito número primo é incerta, todavia, há um indício de consciência desses números demonstrado pelo osso de Ishango, um achado ósseo datado do Paleolítico Superior, no qual aparecem sinais representando os números primos entre 10 e 20, mas isso pode ser apenas uma coincidência. Outro indício pode ser observado na mesopotâmia no segundo milênio a.C., onde há tábuas contendo soluções para alguns problemas aritméticos relativos que, para serem solucionados, requerem um conhecimento de fatoração em números primos. No mesmo milênio, datado de aproximadamente 1550 a.C., o Papiro de Rhind tem expansões de frações egípcias de diferentes formas para números primos e compostos.Bruins, Evert Marie, análise em Mathematical Reviews de As expansões de números que compartilham o menor dos seus fatores são semelhantes, sugerindo que os egípcios estavam pelo menos cientes da diferença entre números primos e compostos.
No mesmo período, há indícios de que os chineses também possuíam um entendimento desses números. Aproximadamente no ano 1000 a.C., associavam características femininas aos números pares e características masculinas aos ímpares, considerando ímpares não primos, como 15, "efeminados". Eles utilizavam um método físico para a identificação de números primos: ao tentar dispor uma certa quantidade de grãos em retângulos, percebiam que números primos, como 17, somente permitiam uma disposição em linha única, enquanto números compostos, como 15, podiam ser arranjados em retângulos menores.
Entretanto, o primeiro registro sobrevivente do estudo de números primos vem dos matemáticos da Grécia Antiga, que os chamaram de (). Os Elementos de Euclides prova a infinidade dos números primos e o teorema fundamental da aritmética, e mostra como construir um número perfeito a partir de um primo de Mersenne. Outra invenção grega, o crivo de Eratóstenes, ainda é utilizado para construir listas de primos. Os séculos seguintes foram marcados por um certo desinteresse pelo estudo dos números primos, sem haver resultados relevantes neste tópico.
Por volta de 1000 d.C., o matemático islâmico Alhazém enunciou o teorema de Wilson, caracterizando os números primos como os números dividem igualmente . Ele também conjecturou que todo número perfeito par vêm da construção de Euclides usando primos de Mersenne, mas não conseguiu prová-la. Outro matemático islâmico, Ibne Albana de Marraquexe, observou que o crivo de Eratóstenes pode ser agilizado considerando apenas os divisores primos até a raiz quadrada da cota superior. Fibonacci levou as inovações dos matemáticos islâmicos à Europa. No seu livro Liber Abaci (1202), foi o primeiro a descrever a divisão por tentativa para realizar o teste de primalidade, novamente utilizando divisores somente até à raiz quadrada do número a ser realizado o teste.
Em 1640, Pierre de Fermat afirmou (sem provar) o pequeno teorema de Fermat (que posteriormente foi provado por Leibniz e Euler) e o teorema de Fermat sobre somas de dois quadrados (provado por Euler). Fermat também investigou a primalidade dos números de Fermat , e Marin Mersenne estudou os primos de Mersenne, primos da forma com primo. Christian Goldbach formulou a conjectura de Goldbach, que todo número par é a soma de primos, numa carta de 1742 para Euler. Euler provou a conjectura de Alhazém (agora chamado de ) que dizia que todo número perfeito par pode ser construído a partir de primos de Mersenne. Ele introduziu métodos da análise matemática a esta área nas suas provas da infinitude dos números primos e a divergência da série dos inversos dos primos . No início do século XIX, Legendre e Gauss conjecturaram que conforme tende a infinito, o número de primos menores que é assintótico a , onde é o logaritmo natural de . Uma pequena consequência dessa alta densidade de primos era o postulado de Bertrand, que para todo , existe pelo menos um primo entre e , provado em 1852 por Pafnuty Chebyshev.. (Prova do postulado: 371–382). Ver também: Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854 As ideias de Bernhard Riemann no seu artigo de 1859 sobre a função zeta esboçaram uma prova da conjectura de Legendre e Gauss. Apesar de a hipótese de Riemann, intimamente relacionada, ainda não tenha sido comprovada, o esboço de Riemann foi concluído em 1896 por Hadamard e de la Vallée Poussin, e agora o resultado é conhecido como o teorema dos números primos. Outro importante resultado do século XIX foi o teorema de Dirichlet sobre progressões aritméticas, que afirma que certas progressões aritméticas possuem infinitos números primos.
Diversos matemáticos trabalharam em testes de primalidade para números demasiados grandes, os quais a divisão por tentativa torna-se inviável. Alguns métodos são restritos a algum tipo específico de número, como o teste de Pépin para números de Fermat (1877), o teorema de Proth (), o teste de primalidade de Lucas–Lehmer (originalmente desenvolvido em 1878) e o teste de primalidade de Lucas generalizado. Desde 1951, todos os maiores primos conhecidos foram encontrados utilizando esses testes em computadores. A pesquisa por números primos cada vez maiores gerou interesses fora do círculo da matemática pelo Great Internet Mersenne Prime Search e outros projetos de processamento distribuído. A ideia de que os números primos tinham poucas aplicações fora da matemática pura foi desfeita na década de 1970, quando a criptografia de chave pública e o sistema de criptografia RSA foram inventados, usando números primos como base..
O aumento da importância prática dos testes de primalidade e da fatoração computadorizados levou ao desenvolvimento de métodos aprimorados capazes de lidar com um grande número de formas irrestritas. A teoria matemática também avançou com o teorema de Green–Tao (2004), que afirma a existência de progressões aritméticas comprimento arbitrário de números primos, e a prova de 2013 de Yitang Zhang de que existem intervalos entre primos de tamanho limitado.
Primalidade do um