Mostrar código-fonte de Número primo

{{multitag|mnot|rec|rev|data=julho de 2018}}
[[Imagem:Primes-vs-composites pt.svg|miniatura|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, {{nowrap|1 × 5}} ou {{nowrap|5 × 1}}, envolvem o próprio 5. No entanto, 4 é composto porque é um produto (2&nbsp;×&nbsp;2)<!-- {{nowrap}} evitado aqui para que os pop-ups de navegação o exibam --> 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 [[Fatoração|fatorado]] como um produto de primos de maneira única, [[Salvo (matemática)|salvo]] pela ordem dos fatores.

A propriedade de ser primo é chamada '''primalidade'''. Um método simples, mas lento, de [[Teste de primalidade|verificar a primalidade]] de um número dado {{mvar|n}}, chamado de divisão por tentativa, testa se {{mvar|n}} é um múltiplo de qualquer inteiro entre 2 e <math>\sqrt{n}</math>. 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. {{desde|2024|10|alt=Em outubro de 2024}}, o [[maior número primo conhecido]] é um número [[primo de Mersenne]] com {{fmtn|41024320}} [[algarismo]]s.<ref name="GIMPS-2024">{{citar web |título=GIMPS Discovers Largest Known Prime Number: 2<sup>136,279,841</sup> − 1 |url=https://www.mersenne.org/primes/?press=M136279841 |data=21 de outubro de 2024 |publicação=Mersenne Research, Inc. |acessodata=21 de outubro de 2024}}</ref><ref name="GIMPS-2018">{{citar web |título=GIMPS Project Discovers Largest Known Prime Number: 2<sup>82,589,933</sup>-1 |url=https://www.mersenne.org/primes/press/M82589933.html |data=21 de dezembro de 2018 |publicação=Mersenne Research, Inc. |acessodata=22 de dezembro de 2018 }}</ref>

Há [[Conjunto infinito|infinitos]] números primos, como [[Teorema de Euclides|demonstrado por Euclides]] por volta de 300&nbsp;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&nbsp;XIX, que afirma que a [[probabilidade]] de um número grande escolhido aleatoriamente ser primo é inversamente [[Proporcionalidade|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 [[Teoria analítica dos números|analíticos]] ou [[Teoria algébrica dos números|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 [[Elemento primo|elementos primos]] e [[Ideal primo|ideais primos]].


== Definição e exemplos ==
{{AP|Lista de números primos}}

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]].<ref>{{citar livro|título=The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996|primeiro=Anthony|último=Gardiner|local=Oxford, Reino Unido|publicado=Oxford University Press|ano=1997|isbn=978-0-19-850105-3|página=[https://archive.org/details/mathematicalolym1997gard/page/26 26]|url=https://archive.org/details/mathematicalolym1997gard|acessourl=registro|lingua=en}}</ref> Noutras palavras, {{mvar|n}} é primo se {{mvar|n}} elementos não podem ser divididos em grupos menores, porém maior que apenas um, de mesma quantidade,<ref>{{citar livro|título=Dyslexia, Dyscalculia and Mathematics: A practical guide|primeiro=Anne|último=Henderson|edição=2.ª|publicado=Routledge|ano=2014|isbn=978-1-136-63662-2|página=62|url=https://books.google.com/books?id=uy-yGVRUilMC&pg=PA62|lingua=en}}</ref> ou não é possível organizar {{mvar|n}} pontos em uma grade retangular que possui mais de um ponto de altura ou largura.<ref>{{citar livro|título=The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space|url=https://archive.org/details/giantgoldenbooko00adle|acessourl=registro |primeiro=Irving|último=Adler|publicado=Golden Press|ano=1960|página=[https://archive.org/details/giantgoldenbooko00adle/page/16 16]|oclc=6975809 |lingua=en}}</ref> Por exemplo, entre os números de 1 a 6, os números 2, 3 e 5 são primos,<ref>{{citar livro |url=https://archive.org/details/barronsmathworkb00leff_0 |acessourl=registro |página=[https://archive.org/details/barronsmathworkb00leff_0/page/360 360] |título=Math Workbook for the SAT I |primeiro=Lawrence S. |último=Leff |publicado=Barron's Educational Series |ano=2000 |isbn=978-0-7641-0768-9 |língua=en}}</ref> visto que não há nenhum outro número que os divida igualmente (sem deixar resto). 1 não é primo, pois é especificadamente excluído da definição. {{nowrap|1=4 = 2 × 2}} e {{nowrap|1=6 = 2 × 3}} são ambos compostos.

[[File:Prime number Cuisenaire rods 7.png|thumb|upright=1.2|alt=consulte a legenda|Demonstração, com hastes de Cuisenaire, que 7 é primo, pois 2, 3, 4, 5 nem 6 divide-o igualmente|esquerda]]

Os [[divisor]]es de um número natural {{mvar|n}} são os números naturais que dividem igualmente {{mvar|n}}. 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.{{sfn|Dudley|1978|loc=[https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA10 Seção 2, p. 10]}} Ainda, outra maneira de expressar a mesma coisa, é que um número {{mvar|n}} é primo se é maior que um e nenhum dos números {{math|2, 3, ... , ''n'' &minus; 1}} divide igualmente {{mvar|n}}.{{sfn|Sierpiński|1988|p=[https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA113 113]}}

Os primeiros 25 números primos (todos os primos menores que 100) são:<!--Não adicione 1 a esta lista.--><ref name=ziegler>{{citar periódico |último= Ziegler |primeiro= Günter M. |autorlink= Günter M. Ziegler |número= 4 |publicação= [[Notices of the American Mathematical Society]] |mr=2039814 |páginas=414–416 |título= The great prime number record races |volume=51 |ano= 2004 |lingua=en}}</ref>
: [[Dois|2]], [[Três|3]], [[Cinco|5]], [[Sete|7]], [[Onze|11]], [[Treze|13]], [[Dezessete|17]], [[Dezanove|19]], [[Vinte e três|23]], 29, 31, [[Trinta e sete|37]], 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 {{OEIS|id=A000040}}

Nenhum [[número par]] {{mvar|n}} maior que 2 é primo, visto que tal número pode ser expresso como o produto {{math|2 × ''n''/2}}. Portanto, Todo número primo além do 2 é um [[número impar]].<ref>{{citar livro|título=Numbers and Geometry|series=Undergraduate Texts in Mathematics|primeiro=John|último=Stillwell|autorlink=John Stillwell|publicado=Springer|ano=1997|isbn=978-0-387-98289-2|página=9|url=https://books.google.com/books?id=4elkHwVS0eUC&pg=PA9}}</ref> 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.<ref>{{citar livro |último=Sierpiński |primeiro=Wacław |autorlink=Wacław Sierpiński |local=New York |mr=0170843 |página=[https://archive.org/details/selectionproblem00sier/page/n37 40] |publicado=Macmillan |título=A Selection of Problems in the Theory of Numbers |url=https://archive.org/details/selectionproblem00sier |acessourl=limitado |ano=1964 |lingua=en}}</ref>

O [[conjunto]] de todos os primos é às vezes denotado pela letra {{math|'''P'''}} (uma letra P maiúscula em [[negrito]])<ref>{{citar livro|título=Elementary Methods in Number Theory|volume=195|series=Graduate Texts in Mathematics|contribution=Notations and Conventions|contribution-url=https://books.google.com/books?id=sE7lBwAAQBAJ&pg=PP10|primeiro=Melvyn B.|último=Nathanson|publicado=Springer|ano=2000|isbn=978-0-387-22738-2|mr=1732941|lingua=en}}</ref> ou por <math>\mathbb{P}</math> (uma letra P maiúscula em ''[[blackboard bold]]'')<ref>{{citar livro|título=The Mathematics of Infinity: A Guide to Great Ideas|volume=111|series=Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts|primeiro=Theodore G.|último=Faticoni|edição=2.ª|publicado=John Wiley & Sons|ano=2012|isbn=978-1-118-24382-4|página=44|url=https://books.google.com/books?id=I433i_ZGxRsC&pg=PA44|lingua=en}}</ref>

== História ==
[[Imagem:IshangoColumnA.png|right|thumb|upright=1.25|Terceira coluna do [[osso de Ishango]], que contém os números primos entre 10 e 20.]]
[[Imagem:Rhind Mathematical Papyrus.jpg|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 osseo datado do [[Paleolítico Superior]], no qual aparecem sinais representando os números primos entre 10 e 20,<ref>{{citar livro|último=Huylebrouck|primeiro=Dirk|título=Africa and Mathematics|capítulo=Missing Link|data=2019|capítulourl=http://dx.doi.org/10.1007/978-3-030-04037-6_9|series=Mathematics, Culture, and the Arts|páginas=153–166|local=Cham|publicado=Springer International Publishing|doi=10.1007/978-3-030-04037-6_9|isbn=978-3-030-04036-9|s2cid=239306457|acessodata=2021-10-19}}</ref> mas isso pode ser apenas uma coincidência.<ref>{{citar livro |último=Everett |primeiro=Caleb |ano=2017 |título=Numbers and the Making of Us: Counting and the Course of Human Cultures |publicado=Harvard University Press |isbn=978-0-674-50443-1 |páginas=35–36 |url=https://books.google.com/books?id=2f1aDgAAQBAJ&pg=PA35}}</ref> Outro indício pode ser observado na mesopotâmia no [[segundo milênio&nbsp;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.<ref>{{citar livro|autorlink=Otto Neugebauer |primeiro=Otto |ultimo=Neugebauer |título=The Exact Sciences In Antiquity |local=Nova Iorque, NY, EUA |editora=Dover |ano=1969 |capítulo=Babylonian Mathematics |edição=2.ª |isbn=0-486-22332-9}}</ref> No mesmo milênio, datado de aproximadamente 1550&nbsp;a.C., o [[Papiro de Rhind]] tem expansões de [[frações egípcias]] de diferentes formas para números primos e compostos.<ref>Bruins, Evert Marie, análise em ''Mathematical Reviews'' de {{citar periódico |último= Gillings |primeiro= R.J. |doi=10.1007/BF01307175 |publicação= Archive for History of Exact Sciences |mr=0497458 |páginas=291–298 |título= The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it? |volume=12 |número= 4 |ano= 1974|s2cid=121046003 }}</ref> 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.<ref>{{citar web|url=http://mathpages.com/home/kmath340/kmath340.htm|título=Egyptian Unit Fractions|website=Mathpages|acessodata=14 de janeiro de 2011|lingua=en}}</ref>

Entretanto, o primeiro registro sobrevivente do estudo de números primos vem dos [[Matemática da Grécia Antiga|matemáticos da Grécia Antiga]], que os chamaram de ''{{transl|grc|prōtos arithmòs}}'' ({{lang|grc|πρῶτος ἀριθμὸς}}). ''[[Os Elementos]]'' de [[Euclides]] prova a [[Teorema de Euclides|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]].<ref name="stillwell-2010-p40">{{citar livro|título=Mathematics and Its History|series=Undergraduate Texts in Mathematics|primeiro=John|último=Stillwell|autorlink=John Stillwell |edição=3rd |publicado=Springer |ano=2010 |isbn=978-1-4419-6052-8 |página=40 |url=https://books.google.com/books?id=V7mxZqjs5yUC&pg=PA40}}</ref> Outra invenção grega, o [[crivo de Eratóstenes]], ainda é utilizado para construir listas de primos.<ref name="pomerance-sciam">{{citar periódico |título=The Search for Prime Numbers|primeiro=Carl|último=Pomerance|autorlink=Carl Pomerance|publicação=[[Scientific American]]|volume=247|número=6|data=dezembro de 1982|páginas=136–147|jstor=24966751|doi=10.1038/scientificamerican1282-136|bibcode=1982SciAm.247f.136P}}</ref><ref name="mollin">{{citar periódico |último= Mollin |primeiro= Richard A. |doi=10.2307/3219180 |número= 1 |publicação= Mathematics Magazine |mr=2107288 |páginas=18–29 |título= A brief history of factoring and primality testing B. C. (before computers) |volume=75 |ano= 2002|jstor=3219180 }}</ref> Os séculos seguintes foram marcados por um certo desinteresse pelo estudo dos números primos, sem haver resultados relevantes neste tópico.<ref>{{MacTutor|classe=HistTopics|id=Prime_numbers|título=Prime numbers|acessodata=2024-08-07}}</ref>

Por volta de 1000&nbsp;d.C., o matemático [[Matemática islâmica|islâmico]] [[Alhazém]] enunciou o [[teorema de Wilson]], caracterizando os números primos como os números {{mvar|n}} dividem igualmente {{math|(''n'' &minus; 1)! + 1}}. 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.<ref>{{MacTutor|id=Al-Haytham|título=Abu Ali al-Hasan ibn al-Haytham}}</ref> 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.<ref name="mollin"/> [[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.<ref name="mollin"/>

Em 1640, Pierre de Fermat afirmou (sem provar) o [[pequeno teorema de Fermat]] (que posteriormente foi provado por [[Leibniz]] e [[Euler]]){{sfn|Sandifer|2007|p=[https://books.google.com/books?id=sohHs7ExOsYC&pg=PA45 45]}} e o [[teorema de Fermat sobre somas de dois quadrados]] (provado por Euler).<ref>{{citar livro |ultimo=Burton |primeiro=David M. |capítulo=Representation of Integers as Sums of Squares |titulo=Elementary Numbert Theory |local= Boston, MA, EUA |editora=Allyn and Bacon |ano=1980 |isbn=0-205-06965-7 |língua=en}}</ref> Fermat também investigou a primalidade dos [[números de Fermat]] {{math|2<sup>2<sup>''n''</sup></sup> + 1}},<ref>{{citar livro|título=How Euler Did Even More|primeiro=C. Edward|último=Sandifer|local=EUA|publicado=Mathematical Association of America|ano=2015|isbn=978-0-88385-584-3|página=42|url=https://books.google.com/books?id=3c6iBQAAQBAJ&pg=PA42|doi=10.5948/978161444519}}</ref> e [[Marin Mersenne]] estudou os [[primos de Mersenne]], primos da forma {{math|2<sup>''p''</sup> &minus; 1}} com {{mvar|p}} primo.<ref>{{citar livro|título=Elementary Number Theory with Applications|primeiro=Thomas|último=Koshy|publicado=Academic Press|ano=2002|isbn=978-0-12-421171-1|página=369|url=https://books.google.com/books?id=-9pg-4Pa19IC&pg=PA369}}</ref> [[Christian Goldbach]] formulou a [[conjectura de Goldbach]], que todo número par é a soma de primos, numa carta de 1742 para Euler.<ref>{{citar livro|título=Goldbach Conjecture|edição=2.ª|volume=4|series=Series In Pure Mathematics|primeiro=Wang|último=Yuan|local=Singapura|publicado=World Scientific|ano=2002|isbn=978-981-4487-52-8|página=21|url=https://books.google.com/books?id=g4jVCgAAQBAJ&pg=PA21|lingua=en}}</ref> Euler provou a conjectura de Alhazém (agora chamado de {{ill|en|teorema de Euclides–Euler|Euclid–Euler theorem}}) que dizia que todo número perfeito par pode ser construido a partir de primos de Mersenne.<ref name="stillwell-2010-p40"/> 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]] <math>\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\tfrac{1}{11}+\cdots</math>.<ref>{{citar livro|título=The Development of Prime Number Theory: From Euclid to Hardy and Littlewood|series=Springer Monographs in Mathematics|primeiro=Wladyslaw|último=Narkiewicz|publicado=Springer|ano=2000|isbn=978-3-540-66289-1|página=11|contribution=1.2 Sum of Reciprocals of Primes|contribution-url=https://books.google.com/books?id=VVr3EuiHU0YC&pg=PA11|lingua=en}}</ref> No início do século&nbsp;XIX, Legendre e Gauss conjecturaram que conforme {{mvar|x}} tende a infinito, o número de primos menores que {{mvar|x}} é [[Análise assintótica|assintótico]] a {{math|''x''/log&thinsp;''x''}}, onde {{math|log&thinsp;''x''}} é o [[logaritmo natural]] de {{mvar|x}}. Uma pequena consequência dessa alta densidade de primos era o [[postulado de Bertrand]], que para todo {{math|''n'' > 1}}, existe pelo menos um primo entre {{mvar|n}} e {{math|2''n''}}, provado em 1852 por [[Pafnuty Chebyshev]].<ref>{{citar periódico|primeiro=P. |último=Tchebychev |autorlink=Pafnuty Chebyshev |título=Mémoire sur les nombres premiers. |publicação=Journal de mathématiques pures et appliquées |series=Série 1 |ano=1852 |páginas=366–390 |url=http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf |língua=fr}}. (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</ref> 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 [[Jacques Hadamard|Hadamard]] e [[Charles-Jean de La Vallée Poussin|de la Vallée Poussin]], e agora o resultado é conhecido como o [[teorema dos números primos]].<ref>{{citar livro |último= Apostol |primeiro= Tom M. |autorlink= Tom M. Apostol |editor-sobrenome1= Bambah |editor-nome1= R.P. |editor-sobrenome2= Dumir |editor-nome2= V.C. |editor-sobrenome3= Hans-Gill |editor-nome3= R.J. |contribution=A centennial history of the prime number theorem |local= Basel |mr=1764793 |páginas=1–14 |publicado= Birkhäuser |series=Trends in Mathematics |título= Number Theory |contribution-url=https://books.google.com/books?id=aiDyBwAAQBAJ&pg=PA1 |ano= 2000 |lingua=en}}</ref> Outro importante resultado do século&nbsp;XIX foi o [[teorema de Dirichlet sobre progressões aritméticas]], que afirma que certas progressões aritméticas possuem infinitos números primos.<ref>{{citar livro |último= Apostol |primeiro= Tom M. |autorlink= Tom M. Apostol |contribution=7. Dirichlet's Theorem on Primes in Arithmetical Progressions |contribution-url=https://books.google.com/books?id=3yoBCAAAQBAJ&pg=PA146 |local= New York; Heidelberg |mr=0434929 |páginas=146–156 |publicado= Springer-Verlag |título= Introduction to Analytic Number Theory |ano= 1976 |lingua=en}}</ref>

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),<ref>{{citar livro|título=A History of Algorithms: From the Pebble to the Microchip|primeiro=Jean-Luc|último=Chabert|publicado=Springer|ano=2012|isbn=978-3-642-18192-4|página=261|url=https://books.google.com/books?id=XcDqCAAAQBAJ&pg=PA261|lingua=en}}</ref> o [[Primos de Proth|teorema de Proth]] ({{c.|1878}}),{{sfn|Rosen|2000|p=342}} o [[teste de primalidade de Lucas–Lehmer]] (originalmente desenvolvido em 1878) e o [[teste de primalidade de Lucas]] generalizado.<ref name="mollin"/> Desde 1951, todos os [[Maior número primo conhecido|maiores primos conhecidos]] foram encontrados utilizando esses testes em computadores.{{TagNota|Um número primo de 44 dígitos encontrado em 1951 por Aimé Ferrier com uma calculadora mecânica continua a ser o maior primo encontrado sem o auxílio de computadores eletrônicos.<ref>{{citar livro|título=The Once and Future Turing|primeiro1=S. Barry|último1=Cooper|primeiro2=Andrew|último2=Hodges|publicado=Cambridge University Press|ano=2016|isbn=978-1-107-01083-3|páginas=37–38|url=https://books.google.com/books?id=h12cCwAAQBAJ&pg=PA37}}</ref>}} 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 [[sistema de processamento distribuído|processamento distribuído]].<ref name=ziegler/>{{sfn|Rosen|2000|p=245}} A ideia de que os números primos tinham poucas aplicações fora da matemática pura{{TagNota|name="pura"|Por exemplo, Beiler escreve que o teórico dos números [[Ernst Kummer]] adorava seus números ideais, intimamente relacionados aos primos, "porque eles não haviam se sujado com nenhuma aplicação prática",<ref>{{citar livro|título=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|primeiro=Albert H.|último=Beiler|ano=1999|publicado=Dover|anooriginal=1966|isbn=978-0-486-21096-4|página=2|url=https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA2|oclc=444171535|lingua=en}}</ref> e Katz escreve que [[Edmund Landau]], conhecido por seu trabalho sobre a distribuição de primos, "detestava aplicações práticas da matemática" e, por essa razão, evitava assuntos como [[geometria]] que já haviam se mostrado úteis.<ref>{{citar periódico |último=Katz |primeiro=Shaul |doi=10.1017/S0269889704000092 |número=1–2 |publicação=Science in Context |mr=2089305 |páginas=199–234 |título=Berlin roots&nbsp;– Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem |volume=17 |ano=2004 |s2cid=145575536 |lingua=en}}</ref>}} 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.<ref name="ent-7">{{citar livro|título=Elementary Number Theory|series=Textbooks in mathematics|primeiro1=James S.|último1=Kraft|primeiro2=Lawrence C.|último2=Washington|publicado=CRC Press|ano=2014|isbn=978-1-4987-0269-0|página=7|url=https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA7|lingua=en}}</ref>

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.<ref name="pomerance-sciam"/><ref>{{citar livro|título=Secret History: The Story of Cryptology|series=Discrete Mathematics and Its Applications|primeiro=Craig P.|último=Bauer|publicado=CRC Press|ano=2013|isbn=978-1-4665-6186-1|página=468|url=https://books.google.com/books?id=EBkEGAOlCDsC&pg=PA468|lingua=en}}</ref><ref>{{citar livro|título=Old and New Unsolved Problems in Plane Geometry and Number Theory|volume=11|series=Dolciani mathematical expositions|primeiro1=Victor|último1=Klee|autorlink1=Victor Klee|primeiro2=Stan|último2=Wagon|publicado=Cambridge University Press|ano=1991|isbn=978-0-88385-315-3|página=224|url=https://books.google.com/books?id=tRdoIhHh3moC&pg=PA224|lingua=en}}</ref> 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 [[Intervalo entre primos|intervalos entre primos]] de tamanho limitado.{{sfn|Neale|2017|pp=18, 47}}

=== Primalidade do um ===

A maioria dos antigos gregos nem consideravam 1 ser um número,<ref name="crxk-34">{{harvnb|Caldwell|Reddick|Xiong|Keller|2012|loc=Artigo 12.9.8}}. Para uma seleção de citações e sobre as posições dos antigos gregos sobre a situação do 1 e 2, veja em particular pp. 3–4. Para os matemáticos islâmicos, veja p. 6.</ref><ref>{{citar livro|título=Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary|volume=39|series=Philosophia Antiqua : A Series of Monographs on Ancient Philosophy|primeiro=Leonardo|último=Tarán|publicado=Brill|ano=1981|isbn=978-90-04-06505-5|páginas=35–38|url=https://books.google.com/books?id=cUPXqSb7V1wC&pg=PA35|lingua=en}}</ref> então eles nem consideravam a sua primalidade. Alguns estudiosos da tradição grega e da romana, incluindo [[Nicômaco de Gérasa|Nicômaco]], [[Jâmblico]], [[Boécio]] e [[Cassiodoro]], consideravam os números primos como uma subdivisão dos números ímpares, então também não consideravam o 2 ser primo. No entanto, Euclides e a maioria dos outros matemáticos gregos consideravam 2 um número primo. Os [[Matemática islâmica|matemáticos islâmicos medievais]] seguiram em grande parte os gregos ao considerar que 1 não era um número.<ref name="crxk-34"/> Na Idade Média e Renascença, matemáticos começaram a tratar o 1 como um número, e alguns deles incluia-o como o primeiro número primo.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012|pp=7–13}}. Veja em particular as entradas de Stevin, Brancker, Wallis, e Prestet.</ref> Em meados do século&nbsp;XVIII, [[Christian Goldbach]] listou 1 sendo primo em sua correspondência com [[Leonhard Euler]]; porém, o próprio Euler não considerava 1 como primo.{{sfn|Caldwell|Reddick|Xiong|Keller|2012|p=15}} Ainda no século&nbsp;XIX, diversos matemáticos ainda consideravam 1 ser primo,<ref name="cx"/> e listas de números primos que incluíam 1 continuaram a ser publicadas até 1956.<ref>{{citar livro |último=Riesel |primeiro=Hans |título=Prime Numbers and Computer Methods for Factorization |publicado=Birkhäuser |local=Basel, Switzerland |isbn=978-0-8176-3743-9 |ano=1994 |página=36 |edição=2.ª |mr=1292250 |url=https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA36 |doi=10.1007/978-1-4612-0251-6 |lingua=en}}</ref><ref name="cg-bon-129-130">{{citar livro |último1=Conway |primeiro1=John Horton |autorlink1=John Conway |último2=Guy |primeiro2=Richard K. |autorlink2=Richard Kenneth Guy |título=The Book of Numbers |url=https://archive.org/details/bookofnumbers0000conw |acessourl=registro |publicado=Copernicus |local=New York |isbn=978-0-387-97993-9 |ano=1996 |páginas=[https://archive.org/details/bookofnumbers0000conw/page/129 129–130] |mr=1411676 |doi=10.1007/978-1-4612-4072-3 |lingua=en}}</ref>

Se a definição de número primo fosse alterada para incluir o 1, diversas afirmações envolvendo números precisariam ser reformuladas de uma forma mais complicada. Por exemplo, o teorema fundamental da aritmética teria que ser reescrita para em termos de fatores maiores que 1, pois todo número poderia ter múltiplas decomposições com diferentes quantidades de cópias de 1.<ref name="cx">{{citar periódico |último1=Caldwell |primeiro1=Chris K. |último2=Xiong |primeiro2=Yeng |número=9 |publicação=[[Journal of Integer Sequences]] |mr=3005530 |página=Article 12.9.7 |título=What is the smallest prime? |url=https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf |volume=15 |ano=2012}}</ref> Similarmente, o [[crivo de Eratóstenes]] não funcionaria adequadamente se 1 fosse tratado como primo, pois eliminaria todos os múltiplos de 1 (isto é, todos os outros números) e resultaria em apenas um único número 1.<ref name="cg-bon-129-130"/> Algumas outras propriedades mais técnicas dos primos também não iria funcionar para o número 1: por exemplo, as fórmulas para a [[função totiente de Euler]] ou para a [[função soma dos divisores]] são diferentes para números primos e para 1.<ref>Para a função totiente, veja {{harvnb|Sierpiński|1988|p=[https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA245 245]}}. Para a soma dos divisores, veja {{harvnb|Sandifer|2007|p=[https://books.google.com/books?id=sohHs7ExOsYC&pg=PA59 59].}}</ref> No início do século&nbsp;XX, matemáticos começaram a concordar que 1 não deveria ser listado como primo, mas sim uma categoria própria especial chamada "[[unidade (teoria dos anéis)|unidade]]".<ref name="cx"/>

== Os átomos da aritmética ==
Os gregos foram os primeiros a perceber que qualquer número natural, exceto o <math>1,</math> pode ser gerado pela [[multiplicação]] de números primos, os chamados ''"blocos de construção". ''A primeira pessoa, até onde se sabe, que produziu tabelas de números primos foi [[Eratóstenes]], no terceiro século a.C. Ele escrevia inicialmente uma lista com todos os números de ''<math>1</math> ''a ''<math>100.</math> ''Em seguida escolhia o primeiro primo, ''<math>2,</math> ''e eliminava da lista todos os seus [[múltiplos]]. Passava ao número seguinte que não fora eliminado e procedia também eliminando todos os seus múltiplos. Desta forma Eratóstenes produziu tabelas de primos, mais tarde este procedimento passou a se chamar de [[crivo de Eratóstenes]]. Observe a ilustração a seguir:

<gallery widths="554" heights="445">
File:New_Animation_Sieve_of_Eratosthenes.gif|Crivo de Eratóstenes
</gallery>
Assim obtemos: 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, ... A partir desse procedimento podemos simplificar a descobertas de primos usando o lema: Se um número natural n > 1 não é divisível por nenhum primo p tal que <math>p^2</math> ≤ n, então ele é primo. (demonstrado adiante). Este lema fornece um teste de primalidade, pois, para verificar se um dado número n é primo, basta verificar que não é divisível por nenhum p que não supere <math>\sqrt{n}.</math>

Durante o século XVII os matemáticos descobriram o que acreditavam ser um método infalível para determinar se um número <math>N</math> era primo: calcule <math>2</math> elevado a potência <math>N</math> e divida-o por <math>N,</math> se o resto for <math>2,</math> então o número será primo. Em termos da [[aritmética modular|calculadora-relógio]] de [[Gauss]], esses matemáticos estavam tentando calcular <math>2^N</math> em um relógio com <math>N</math> horas. Em 1819, o teste dos números primos foi eliminado, pois funciona para todos os números até <math>340,</math> mas falha para <math>341 = 11 \times 31.</math> Exceção descoberta com uma [[aritmética modular|calculadora-relógio]] de Gauss contendo 341 horas utilizada para simplificar a análise de um número como <math>2^{341}.</math>

=== Teoria dos números ===
{{AP|Teoria dos números}}

Sabe-se que, à medida que avançamos na sequê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 <math>n,</math> qual é a proporção de números primos entre os números menores que <math>n</math>?

* A resposta à primeira questão é que o conjunto dos primos é [[infinito]], um resultado conhecido na parte central dos ''[[Os Elementos|Elementos]]'' de [[Euclides]], que lida com as propriedades dos números. Na proposição 20, Euclides explica uma verdade simples porém fundamental sobre os números primos: existe um número infinito deles. Pode-se demonstrar, em notação moderna, da seguinte forma:

: Supondo que o número de primos seja finito e sejam <math> p_1,\ p_2,\ p_3,\ ...,\ p_n</math> os primos. Seja <math> P </math> o número tal que

<math display="block">P</math> = <math>\prod_{i=1}^n p_i + 1,</math> onde <math>\prod</math> denota o [[produtório]].

: Se <math>P</math> é um número primo, é necessariamente diferente dos primos <math> p_1,\ p_2,\ p_3,\ ...,\ p_n,</math> pois sua [[divisão]] por qualquer um deles tem um resto de 1.

: Por outro lado, se <math>P</math> é composto, existe um número primo <math> q </math> tal que <math> q </math> é divisor de <math> P .</math>
: Mas obviamente <math> q \ne\ p_1,\; p_2,\; ...,\; p_n.</math> Logo existe um novo número primo.

: Há um novo número primo, seja <math>P</math> 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 <math>n > 1.</math> Temos <math>n + 1</math> que, necessariamente, é [[Números coprimos|coprimo]] de <math>n</math> (números coprimos são os que não têm nenhum fator comum maior do que <math>1</math>). Provamos isto imaginando que a divisão do menor pelo maior tem resultado <math>0</math> e resto <math> n </math> e do maior pelo menor tem resultado <math>1</math> e resto <math>1.</math> Assim, <math>n (n + 1)</math> tem, necessariamente, ao menos dois factores primos.

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

* A resposta para a segunda pergunta acima é que essa proporção é aproximadamente <math>\frac{n}{\ln (n)},</math> onde <math>\ln</math> é o [[logaritmo natural]].
* Para qualquer número inteiro <math>k,</math> existem <math>k</math> números inteiros consecutivos todos compostos.
* O produto de qualquer sequência de <math>k</math> números inteiros consecutivos é divisível por <math>k!</math>
* Se <math>k</math> não é primo, então <math>k</math> possui, necessariamente, um fator primo menor do que ou igual a <math>\sqrt{k}.</math>
* Todo inteiro maior que 1 pode ser representado de maneira única como o produto de fatores primos


== Grupos e sequências de números primos ==
[[Pierre de Fermat]] (1601-1665) descobriu que todo número primo da forma <math>4n + 1,</math> tal como <math>5,13,17,29,37,41,</math> etc., é a soma de dois quadrados. Por exemplo:
<math display="block"> 5 = 1^2 + 2^2,</math>
<math display="block">13 = 2^2 + 3^2,</math>
<math display="block">17 = 1^2 + 4^2,</math>
<math display="block">29 = 2^2 + 5^2,</math>
<math display="block">37 = 1^2 + 6^2,</math>
<math display="block">41 = 4^2 + 5^2.</math>

Hoje são conhecidos dois grupos de números primos:

* '''<math>(4n+1)</math>''' - que podem sempre ser escritos na forma (<math>x^2+y^2</math>); e
* '''<math>(4n-1)</math>''' - nunca podem ser escritos na forma (<math>x^2+y^2</math>).

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:

[[trinta e um|<math>31</math>]], <math>331, 3.331, 33.331, 333.331, 3.333.331</math> e <math>33.333.331</math> são primos
mas <math>333.333.331</math> não é, pois <math>333.333.331 = 17 \times 19.607.843.</math>

Um olhar mais atento na forma como se distribuem os números primos revela que não há uma regularidade nesta distribuição. Por exemplo existem longos ''buracos'' entre os números primos, o número <math>370.261</math> é seguido de [[cento e onze]]<ref>Conforme [http://www.wolframalpha.com/input/?i=370261+%3C+x+%3C+NextPrime%28370261%29 cálculo feito] pelo [[Wolfram Alpha]].</ref> números compostos e não existem<ref>Conforme [http://www.wolframalpha.com/input/?i=prime+from+20831323+to+20831533 cálculo feito] pelo [[Wolfram Alpha]].</ref> primos entre os números <math>20.831.323</math> e <math>20.831.533.</math>

Algumas fórmulas produzem muitos números primos, por exemplo <math>x^2 - x + 41</math> fornece primos quando <math>x=0,\ 1,\ 2,\ ..., \ 40.</math> <ref>Hua (2009), {{Citação do google books|id=H1jFySMjBMEC|pag=177|texto=41 takes on prime values|p. 176-177}}"</ref><ref>Ver [http://www.wolframalpha.com/input/?i=evaluate+x^2%E2%88%92x%2B41+for+x+from+0..40 lista dos valores], calculada pelo [[Wolfram Alpha]]</ref> Veja que para x = 41, a fórmula resulta em <math> 41^2 </math> que não é primo.

Não existe uma fórmula que forneça primos para todos os valores primos de <math>x,</math> de fato em 1752 [[Goldbach]] provou que não há uma [[Polinómio|expressão polinomial]] em <math>x</math> com coeficientes inteiros que possa fornecer primos para todos os valores de <math>x.</math>

Não se sabe se há uma expressão polinomial <math>ax^2+bx+c</math> com <math>a \ne 0</math> que represente infinitos números primos. [[Dirichlet]] usou métodos para provar que se <math>a,</math> <math>2b</math> e <math>c</math> não têm fator primo em comum, a expressão polinomial a duas variáveis
<math display="block">ax^2 + 2bxy + cy^2</math>
representa infinitos primos, quando <math>x</math> e <math>y</math> assumem valores positivos inteiros.

[[Pierre de Fermat|Fermat]] pensou que a fórmula <math>2^{2^n} + 1</math> forneceria números primos para <math>n = 0,\ 1,\ 2,\ ....</math> Este números são chamados de [[Número de Fermat|números de Fermat]] e são comumente denotados por <math>F_n.</math> Os cinco primeiros números são:
<math display="block">F_0 = 3,\; F_1 = 5,\; F_2 = 17,\; F_3 = 257\; e \;F_4 = 65.537,</math>
sendo todos primos.

== Aproximações para o n-ésimo primo ==
Como consequência do [[teorema do número primo]]<!-- prime number theorem //-->, uma expressão assintótica para o n-ésimo primo <math>p_n</math> é:
<math display="block">p_n \sim n \ln n.</math>

Uma aproximação melhor é:
<math display="block">{ p_n = n \ln n +  n \ln \ln n - n + \frac{n}{\ln n} \left(\ln \ln n - 2 \right) - \frac{n\ln\ln n}{2(\ln n)^2}\left(\ln\ln n-6\right) + O\left( \frac {n} {(\ln n)^2}\right).}</math><ref>{{citar periódico|autor =[[Ernesto Cesàro|Ernest Cesàro]]|data=1894|título=Sur une formule empirique de M. Pervouchine|periódico=Comptes rendus hebdomadaires des séances de l'Académie des sciences|volume=119|páginas=848–849|url=http://gallica.bnf.fr/ark:/12148/bpt6k30752}} {{fr}}</ref>

O [[teorema de Rosser]] mostra que <math>p_n</math> é maior que <math>n \ln n.</math> É possível melhorar esta aproximação com os limites<ref>{{citar livro|autor =[[Eric Bach]], [[Jeffrey Shallit]]|título=Algorithmic Number Theory|volume=1|ano=1996|publicado=MIT Press|isbn=0-262-02405-5|página=233}}</ref><ref>{{citar periódico|autor =[[Pierre Dusart]]|url=http://www.ams.org/mcom/1999-68-225/S0025-5718-99-01037-6/S0025-5718-99-01037-6.pdf|título=The ''k''th prime is greater than ''k(ln k + ln ln k-1)'' for ''k''>=2|periódico=Mathematics of Computation|volume=68|ano=1999|páginas=411–415}}</ref>: <math> n \ln n + n(\ln\ln n - 1) < p_n <  n \ln n + n \ln \ln n</math>, para <math>n \ge 6. </math>
{{âncora|Maior número primo já calculado}}

== Maior número primo conhecido ==
Em Janeiro de 2013, foi divulgado o maior número primo já calculado até então. Tem 17.425.170 dígitos e, se fosse escrito por extenso, ocuparia 3,4 mil páginas impressas com cinco mil caracteres cada. É o número <math>2^{57885161} - 1</math>. Foi descoberto por Curtis Cooper, da [[Universidade Central do Missouri]] em Warrensburg, EUA, como parte do [[Great Internet Mersenne Prime Search]] (GIMPS), um projeto internacional de computação compartilhada desenhado para encontrar números primos de Mersene.<ref>{{citar web|url=http://www.foxnews.com/science/2013/02/05/worlds-largest-prime-number-discovered/|título = World’s largest prime number discovered -- all 17 million digits|autor=|data=|publicado=|acessodata=}}</ref>

Em janeiro de 2016, um grupo de matemáticos da mesma universidade descobriu um número primo com 22.338.618 dígitos, que recebeu o nome "M74207281".<ref>{{citar web|url=http://www.smithsonianmag.com/smart-news/missouri-mathematicians-discover-new-prime-number-180957881/?utm_source=smithsoniandaily&no-ist|título=Missouri Mathematicians Discover New Prime Number}}</ref> É o número <math>2^{74207281} - 1,</math> que tem 5 milhões de dígitos a mais que o último conhecido.<ref>{{citar web|url=http://www.bbc.com/news/technology-35361090|título=Largest known prime number discovered in Missouri|autor=[[BBC]]}}</ref> O achado foi divulgado pelo programa GIMPS.

Em dezembro de 2017 um engenheiro eletrotécnico da empresa de entregas FedEx descobriu um número primo ainda maior: “M77232917”, como foi batizado, tem mais de 23 milhões de dígitos. O homem que o descobriu chama-se Jonathan Pace, tem 51 anos, é norte-americano e também participa do GIMPS.<ref>{{citar web|url=http://observador.pt/2018/01/05/descoberto-o-maior-numero-primo-conhecido-tem-mais-de-23-milhoes-de-digitos/|título=Descoberto o maior número primo conhecido. Tem mais de 23 milhões de dígitos|autor=|data=|publicado=|acessodata=}}</ref> Em dezembro de 2018 uma nova marca de maior número primo foi registrada, alcançando a quantidade de 24 milhões de dígitos.

Em 2024, foi descoberto o maior número primo, 2<sup>136 279 841</sup> – 1, com 41 milhões de dígitos (um [[primo de Mersenne]]). A descoberta de Luke Durant foi feita com recurso a software gratuito conhecido como Great Internet Mersenne Prime Search (GIMPS). A descoberta envolveu a coordenação de milhares de unidades de processamento gráfico (GPUs) em 24 centros de dados em 17 países.<ref>{{citar web |url=https://www.livescience.com/physics-mathematics/mathematics/largest-known-prime-number-spanning-41-million-digits-discovered-by-amateur-mathematician-using-free-software |título=Largest known prime number, spanning 41 million digits, discovered by amateur mathematician using free software |autor= |data= |website= |publicado= |acessodata= |língua= |arquivourl= |arquivodata= |urlmorta=}}</ref>

== Outras Aplicações ==
=== Biologia ===
* A estratégia evolutiva usada por [[cigarra]]s do gênero "''Magicicada''" faz uso de números primos. Evolutivamente, à medida que algumas espécies foram alongando seus períodos de "hibernação", também os de seus predadores naturais foram se alongando. Foram favorecidas aquelas que só emergiam após número primo de anos (13, 17), pois isso reduz ao máximo as chances de encontrar seus predadores naturais.<ref>[https://ideiasesquecidas.com/2020/05/27/cigarras-e-numeros-primos/ ideiasesquecidas.com/] ''Cigarras e números primos''</ref> Um exemplo para entender isso é: Imagine uma espécie de cigarra que vire ninfa a cada 2 anos, e uma outra a cada 4. Um predador natural de cigarras que fique hibernando 4 anos, quando sair de sua hibernação, terá como fonte de alimentação ambas espécies, aumentando a quantidade de comida disponível. Já com as cigarras que ficam hibernando um número primo de anos, seus predadores naturais terão que hibernar esse período de temp também, e terão menos opções de comida.

* Há uma espécie de [[bambu]], "Phyllostachys bambusoides", que tem sua florada a cada 23 anos.<ref>[https://www.nationalgeographic.com/science/article/bamboo-mathematicians nationalgeographic.com/]  Zimmer, Carl (May 15, 2015). "Bamboo Mathematicians". Phenomena: The Loom. National Geographic. Retrieved February 22, 2018.</ref> Cientistas acreditam que esse "número primo de tempo" para cada floração é um diferencial evolutivo dessa espécie frente as demais.

=== Mecânica quântica ===
Começando com o trabalho de Hugh Montgomery e [[Freeman Dyson]] na década de 1970, matemáticos e físicos especularam que os zeros da função zeta Riemann estão conectados aos níveis de energia dos sistemas quânticos.<ref>{{citar web|primeiro=Ivars|último=Peterson|autorlink=Ivars Peterson |obra=MAA Online |url=http://www.maa.org/mathland/mathtrek_6_28_99.html |título=The Return of Zeta |data=28 de junho de 1999 |acessodata=2008-03-14 |urlmorta= sim|arquivourl=https://web.archive.org/web/20071020141624/http://maa.org/mathland/mathtrek_6_28_99.html |arquivodata=20 de outubro de 2007 }}</ref><ref>{{citar periódico|último=Hayes|primeiro=Brian|autorlink=Brian Hayes (scientist)|data=2003|título=Computing science: The spectrum of Riemannium|jstor=27858239|periódico=[[American Scientist]]|volume=91|número=4|páginas=296–300|doi=10.1511/2003.26.3349 |issn = 0003-0996 }}</ref> Os números primos também são significativos na ciência da informação quântica, graças a estruturas matemáticas como bases mutuamente imparciales e medidas de valor positivo de operadores positivos.<ref>{{citar livro|título=Geometry of quantum states : an introduction to quantum entanglement|último1=Bengtsson|primeiro1=Ingemar|último2=Życzkowski|primeiro2=Karol|publicado=[[Cambridge University Press]]|ano=2017|isbn=978-1-107-02625-4|edição=Second|local=Cambridge|páginas=313–354|oclc=967938939|autorlink2=Karol Życzkowski}}</ref><ref>{{citar periódico|último=Zhu|primeiro=Huangjun|título=SIC POVMs and Clifford groups in prime dimensions|url=http://stacks.iop.org/1751-8121/43/i=30/a=305305?key=crossref.45cb006b9f3c7e510461594ea8dfa7f7|periódico=Journal of Physics A: Mathematical and Theoretical|volume=43|número=30|páginas=305305|arxiv=1003.3591|doi=10.1088/1751-8113/43/30/305305|bibcode=2010JPhA...43D5305Z|ano=2010|s2cid=118363843}}</ref>

== Ver também ==
{{div col}}
* [[Crivo de Eratóstenes]]
* [[Números primos gêmeos]]
* [[Elemento Primo]]
* [[Elemento Irredutivel|Elemento Irredutível]]
* [[Função de contagem de números primos]]
* [[Teorema do número primo]]
* [[Teste de primalidade]]
* [[Certificado de Primalidade]]
* [[Função total de fatores primos não repetidos]]
* [[coprimo]]
* [[Primorial]]
* [[Série dos inversos dos primos]]
* [[Demonstração de Furstenberg da infinitude dos números primos]]
* [[Fator primo]]
* [[PrimeGrid]]
* [[Hipótese de Riemann|Hipótese de Riemann sobre os números primos]]
{{div col end}}

{{Notas}}

{{Referências}}

== Bibliografia ==
* {{Citar livro|nome=L. K.|sobrenome=Hua|título=Additive Theory of Prime Numbers|idioma=|edição=|local=|editora=AMS Bookstore|ano=2009|coleção= Translations of Mathematical Monographs|volume=13|isbn=978-0-8218-4942-2|url=http://www.ams.org/bookstore-getitem/item=MMONO/13.S}}
* Marcus du Sautoy, '''Os mistérios dos números: Uma viagem pelos grandes enigmas da matemática (que até hoje ninguém foi capaz de resolver)''', Jorge Zahar Editor Ltda, 2013 ISBN 8-537-81099-1
* Luogeng Hua, '''Additive theory of prime numbers''', American Mathematical Soc. ISBN 0-821-89750-0 {{en}}
* Mary Jane Sterling, '''Álgebra I Para Leigos''', Alta Books Editora, 2013 ISBN 8-576-08256-X
* Edward S. Wall, '''Teoria dos Números para Professores do Ensino Fundamental''', McGraw Hill Brasil, 2014 ISBN 8-580-55353-9
* PAULO BOUHID, '''NÚMEROS CRUZADOS''', biblioteca24horas ISBN 8-578-93055-X
* LAURA LEMAY, ROGERS CADENHEAD, '''APRENDA EM 21 DIAS JAVA 2''' - TRADUÇÃO DA 4a ED. Elsevier Brasil ISBN 8-535-21685-5
* {{citar periódico |último1=Caldwell |primeiro1=Chris K. |último2=Reddick |primeiro2=Angela |último3=Xiong |primeiro3=Yeng |último4=Keller |primeiro4=Wilfrid |número=9 |publicação=[[Journal of Integer Sequences]] |mr=3005523 |título=The history of the primality of one: a selection of sources |url=https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html |volume=15 |ano=2012 |lingua=en |ref=harv}}
* {{citar livro |último1=Dudley |primeiro1=Underwood |título=Elementary number theory |publicado=W.H. Freeman and Co. |edição=2.ª |isbn=978-0-7167-0076-0 |ano=1978 |url=https://books.google.com/books?id=tr7SzBTsk1UC&printsec=frontcover |lingua=en |ref=harv}}
* {{citar livro|título=Unsolved Problems in Number Theory|series=Problem Books in Mathematics|edição=3.ª|primeiro=Richard|último=Guy|autorlink=Richard Kenneth Guy|publicado=Springer|ano=2013|isbn=978-0-387-26677-0|capítulo-url=https://books.google.com/books?id=1BnoBwAAQBAJ&printsec=frontcover|capítulo=A1 Prime values of quadratic functions|lingua=en|ref=harv}}
* {{citar livro|título=Closing the Gap: The Quest to Understand Prime Numbers|primeiro=Vicky|último=Neale|autorlink=Vicky Neale|publicado=Oxford University Press|ano=2017|isbn=978-0-19-109243-5|lingua=en|ref=harv}}
* {{citar livro|título=Elementary Number Theory and Its Applications|primeiro=Kenneth H.|último=Rosen|edição=4.ª|publicado=Addison-Wesley|ano=2000|isbn=978-0-201-87073-2|contribution=Theorem 9.20. Proth's Primality Test|lingua=en|ref=harv}}
* {{citar livro|título=How Euler Did It|series=MAA Spectrum|primeiro=C. Edward|último=Sandifer|local=EUA|publicado=Mathematical Association of America|ano=2007|isbn=978-0-88385-563-8|url=https://books.google.com/books?id=sohHs7ExOsYC&printsec=frontcover|doi=10.1090/spec/052|ref=harv}}
* {{citar livro |último=Sierpiński |primeiro=Wacław |autorlink=Wacław Sierpiński |título=Elementary Theory of Numbers |edição=2.ª |volume=31 |série=North-Holland Mathematical Library |publicado=Elsevier |ano=1988 |isbn=978-0-08-096019-7 |url=https://books.google.com/books?id=ktCZ2MvgN3MC&printsec=frontcover |lingua=en |ref=harv}}
* {{citar livro |último=Tao |primeiro=Terence |autorlink=Terence Tao |isbn=978-0-8218-4883-8 |local=Providence, RI |mr=2523047 |publicado=American Mathematical Society |título=Poincaré's legacies, pages from year two of a mathematical blog. Part I |ano=2009 |ref=harv}}

== Ligações externas ==
{{Wikilivros|Teoria de números|Números primos}}
* [http://www.profcardy.com/artigos/mersenne.php Primos de Mersenne de maneira didática]
* [http://primes.utm.edu/curios/ Prime curios]at the prime pages
* [http://www.utm.edu/research/primes The prime pages]
* [http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html MacTutor history of prime numbers]
* [https://web.archive.org/web/20050723210919/http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ]
* [http://www.primenumbers.net/prptop/prptop.php Lista dos maiores números provavelmente primos]
* [http://www.primepuzzles.net/ The prime puzzles]
* [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html Uma tradução para o inglês da demonstração de Euclides da infinitude dos primos]
* [http://wims.unice.fr/wims/wims.cgi?module=tool/number/primes.en Primes]from WIMS is an online prime generator.
* [http://mathworld.wolfram.com/PrimeSpiral.html Prime Spiral pattern]
* [http://www.alpertron.com.ar/googolm1.pl?digits=12 12 digit primes]Known 12-digit prime factors of [[Googolplex]] - 1
* [http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier]
* [http://www.mersenne.org Primos de Mersenne - Os maiores primos já encontrados]

{{Classes de números primos}}
{{Teoria dos números}}
{{Portal3|Matemática}}

{{DEFAULTSORT:Número primo}}

[[Categoria:Números primos| ]]
[[Categoria:Sequências de números inteiros]]