Número primo

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, 1 × 5 ou 5 × 1, 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.

Os números compostos podem ser organizados em retângulos, já os números primos não.

A propriedade de ser primo é chamada primalidade. Um método simples, mas lento, de verificar a primalidade de um número dado n, chamado de divisão por tentativa, testa se n é um múltiplo de qualquer inteiro entre 2 e ${\displaystyle {\sqrt {n}}}$. 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. Em outubro de 2024^[update], o maior número primo conhecido é um número primo de Mersenne com 41 024 320 algarismos.^[1][2]

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

Ver artigo principal: 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.^[3] Noutras palavras, n é primo se n elementos não podem ser divididos em grupos menores, porém maior que apenas um, de mesma quantidade,^[4] ou não é possível organizar n pontos em uma grade retangular que possui mais de um ponto de altura ou largura.^[5] Por exemplo, entre os números de 1 a 6, os números 2, 3 e 5 são primos,^[6] 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. 4 = 2 × 2 e 6 = 2 × 3 são ambos compostos.

Demonstração, com hastes de Cuisenaire, que 7 é primo, pois 2, 3, 4, 5 nem 6 divide-o igualmente

Os divisores de um número natural n são os números naturais que dividem igualmente 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.^[7] Ainda, outra maneira de expressar a mesma coisa, é que um número n é primo se é maior que um e nenhum dos números 2, 3, ... , n − 1 divide igualmente n.^[8]

Os primeiros 25 números primos (todos os primos menores que 100) são:^[9]

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 (sequência A000040 na OEIS)

Nenhum número par n maior que 2 é primo, visto que tal número pode ser expresso como o produto 2 × n/2. Portanto, Todo número primo além do 2 é um número impar.^[10] 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.^[11]

O conjunto de todos os primos é às vezes denotado pela letra P (uma letra P maiúscula em negrito)^[12] ou por ${\displaystyle \mathbb {P} }$ (uma letra P maiúscula em blackboard bold)^[13]

História

Terceira coluna do osso de Ishango, que contém os números primos entre 10 e 20.

O Papiro de Rhind

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,^[14] mas isso pode ser apenas uma coincidência.^[15] 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.^[16] 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.^[17] 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.^[18]

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.^[19]

Entretanto, o primeiro registro sobrevivente do estudo de números primos vem dos matemáticos da Grécia Antiga, que os chamaram de prōtos arithmòs (πρῶτος ἀριθμὸς). 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.^[20] Outra invenção grega, o crivo de Eratóstenes, ainda é utilizado para construir listas de primos.^[21][22] Os séculos seguintes foram marcados por um certo desinteresse pelo estudo dos números primos, sem haver resultados relevantes neste tópico.^[23]

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 n dividem igualmente (n − 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.^[24] 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.^[22] 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.^[22]

Em 1640, Pierre de Fermat afirmou (sem provar) o pequeno teorema de Fermat (que posteriormente foi provado por Leibniz e Euler)^[25] e o teorema de Fermat sobre somas de dois quadrados (provado por Euler).^[26] Fermat também investigou a primalidade dos números de Fermat 2²ⁿ + 1,^[27] e Marin Mersenne estudou os primos de Mersenne, primos da forma 2^p − 1 com p primo.^[28] Christian Goldbach formulou a conjectura de Goldbach, que todo número par é a soma de primos, numa carta de 1742 para Euler.^[29] Euler provou a conjectura de Alhazém (agora chamado de teorema de Euclides–Euler [en]) que dizia que todo número perfeito par pode ser construído a partir de primos de Mersenne.^[20] 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 ${\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }$.^[30] No início do século XIX, Legendre e Gauss conjecturaram que conforme x tende a infinito, o número de primos menores que x é assintótico a x/log x, onde log x é o logaritmo natural de x. Uma pequena consequência dessa alta densidade de primos era o postulado de Bertrand, que para todo n > 1, existe pelo menos um primo entre n e 2n, provado em 1852 por Pafnuty Chebyshev.^[31] 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.^[32] 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.^[33]

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),^[34] o teorema de Proth (c. 1878),^[35] o teste de primalidade de Lucas–Lehmer (originalmente desenvolvido em 1878) e o teste de primalidade de Lucas generalizado.^[22] Desde 1951, todos os maiores primos conhecidos foram encontrados utilizando esses testes em computadores.^{[nota 1]} 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.^[9][37] A ideia de que os números primos tinham poucas aplicações fora da matemática pura^{[nota 2]} 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.^[40]

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.^[21][41][42] 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.^[43]

Primalidade do um

A maioria dos antigos gregos nem consideravam 1 ser um número,^[44][45] então eles nem consideravam a sua primalidade. Alguns estudiosos da tradição grega e da romana, incluindo 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áticos islâmicos medievais seguiram em grande parte os gregos ao considerar que 1 não era um número.^[44] Na Idade Média e Renascença, matemáticos começaram a tratar o 1 como um número, e por volta do século XVII alguns deles incluia-o como o primeiro número primo.^[46] Em meados do século 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.^[47] Ainda no século XIX, diversos matemáticos ainda consideravam 1 ser primo,^[48] e listas de números primos que incluíam 1 continuaram a ser publicadas até 1956.^[49][50] Entretanto, por volta dessa época, no início do século XX, os matemáticos começaram a concordar que 1 não deveria ser classificado como um número primo.^[48]

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.^[48] 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.^[50] 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.^[51] No início do século 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".^[48]

Propriedades elementares

Unicidade da decomposição

Ver artigo principal: Teorema fundamental da aritmética

Escrever um número como um produto de números primos é chamado de decomposição em fatores primos de um número. Por exemplo: $${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$$ Os termos do produto são chamados de fatores primos. O mesmo fator primo pode aparecer mais de uma vez; nesse exemplo, há duas cópias do fator primo 5. Quando um primo aparece mais de uma vez, pode ser utilizado a exponenciação para agrupar as múltiplas cópias do mesmo número: para esse exemplo, na segunda maneira de escrita do produto acima, 5² indica o quadrado de 5.^[52]

A principal importância dos números primos para a teoria dos números e a matemática em geral deriva do teorema fundamental da aritmética.^[53] Este teorema afirma que todo número inteiro maior que 1 pode ser escrito como o produto de um ou mais primos. Mais fortemente, este produto é único no sentido que quaisquer duas decomposições de um mesmo número terão os mesmos números de cópias dos mesmos primos, apesar de que a ordem dos fatores pode alterar.^[54][55] Então, embora existam diferentes formas de encontrar a decomposição usando um algoritmo de fatoração de inteiros, todos eles deverão produzir o mesmo resultado. Os números primos podem ser considerados os "blocos fundamentais de construção" dos números naturais.^[56][57]

Algumas provas da unicidade da decomposição se baseiam no lema de Euclides: Se p é um número primo e p divide o produto ab dos inteiros a e b, então p divide a ou p divide b (ou ambos).^[58][59] Por outro lado, se um número p tem a propriedade de ao dividir um produto, ele sempre divide pelo menos um dos fatores do produto, então p deve ser primo.^[60]

Infinitude

Ver artigo principal: Teorema de Euclides

Existem infinitos números primos. Outra maneira de dizer isto é que a sequência de números primos

2, 3, 5, 7, 11, 13, ...

nunca acaba. Esta afirmação é referida como o teorema de Euclides, em homenagem ao antigo matemático grego Euclides, já que a primeira prova conhecida para esta afirmação é atribuída a ele. Diversas outras provas da infinitude dos números primos são conhecidas, incluindo uma prova analítica de Euler, uma prova de Goldbach baseada nos números de Fermat,^[61] a prova de Furstenberg usando topologia geral^[62] e a elegante prova de Kummer.^[63]

O teorema de Euclides^[64] mostra que toda lista finita de primos é incompleta. A ideia-chave é multiplicar todos os primos da dada lista e somar 1. A lista consiste de primos p₁, p₂, ..., p_n, o que dá o número $${\displaystyle N=p_{1}\cdot p_{2}\cdots p_{n}+1.}$$

Pelo teorema fundamental da aritmética, existe algum primo p pertencente à lista que divide N. Entretanto, todos os elementos da lista dividem o produto p₁ · p₂ ⋯ p_n e, portanto, se p divide N, então p divide 1, o que é um absurdo. Como não há uma lista finita de todos os primos, então existem infinitos números primos.^[65]

Os números formados por adicionar um ao produto de um número primo por todos os primos menores que ele são chamados de números de Euclides.^[66] Os cinco primeiros deles são primos, mas o sexto, $${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$$ é um número composto.^[67]

Fórmulas para números primos

Ver artigo principal: Fórmulas para números primos

Às vezes, a "resposta" é apresentada como uma fórmula tão confusa e longa, e tão cheia de fatoriais e alternâncias de sinais e outras coisas, que podemos sentir que a doença é preferível à cura.

Herbert Wilf (1982)^[68]

Nenhuma fórmula eficiente para encontrar números primos é conhecida. Por exemplo, não há nenhum polinômio não constante, mesmo em várias variáveis, que resulte em apenas valores primos.^[69] Porém, existem diversas expressões que codificam todos os primos, ou apenas primos. Uma possível fórmula é baseado no teorema de Wilson e gera o número 2 diversas vezes e todos os outros números primos exatamente uma vez.^[70]

Outra fórmula, publicada por Willans em 1964, é $${\displaystyle p_{n}=1+\sum _{i=1}^{2^{n}}\left\lfloor \left({\frac {n}{\sum _{j=1}^{i}\left\lfloor \left(\cos {\frac {(j-1)!+1}{j}}\pi \right)^{2}\right\rfloor }}\right)^{1/n}\right\rfloor ,}$$ que computa o n-ésimo número primo p_n. Essa fórmula também é ineficaz, pois, além de conter o termo ${\displaystyle (j-1)!}$, ela calcula o valor p_n somando p_n vezes o número 1; por exemplo,^[71] $${\displaystyle p_{5}=1+1+1+1+1+1+1+1+1+1+1+0+0+\dots +0=11.}$$ Os artigos What is an Answer? de Herbert Wilf (1982)^[68] e Formulas for Primes de Underwood Dudley (1983)^[72] discutem mais sobre a inutilidade de tais fórmulas.

Há também um conjunto de equações diofantinas em nove variáveis e um parâmetro com a seguinte propriedade: o parâmetro é primo se, e somente se, o sistema de equações resultante tiver uma solução sobre os números naturais. Isso pode ser usado para obter uma única fórmula com a propriedade de que todos os seus valores positivos são primos.^[69]

Outros exemplos de fórmulas geradoras de números primos vêm do teorema de Mills e de um teorema de Wright. Eles afirmam que existem as constantes reais A > 1 e μ tais que $${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ e }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$$ são primos para qualquer número natural n na primeira fórmula, e qualquer número de exponentes na segunda fórmula.^[73] Aqui ${\displaystyle \lfloor {}\cdot {}\rfloor }$ representa a função piso, ou seja, o maior número inteiro que seja menor ou igual ao número em questão. Entretanto, essas fórmulas não são úteis para generalizar primos, visto que primeiramente deve ser gerado os números primos para poder computar os valores de A ou μ.^[69]

Questões em aberto

Ver também a categoria: Conjecturas sobre números primos

Diversas conjecturas sobre números primos foram propostas. Muitas dessas conjecturas, geralmente com uma formulação elementar, têm resistido à prova durante décadas: todas os quatro problemas de Landau de 1912 continuam em aberto.^[74] Um desses problemas é a conjectura de Goldbach, que afirma que todo número inteiro n maior que 2 pode ser escrito como a soma de dois primos^[75] Em 2014^[update], essa conjectura foi verificada para todos os números até n = 4×10¹⁸.^[76] Afirmações mais fracas que essa já foram provadas, como, por exemplo, o teorema de Vinogradov, que diz que todo ímpar suficientemente grande pode ser escrito como a soma de três primos.^[77] O teorema de Chen diz que todo par suficientemente grande pode ser escrito como a soma de um primo e um semiprimo (produto de dois primos).^[78] Também, qualquer par maior que 10 pode ser escrito como a soma de seis primos.^[79] O ramo da teoria dos números que estuda tais questões se chama teoria aditiva dos números.^[80]

Outro tipo de problema está relacionado aos intervalos entre primos, isto é, a diferença entre primos consecutivos. A existência de intervalos entre primos de tamanho arbitrário pode ser observada na sequência n! + 2, n! + 3, ..., n! + n, que consiste de n − 1 números compostos, para qualquer número natural n.^[81] Entretanto, intervalos maiores podem ocorrer muito antes do que este argumento apresenta.^[82] Por exemplo, o primeiro intervalo de 8 unidades ocorre entre os primos 89 e 97,^[83] muito menor do que 8! = 40320. É conjecturado que existem infinitos números primos gêmeos, que são pares de primos cuja diferença é 2; esta é a conjectura dos primos gêmeos. A conjectura de Polignac é mais generalizada, afirmando que para cada inteiro positivo k, existem infinitos pares de primos consecutivos cujas diferenças são iguais a 2k.^[84] A conjectura de Andrica,^[84] a conjectura de Brocard,^[85] a conjectura de Legendre^[86] e a conjectura de Oppermann^[85] sugerem que o maior intervalo entre primos de 1 a n deve ser de aproximadamente ${\displaystyle {\sqrt {n}}}$, um resultado conhecido por seguir a hipótese de Riemann, enquanto a conjectura de Cramér, muito mais forte, define o maior intervalo entre primos com o tamanho de ${\displaystyle O((\log n)^{2})}$.^[84] Intervalos entre primos podem ser generalizados a n-uplas de números primos, que são definidas para diferenças entre mais de dois números primos. A infinitude e densidade são assuntos da primeira conjectura de Hardy–Littlewood, que podem ser motivados pela heurística de que os números primos se comportam de forma semelhante a uma sequência aleatória de números com densidade dada pelo teorema dos números primos.^[87]

Teoria dos números

Ver artigo principal: 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 ${\displaystyle n,}$ qual é a proporção de números primos entre os números menores que ${\displaystyle n}$?

• A resposta à primeira questão é que o conjunto dos primos é infinito, um resultado conhecido na parte central dos 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 ${\displaystyle p_{1},\ p_{2},\ p_{3},\ ...,\ p_{n}}$ os primos. Seja ${\displaystyle P}$ o número tal que

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

Se ${\displaystyle P}$ é um número primo, é necessariamente diferente dos primos ${\displaystyle 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 ${\displaystyle P}$ é composto, existe um número primo ${\displaystyle q}$ tal que ${\displaystyle q}$ é divisor de ${\displaystyle P.}$

Mas obviamente ${\displaystyle q\neq \ p_{1},\;p_{2},\;...,\;p_{n}.}$ Logo existe um novo número primo.

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

Tomemos o sucessor deste, que representamos como ${\displaystyle n(n+1)+1.}$ Pelo mesmo raciocínio, ele é coprimo a ${\displaystyle n(n+1).}$ Ao multiplicar os dois números, temos ${\displaystyle [n(n+1)]*[n(n+1)+1].}$ 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 ${\displaystyle {\frac {n}{\ln(n)}},}$ onde ${\displaystyle \ln }$ é o logaritmo natural.
• Para qualquer número inteiro ${\displaystyle k,}$ existem ${\displaystyle k}$ números inteiros consecutivos todos compostos.
• O produto de qualquer sequência de ${\displaystyle k}$ números inteiros consecutivos é divisível por ${\displaystyle k!}$
• Se ${\displaystyle k}$ não é primo, então ${\displaystyle k}$ possui, necessariamente, um fator primo menor do que ou igual a ${\displaystyle {\sqrt {k}}.}$
• 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 ${\displaystyle 4n+1,}$ tal como ${\displaystyle 5,13,17,29,37,41,}$ etc., é a soma de dois quadrados. Por exemplo: $${\displaystyle 5=1^{2}+2^{2},}$$ $${\displaystyle 13=2^{2}+3^{2},}$$ $${\displaystyle 17=1^{2}+4^{2},}$$ $${\displaystyle 29=2^{2}+5^{2},}$$ $${\displaystyle 37=1^{2}+6^{2},}$$ $${\displaystyle 41=4^{2}+5^{2}.}$$

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

• ${\displaystyle (4n+1)}$ - que podem sempre ser escritos na forma (${\displaystyle x^{2}+y^{2}}$); e
• ${\displaystyle (4n-1)}$ - nunca podem ser escritos na forma (${\displaystyle 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:

${\displaystyle 31}$, ${\displaystyle 331,3.331,33.331,333.331,3.333.331}$ e ${\displaystyle 33.333.331}$ são primos mas ${\displaystyle 333.333.331}$ não é, pois ${\displaystyle 333.333.331=17\times 19.607.843.}$

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 ${\displaystyle 370.261}$ é seguido de cento e onze^[88] números compostos e não existem^[89] primos entre os números ${\displaystyle 20.831.323}$ e ${\displaystyle 20.831.533.}$

Algumas fórmulas produzem muitos números primos, por exemplo ${\displaystyle x^{2}-x+41}$ fornece primos quando ${\displaystyle x=0,\ 1,\ 2,\ ...,\ 40.}$ ^[90][91] Veja que para x = 41, a fórmula resulta em ${\displaystyle 41^{2}}$ que não é primo.

Não existe uma fórmula que forneça primos para todos os valores primos de ${\displaystyle x,}$ de fato em 1752 Goldbach provou que não há uma expressão polinomial em ${\displaystyle x}$ com coeficientes inteiros que possa fornecer primos para todos os valores de ${\displaystyle x.}$

Não se sabe se há uma expressão polinomial ${\displaystyle ax^{2}+bx+c}$ com ${\displaystyle a\neq 0}$ que represente infinitos números primos. Dirichlet usou métodos para provar que se ${\displaystyle a,}$ ${\displaystyle 2b}$ e ${\displaystyle c}$ não têm fator primo em comum, a expressão polinomial a duas variáveis $${\displaystyle ax^{2}+2bxy+cy^{2}}$$ representa infinitos primos, quando ${\displaystyle x}$ e ${\displaystyle y}$ assumem valores positivos inteiros.

Fermat pensou que a fórmula ${\displaystyle 2^{2^{n}}+1}$ forneceria números primos para ${\displaystyle n=0,\ 1,\ 2,\ ....}$ Este números são chamados de números de Fermat e são comumente denotados por ${\displaystyle F_{n}.}$ Os cinco primeiros números são: $${\displaystyle F_{0}=3,\;F_{1}=5,\;F_{2}=17,\;F_{3}=257\;e\;F_{4}=65.537,}$$ sendo todos primos.

Aproximações para o n-ésimo primo

Como consequência do teorema do número primo, uma expressão assintótica para o n-ésimo primo ${\displaystyle p_{n}}$ é: $${\displaystyle p_{n}\sim n\ln n.}$$

Uma aproximação melhor é: $${\displaystyle {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).}}$$^[92]

O teorema de Rosser mostra que ${\displaystyle p_{n}}$ é maior que ${\displaystyle n\ln n.}$ É possível melhorar esta aproximação com os limites^[93][94]: ${\displaystyle n\ln n+n(\ln \ln n-1)<p_{n}<n\ln n+n\ln \ln n}$, para ${\displaystyle n\geq 6.}$

Métodos computacionais

A engrenagem menor neste equipamento agrícula possui 13 dentes, um número primo, e a engrenagem média tem 21, coprimo de 13

Por muito tempo, a teoria dos números, em geral, e o estudo dos números primos, em particular, foram vistos como o exemplo canônico da matemática pura, sem aplicações fora da matemática^{[nota 2]} além do uso de dentes de engrenagens com números primos para distribuir o desgaste uniformemente.^[95] Em particular, os teóricos dos números, como o matemático britânico G. H. Hardy, orgulhavam-se de fazer um trabalho que não tinha absolutamente nenhum significado militar.^[96]

Essa visão da pureza da teoria dos números foi abalada na década de 1970, quando foi anunciado publicamente que os números primos poderiam ser usados como base para a criação de algoritmos de criptografia de chave pública.^[40] Esses aplicativos levaram a um estudo significativo de algoritmos para computação com números primos e, em particular, de testes de primalidade, métodos para determinar se um determinado número é primo. A rotina mais básica de teste de primalidade, a divisão por tentativa, é muito lenta para ser útil para números grandes.^[97] Um grupo de testes de primalidade modernos é aplicável a números arbitrários, enquanto testes mais eficientes estão disponíveis para números de tipos especiais. A maioria dos testes de primalidade apenas informa se o argumento é primo ou não. As rotinas que também fornecem um fator primo de argumentos compostos (ou todos os seus fatores primos) são chamadas de algoritmos de fatoração.^[98] Os números primos também são usados na computação para somas de verificação,^[99] tabelas de dispersão^[100] e geradores de números pseudo-aleatórios.^[101][102]

Divisão por tentativa

Ver artigo principal: Divisão por tentativa

O método mais básico para verificar a primalidade de um determinado número inteiro é chamado de divisão por tentativa. Esse método divide cada número inteiro n de 2 até a raiz quadrada de n. Qualquer número inteiro que se divida igualmente é considerado composto; caso contrário, é primo. Os números inteiros maiores que a raiz quadrada não precisam ser verificados porque, sempre que n = a · b, um dos dois fatores e é menor ou igual à raiz quadrada de n. Outra otimização é verificar apenas os números primos como fatores nesse intervalo.^[97] Por exemplo, para verificar se 37 é primo, esse método o divide pelos números primos no intervalo de 2 a ${\displaystyle {\sqrt {37}}}$, que são 2, 3 e 5. Cada divisão gera um resto diferente de zero e, portanto, 37 é, de fato, primo.

Embora esse método seja simples de descrever, ele não é prático para testar a primalidade de números inteiros grandes, porque o número de testes que ele realiza cresce exponencialmente em função do número de dígitos desses números inteiros.^[103] No entanto, a divisão por tentativa ainda é usada, com um limite menor do que a raiz quadrada no tamanho do divisor, para descobrir rapidamente números compostos com fatores pequenos, antes de usar métodos mais complicados nos números que passam por esse filtro.^[104]

Crivos

O crivo de Eratóstenes começa com todos os números não marcados (cinza). Ele encontra repetidamente o primeiro número não marcado, marca-o como primo (cores escuras) e marca seu quadrado e todos os múltiplos posteriores como compostos (cores mais claras). Depois de marcar os múltiplos de 2 (vermelho), 3 (verde), 5 (azul) e 7 (amarelo), todos os primos até a raiz quadrada do tamanho da tabela foram processados, e todos os números restantes não marcados (11, 13 etc.) são marcados como primos (magenta).

Ver artigo principal: Crivo de Eratóstenes

Antes dos computadores, as tabelas matemáticas que listavam todos os primos ou decomposições em números primos até um determinado limite eram comumente impressas.^[105] O método mais antigo conhecido para gerar uma lista de primos é chamado de crivo de Eratóstenes.^[106] A animação mostra uma variante otimizada desse método.^[107] Outro crivo assintoticamente mais eficiente para o mesmo problema é o crivo de Atkin.^[108] Na matemática avançada, a teoria dos crivos aplica métodos semelhantes a outros problemas.^[109]

Teste de primalidade versus prova de primalidade

Alguns dos testes modernos mais rápidos para verificar se um dado número n arbitrário é primo são algoritmos probabilísticos (ou de Monte Carlo), o que significa que eles possuem uma pequena chance aleatória de gerar uma resposta errada.^[110] Por exemplo, o teste de primalidade de Solovay–Strassen em um dado número p escolhe um número aleatório a de 2 a p − 2 e usa exponenciação modular para verificar se a^{(p − 1)} ± 1 é divisível por p.^{[nota 3]} Se for divisível, então a resposta é sim, caso contrário, é não. Se p realmente for primo, então a resposta sempre será sim, mas se for composto, então a resposta é sim com a probabilidade de no máximo 1/2 e não com a probabilidade de no mínimo 1/2.^[111] Se esse teste é repetido n vezes no mesmo número, a probabilidade de um número composto passar em todos os testes é de no máximo 1/2ⁿ. Como essa probabilidade decresce exponencialmente conforme o número de testes aumenta, ele produz uma alta confiança (porém não seja certeza) de que um número que passe por repetidos testes seja primo. Por outro lado, se algum dos testes falhar, então o número é certamente composto.^[112] Um número composto que passa por tal teste é chamado de pseudoprimo.^[111]

Por outro lado, alguns outros algoritmos garantem que a resposta sempre será correta: os primos sempre serão determinados como primos e os compostos sempre serão determinados como compostos. Isso é verdade para a divisão por tentativa, por exemplo. Os algoritmos que garantem um resultado correto incluem tanto algoritmos determinísticos (não aleatórios), como o teste de primalidade AKS,^[113] quanto algoritmos de Las Vegas randomizado, em que as escolhas aleatórias feitas não interferem em sua resposta final, como algumas variações da prova de primalidade por curvas elípticas.^[110] Quando o método da curva elíptica conclui que um número é primo, ele gera um certificado de primalidade que pode ser rapidamente verificado.^[114] Na prática, a prova de primalidade por curvas elípticas é o mais rápido entre os testes de primalidade com garantia de uma resposta correta, mas sua análise de tempo de execução é baseada em argumentos heurísticos em vez de provas rigorosas. O teste de primalidade AKS possui uma complexidade de tempo matematicamente provada, mas, na prática, o método é mais lento que a prova por curvas elípticas.^[115] Esses métodos podem ser usados ​​para gerar grandes números primos aleatórios, gerando e testando números aleatórios até encontrar um que seja primo; ao fazer isso, um teste probabilístico mais rápido pode eliminar rapidamente a maioria dos números compostos antes que um algoritmo que garanta uma resposta correta seja usado para verificar se os números restantes são primos.^{[nota 4]}

A tabela a seguir lista alguns desses testes. Seu tempo de execução é dado em termos de n, o número a ser testado e, para algoritmos probabilísticos, o número k de testes realizados. Além disso, ε é um número positivo arbitrariamente pequeno, e log é o logaritmo para uma base não especificada. A notação big-O significa que cada limite de tempo deve ser multiplicado por um fator constante para convertê-lo de unidades adimensionais para unidades de tempo; esse fator depende de detalhes de implementação, como o tipo de computador usado para executar o algoritmo, mas não dos parâmetros de entrada n e k.

Teste	Develovido em	Tipo	Tempo de execução	Notas	Refs.
Teste de primalidade AKS	2002	deterministico	${\displaystyle O((\log n)^{6+\varepsilon })}$		[113][116]
Prova de primalidade por curvas elípticas	1986	Las Vegas	${\displaystyle O((\log n)^{4+\varepsilon })}$ heuristicamente		[115]
Teste de primalidade de Baillie–PSW	1980	Monte Carlo	${\displaystyle O((\log n)^{2+\varepsilon })}$		[117][118]
Teste de primalidade de Miller–Rabin	1980	Monte Carlo	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	probabilidade de erro de ${\displaystyle 4^{-k}}$	[119]
Teste de primalidade de Solovay–Strassen	1977	Monte Carlo	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	probabilidade de erro de ${\displaystyle 2^{-k}}$	[119]

Algoritmos para tipos específicos e o maior primo conhecido

Ver também: Lista de números primos

Além dos testes mencionados acima, que se aplicam a qualquer número natural, alguns números de formato especial podem ser testados quanto à primalidade mais rapidamente. Por exemplo, o teste de primalidade de Lucas–Lehmer pode determinar se um número de Mersenne (um a menos que uma potência de dois) é primo, deterministicamente, usando o mesmo tempo que uma única iteração do teste de Miller-Rabin.^[120] É por isso que desde 1992 (até outubro de 2024^[update]) o maior primo conhecido sempre foi um primo de Mersenne.^[121] Conjectura-se que existam infinitos primos de Mersenne.^[122]

A tabela a seguir apresenta os maiores números primos conhecidos de vários tipos. Alguns desses primos foram encontrados usando processamento distribuído. Em 2009, o projeto Great Internet Mersenne Prime Search recebeu um prêmio de 100 mil dólares pela primeira descoberta de um primo com pelo menos 10 milhões de dígitos.^[123] A Electronic Frontier Foundation também oferece 150 mil e 250 mil dólares para quem encontrar primos com pelo menos 100 milhões e 1 bilhão de dígitos, respectivamente.^[124]

Tipo	Primo	Número de dígitos decimais	Data	Descoberto por
Primo de Mersenne	2136 279 841 − 1	41 024 320	21 de outubro de 2024[1]	Luke Durant, Great Internet Mersenne Prime Search
Primo de Proth	10 223 × 231 172 165 + 1	9 383 761	31 de outubro de 2016[125]	Péter Szabolcs, PrimeGrid[126]
Primo fatorial	208 003! − 1	1 015 843	Julho de 2016	Sou Fukui[127]
Primo primorial[nota 5]	1 098 133# − 1	476 311	Março de 2012	James P. Burt, PrimeGrid[128]
Primos gêmeos	2 996 863 034 895 × 21 290 000 ± 1	388 342	Setembro de 2016	Tom Greer, PrimeGrid[129]

Fatoração de inteiros

Ver artigo principal: Fatoração de inteiros

Dado um número inteiro composto n, a tarefa de fornecer um um ou mais de seus fatores primos é chamada de fatoração de n. É significativamente mais difícil do que o teste de primalidade,^[130] e, embora muitos algoritmos de fatoração sejam conhecidos, eles são mais lentos do que os métodos mais rápidos de teste de primalidade. A divisão por tentativa e o algoritmo rho de Pollard podem ser usados para encontrar fatores muito pequenos de n,^[104] e a fatoração de curva elíptica pode ser eficaz quando n tem fatores de tamanho moderado.^[131] Os métodos adequados para números arbitrariamente grandes que não dependem do tamanho de seus fatores incluem o crivo quadrático e o crivo do corpo de números generalizado. Assim como no teste de primalidade, há também algoritmos de fatoração que exigem que sua entrada tenha uma forma específica, incluindo o crivo do corpo de números específico.^[132] Em dezembro de 2019^[update], o maior número conhecido por ter sido fatorado por um algoritmo de uso geral é o RSA-240, que tem 240 dígitos decimais (795 bits) e é o produto de dois primos grandes.^[133]

O algoritmo de Shor pode fatorar qualquer número inteiro em uma quantidade polinomial de etapas em um computador quântico.^[134] Entretanto, a tecnologia atual só pode executar esse algoritmo para números muito pequenos. Em outubro de 2012^[update], o maior número que foi fatorado por um computador quântico que executa o algoritmo de Shor é 21.^[135]

Outras aplicações computacionais

Vários algoritmos de criptografia de chave pública, como RSA e a troca de chaves de Diffie–Hellman, são baseados em grandes números primos (primos de 2048 bits são comuns).^[136] O RSA se baseia na suposição de que é muito mais fácil (ou seja, mais eficiente) realizar a multiplicação de dois números (grandes) x e y do que calcular x e y (assumindo que são coprimos) se apenas o produto xy for conhecido.^[40] A troca de chaves Diffie–Hellman se baseia no fato de que existem algoritmos eficientes para exponenciação modular (computando a^b mod c), enquanto a operação reversa (o logaritmo discreto) é considerada um problema difícil.^[137]

Os números primos são usados com frequência em tabelas de dispersão. Por exemplo, o método original de Carter e Wegman para hashing universal baseava-se em funções hash de computação escolhendo funções lineares aleatórias no módulo de grandes números primos. Carter e Wegman generalizaram esse método para o hashing k-independente usando polinômios de grau mais alto, novamente no módulo de grandes números primos.^[138] Assim como na função de hash, os números primos são usados para definir o tamanho da tabela de dispersão em tabelas de dispersão baseadas em sondagem quadrática para garantir que a sequência de sondagem cubra toda a tabela.^[100]

Alguns métodos de soma de verificação são baseados na matemática dos números primos. Por exemplo, as somas de verificação usadas nos International Standard Book Numbers são definidas tomando-se o resto do número no módulo 11, um número primo. Como 11 é primo, esse método pode detectar erros de um único dígito e transposições de dígitos adjacentes.^[99] Outro método de soma de verificação, o Adler-32 [en], usa o módulo aritmético 65521, o maior número primo menor que 2¹⁶.^[139] Os números primos também são usados em geradores de números pseudo-aleatórios, incluindo geradores congruentes lineares^[101] e o Mersenne Twister.^[102]

Outras aplicações

Os números primos são de importância central para a teoria dos números, mas também têm muitas aplicações em outras áreas da matemática, incluindo álgebra abstrata e geometria elementar. Por exemplo, é possível colocar um número primo de pontos em uma malha bidimensional de modo que não haja três pontos alinhados, ou de modo que cada triângulo formado por três dos pontos tenha uma área não nula.^[140] Outro exemplo é o critério de Eisenstein, um teste para saber se um polinômio é irredutível com base na divisibilidade de seus coeficientes por um número primo e seu quadrado.^[141]

A soma conectada de dois nós primos

O conceito de um número primo é tão importante que foi generalizado de diferentes maneiras em vários ramos da matemática. Em geral, "primo" indica minimalidade ou indecomponibilidade, em um sentido apropriado. Por exemplo, o corpo primo de um determinado corpo é seu menor subcorpo que contém 0 e 1. É o corpo dos números racionais ou um corpo finito com um número primo de elementos (daí o nome).^[142] Muitas vezes, um segundo significado adicional é pretendido com o uso da palavra primo: qualquer objeto pode ser decomposto, essencialmente de forma única, em seus componentes primos. Por exemplo, na teoria dos nós, um nó primo é um nó que não podem ser decompostos, no sentido de que não pode ser escrito como a soma conectada de dois nós não triviais. Qualquer nó pode ser expresso exclusivamente como uma soma conectada de nós primos.^[143] A decomposição prima de 3-variedades é outro exemplo desse tipo.^[144]

Além da matemática e da computação, os números primos têm possíveis conexões com a mecânica quântica^[145][146] e têm sido usados metaforicamente nas artes e na literatura. Eles também foram usados na biologia evolutiva para explicar os ciclos de vida das cigarras.^[147]

Polígonos construtíveis e partições de polígonos

Construção de um pentágono regular utilizando régua e compasso. Isso somente é possível pelo fato de 5 ser um primo de Fermat.

Os primos de Fermat são aqueles da forma $${\displaystyle F_{k}=2^{2^{k}}+1,}$$ com k inteiro não negativo.^{[nota 6]} Eles receberam esse nome em homenagem a Pierre de Fermat, que conjecturou que todos esses números são primos. Os primeiros cinco desses números — 3, 5, 17, 257 e 65 537 — são primos,^[148] mas F₅ é composto, assim como todos os outros números de Fermat que foram verificados até 2017.^[149] Um n-ágono regular é construtível usando régua e compasso se, e somente se, os fatores primos ímpares de n (se houver) forem primos de Fermat distintos.^[148] Da mesma forma, um n-ágono regular pode ser construído usando régua, compasso e uma trissecção do ângulo se, e somente se, os fatores primos de n forem qualquer número de cópias de 2 ou 3, juntamente com um conjunto (possivelmente vazio) de primos de Pierpont [en] distintos, que são primos da forma 2^a ⋅ 3^b + 1.^[150]

É possível dividir qualquer polígono convexo em n polígonos convexos menores de mesma área e perímetro quando n é uma potência de um número primo, mas isso não é conhecido para outros valores de n.^[151]

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 as raízes da função zeta de Riemann estão conectados aos níveis de energia dos sistemas quânticos.^[145][146] Os números primos também são importantes na ciência da informação quântica, graças a estruturas matemáticas como bases mutuamente imparciais e medidas simétricas de valor positivo com operador positivo e informativamente completas.^[152][153]

Biologia

A estratégia evolutiva usada pelas cigarras do gênero Magicicada faz uso de números primos.^[147] Esses insetos passam a maior parte de suas vidas como larvas subterrâneas. Eles só se tornam pupas e emergem de suas tocas depois de 7, 13 ou 17 anos, quando voam, se reproduzem e morrem depois de no máximo algumas semanas. Os biólogos teorizam que essas durações de ciclos de reprodução com números primos evoluíram para evitar que os predadores se sincronizem com esses ciclos.^[154][155] Por outro lado, os períodos de vários anos entre a floração das plantas de bambu são considerados números suaves, tendo apenas pequenos números primos em suas fatorações.^[156]

Artes e literatura

Os números primos influenciaram muitos artistas e escritores. O compositor francês Olivier Messiaen usou os números primos para criar música amétrica por meio de "fenômenos naturais". Em obras como La Nativité du Seigneur (1935) e Quatre études de rythme (1949-1950), ele emprega simultaneamente temas com comprimentos dados por diferentes números primos para criar ritmos imprevisíveis: os primos 41, 43, 47 e 53 aparecem no terceiro estudo, "Neumes rythmiques". De acordo com Messiaen, essa maneira de compor foi "inspirada pelos movimentos da natureza, movimentos de durações livres e desiguais".^[157]

Em seu romance de ficção científica Contact, o cientista Carl Sagan sugeriu que a decomposição em números primos poderia ser usada como um meio de estabelecer planos de imagem bidimensionais em comunicações com alienígenas, uma ideia que ele havia desenvolvido informalmente com o astrônomo americano Frank Drake, em 1975.^[158] No romance The Curious Incident of the Dog in the Night-Time, de Mark Haddon, o narrador organiza as seções da história por números primos consecutivos como forma de transmitir o estado mental de seu personagem principal, um adolescente matematicamente talentoso com síndrome de Asperger.^[159] Os números primos são usados como metáfora para solidão e isolamento no romance The Solitude of Prime Numbers, de Paolo Giordano, no qual são retratados como "forasteiros" entre os números inteiros.^[160]

Notas

1. 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.^[36]
2. 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",^[38] 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.^[39]
3. Neste teste, o termo ± 1 é negativo ser a é um resíduo quadrático do (suposto) primo dado p, senão é positivo. De forma mais geral, para valores não primos de p, o termo ± 1 é a (negação) do símbolo de Jacobi, que pode ser calculado usando a lei da reciprocidade quadrática.
4. De fato, muita da análise da prova de primalidade por curvas elípticas é baseado na suposição que a entrada para o algoritmo já passou por um teste probabilístico.^[114]
5. A função primorial de n, denotada por n#, gera o produto de números primos até n, e um primo primorial é um primo da forma n# ± 1.^[63]
6. Boklan & Conway (2017) também inclui 2⁰ + 1 = 2, que não é dessa forma.

Referências

1. «GIMPS Discovers Largest Known Prime Number: 2^136,279,841 − 1». Mersenne Research, Inc. 21 de outubro de 2024. Consultado em 21 de outubro de 2024
2. Sparkes, Matthew (2 de novembro de 2024). «Amateur sleuth finds largest-known prime number». New Scientist: 19
3. Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996 (em inglês). Oxford, Reino Unido: Oxford University Press. p. 26. ISBN 978-0-19-850105-3
4. Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (em inglês) 2.ª ed. [S.l.]: Routledge. p. 62. ISBN 978-1-136-63662-2
5. Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space (em inglês). [S.l.]: Golden Press. p. 16. OCLC 6975809
6. Leff, Lawrence S. (2000). Math Workbook for the SAT I (em inglês). [S.l.]: Barron's Educational Series. p. 360. ISBN 978-0-7641-0768-9
7. Dudley 1978, Seção 2, p. 10.
8. Sierpiński 1988, p. 113.
9. Ziegler, Günter M. (2004). «The great prime number record races». Notices of the American Mathematical Society (em inglês). 51 (4): 414–416. MR 2039814
10. Stillwell, John (1997). Numbers and Geometry. Col: Undergraduate Texts in Mathematics. [S.l.]: Springer. p. 9. ISBN 978-0-387-98289-2
11. Sierpiński, Wacław (1964). A Selection of Problems in the Theory of Numbers (em inglês). New York: Macmillan. p. 40. MR 0170843
12. Nathanson, Melvyn B. (2000). «Notations and Conventions». Elementary Methods in Number Theory. Col: Graduate Texts in Mathematics (em inglês). 195. [S.l.]: Springer. ISBN 978-0-387-22738-2. MR 1732941
13. Faticoni, Theodore G. (2012). The Mathematics of Infinity: A Guide to Great Ideas. Col: Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts (em inglês). 111 2.ª ed. [S.l.]: John Wiley & Sons. p. 44. ISBN 978-1-118-24382-4
14. Huylebrouck, Dirk (2019). «Missing Link». Africa and Mathematics. Col: Mathematics, Culture, and the Arts. Cham: Springer International Publishing. pp. 153–166. ISBN 978-3-030-04036-9. doi:10.1007/978-3-030-04037-6_9. Consultado em 19 de outubro de 2021
15. Everett, Caleb (2017). Numbers and the Making of Us: Counting and the Course of Human Cultures. [S.l.]: Harvard University Press. pp. 35–36. ISBN 978-0-674-50443-1
16. Neugebauer, Otto (1969). «Babylonian Mathematics». The Exact Sciences In Antiquity 2.ª ed. Nova Iorque, NY, EUA: Dover. ISBN 0-486-22332-9
17. Bruins, Evert Marie, análise em Mathematical Reviews de Gillings, R.J. (1974). «The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it?». Archive for History of Exact Sciences. 12 (4): 291–298. MR 0497458. doi:10.1007/BF01307175
18. «Egyptian Unit Fractions». Mathpages (em inglês). Consultado em 14 de janeiro de 2011
19. du Sautoy, Marcus (2003). The Music of the Primes. Searching to Solve the Greatest Mystery in Mathematics (em inglês) 1.ª ed. Nova Iorque, NY: HarperCollins. pp. 22–23. ISBN 0-06-621070-4
20. Stillwell, John (2010). Mathematics and Its History. Col: Undergraduate Texts in Mathematics 3rd ed. [S.l.]: Springer. p. 40. ISBN 978-1-4419-6052-8
21. Pomerance, Carl (dezembro de 1982). «The Search for Prime Numbers». Scientific American. 247 (6): 136–147. Bibcode:1982SciAm.247f.136P. JSTOR 24966751. doi:10.1038/scientificamerican1282-136
22. Mollin, Richard A. (2002). «A brief history of factoring and primality testing B. C. (before computers)». Mathematics Magazine. 75 (1): 18–29. JSTOR 3219180. MR 2107288. doi:10.2307/3219180
23. O'Connor, John J.; Robertson, Edmund F., «Prime numbers», MacTutor History of Mathematics archive (em inglês), Universidade de St. Andrews, consultado em 7 de agosto de 2024
24. O'Connor, John J.; Robertson, Edmund F., «Abu Ali al-Hasan ibn al-Haytham», MacTutor History of Mathematics archive (em inglês), Universidade de St. Andrews
25. Sandifer 2007, p. 45.
26. Burton, David M. (1980). «Representation of Integers as Sums of Squares». Elementary Numbert Theory (em inglês). Boston, MA, EUA: Allyn and Bacon. ISBN 0-205-06965-7
27. Sandifer, C. Edward (2015). How Euler Did Even More. EUA: Mathematical Association of America. p. 42. ISBN 978-0-88385-584-3. doi:10.5948/978161444519
28. Koshy, Thomas (2002). Elementary Number Theory with Applications. [S.l.]: Academic Press. p. 369. ISBN 978-0-12-421171-1
29. Yuan, Wang (2002). Goldbach Conjecture. Col: Series In Pure Mathematics (em inglês). 4 2.ª ed. Singapura: World Scientific. p. 21. ISBN 978-981-4487-52-8
30. Narkiewicz, Wladyslaw (2000). «1.2 Sum of Reciprocals of Primes». The Development of Prime Number Theory: From Euclid to Hardy and Littlewood. Col: Springer Monographs in Mathematics (em inglês). [S.l.]: Springer. p. 11. ISBN 978-3-540-66289-1
31. Tchebychev, P. (1852). «Mémoire sur les nombres premiers.» (PDF). Journal de mathématiques pures et appliquées. Série 1 (em francês): 366–390. (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
32. Apostol, Tom M. (2000). «A centennial history of the prime number theorem». In: Bambah, R.P.; Dumir, V.C.; Hans-Gill, R.J. Number Theory. Col: Trends in Mathematics (em inglês). Basel: Birkhäuser. pp. 1–14. MR 1764793
33. Apostol, Tom M. (1976). «7. Dirichlet's Theorem on Primes in Arithmetical Progressions». Introduction to Analytic Number Theory (em inglês). New York; Heidelberg: Springer-Verlag. pp. 146–156. MR 0434929
34. Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip (em inglês). [S.l.]: Springer. p. 261. ISBN 978-3-642-18192-4
35. Rosen 2000, p. 342.
36. Cooper, S. Barry; Hodges, Andrew (2016). The Once and Future Turing. [S.l.]: Cambridge University Press. pp. 37–38. ISBN 978-1-107-01083-3
37. Rosen 2000, p. 245.
38. Beiler, Albert H. (1999) [1966]. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains (em inglês). [S.l.]: Dover. p. 2. ISBN 978-0-486-21096-4. OCLC 444171535
39. Katz, Shaul (2004). «Berlin roots – Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem». Science in Context (em inglês). 17 (1–2): 199–234. MR 2089305. doi:10.1017/S0269889704000092
40. Kraft & Washington 2014, p. 7.
41. Bauer, Craig P. (2013). Secret History: The Story of Cryptology. Col: Discrete Mathematics and Its Applications (em inglês). [S.l.]: CRC Press. p. 468. ISBN 978-1-4665-6186-1
42. Klee, Victor; Wagon, Stan (1991). Old and New Unsolved Problems in Plane Geometry and Number Theory. Col: Dolciani mathematical expositions (em inglês). 11. [S.l.]: Cambridge University Press. p. 224. ISBN 978-0-88385-315-3
43. Neale 2017, pp. 18, 47.
44. Caldwell et al. 2012, 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.
45. Tarán, Leonardo (1981). Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary. Col: Philosophia Antiqua : A Series of Monographs on Ancient Philosophy (em inglês). 39. [S.l.]: Brill. pp. 35–38. ISBN 978-90-04-06505-5
46. Caldwell et al. 2012, pp. 7–13. Veja em particular as entradas de Stevin, Brancker, Wallis, e Prestet.
47. Caldwell et al. 2012, p. 15.
48. Caldwell, Chris K.; Xiong, Yeng (2012). «What is the smallest prime?» (PDF). Journal of Integer Sequences. 15 (9): Article 12.9.7. MR 3005530
49. Riesel 1994, p. 36.
50. Conway, John Horton; Guy, Richard K. (1996). The Book of Numbers (em inglês). New York: Copernicus. pp. 129–130. ISBN 978-0-387-97993-9. MR 1411676. doi:10.1007/978-1-4612-4072-3
51. Para a função totiente, veja Sierpiński 1988, p. 245. Para a soma dos divisores, veja Sandifer 2007, p. 59.
52. Weisstein, Eric W. «Prime Factorization». MathWorld (em inglês). Consultado em 14 de outubro de 2024
53. Smith, Karl J. (2011). The Nature of Mathematics 12.ª ed. [S.l.]: Cengage Learning. p. 188. ISBN 978-0-538-73758-6
54. Dudley 1978, Seção 2, Teorema 2, p. 16.
55. Neale, Vicky (2017). Closing the Gap: The Quest to Understand Prime Numbers. [S.l.]: Oxford University Press. p. 107. ISBN 978-0-19-109243-5
56. Nobre, Thiago Braga (29 de dezembro de 2022). «Números primos: nova abordagem na decomposição de um produto». Revista ft (117): 33–34. doi:10.69849/revistaft/ma10202212291733. Consultado em 14 de outubro de 2024
57. du Sautoy, Marcus (2003). The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. [S.l.]: Harper Collins. p. 23. ISBN 978-0-06-093558-0
58. Dudley 1978, Seção 2, Lema 5, p. 15.
59. Higgins, Peter M. (1998). Mathematics for the Curious. [S.l.]: Oxford University Press. pp. 77–78. ISBN 978-0-19-150050-3
60. Rotman, Joseph J. (2000). A First Course in Abstract Algebra (em inglês) 2.ª ed. [S.l.]: Prentice Hall. Problema 1.40, p. 56. ISBN 978-0-13-011584-3
61. Goldbach, Christian (julho de 1730). «Lettre VIII» (PDF). In: Fuss, Paul Heinrich. Correspondance mathématique et physique de quelques célèbres géomètres du XVIIIème siècle (em francês e latim). [S.l.: s.n.] (publicado em 12 de janeiro de 1845). pp. 32–34
62. Furstenberg, Harry (1955). «On the infinitude of primes». American Mathematical Monthly. 62 (5). 353 páginas. JSTOR 2307043. MR 0068566. doi:10.2307/2307043
63. Ribenboim 2004, p. 4.
64. Os Elementos de Euclides, Livro IX, Proposição 20
65. Hefez, Abramo (2006). Elementos de Aritmética 2.ª ed. Rio de Janeiro, RJ: Sociedade Brasileira de Matemática. Teorema 7.2.1, p. 88
66. Vardi, Ilan (1991). Computational Recreations in Mathematica (em inglês). [S.l.]: Addison-Wesley. pp. 82–89. ISBN 978-0-201-52989-0
67. Weisstein, Eric W. «Euclid Number». MathWorld (em inglês). Consultado em 17 de outubro de 2024
68. Wilf, Herbert S. (1982). «What is an answer?». The American Mathematical Monthly (em inglês). 89 (5): 289–292. JSTOR 2321713. MR 653502. doi:10.2307/2321713
69. Matiyasevich, Yuri V. (1999). «Formulas for prime numbers». In: Tabachnikov, Serge. Kvant Selecta: Algebra and Analysis (em inglês). II. [S.l.]: American Mathematical Society. pp. 13–24. ISBN 978-0-8218-1915-9
70. Mackinnon, Nick (junho de 1987). «Prime number formulae». The Mathematical Gazette (em inglês). 71 (456): 113–114. JSTOR 3616496. doi:10.2307/3616496
71. Willans, C. P. (dezembro de 1964). «On formulae for the ${\displaystyle n}$th prime number». The Mathematical Gazette (em inglês). 48 (366): 413–415. JSTOR 3611701. doi:10.2307/3611701
72. Dudley, Underwood (1983). «Formulas for primes». Mathematics Magazine (em inglês). 56 (1): 17–22. JSTOR 2690261. MR 692169. doi:10.2307/2690261
73. Wright, E.M. (1951). «A prime-representing function». American Mathematical Monthly (em inglês). 58 (9): 616–618. JSTOR 2306356. doi:10.2307/2306356
74. Guy 2013, p. vii.
75. Guy 2013, C1 Goldbach's conjecture, pp. 105–107.
76. Oliveira e Silva, Tomás; Herzog, Siegfried; Pardi, Silvio (2014). «Empirical verification of the even Goldbach conjecture and computation of prime gaps up to ${\displaystyle 4\cdot 10^{18}}$». Mathematics of Computation (em inglês). 83 (288): 2033–2060. MR 3194140. doi:10.1090/S0025-5718-2013-02787-1
77. Tao 2009, 3.1 Structure and randomness in the prime numbers, pp. 239–247. Ver especificamente p. 239.
78. Guy 2013, p. 159.
79. Ramaré, Olivier (1995). «On Šnirel'man's constant». Annali della Scuola Normale Superiore di Pisa (em inglês). 22 (4): 645–706. MR 1375315. Consultado em 23 de janeiro de 2018. Arquivado do original em 9 de fevereiro de 2022
80. Rassias, Michael Th. (2017). Goldbach's Problem: Selected Topics (em inglês). Cham: Springer. p. vii. ISBN 978-3-319-57912-2. MR 3674356. doi:10.1007/978-3-319-57914-6
81. Koshy 2002, Teorema 2.14, p. 109. Riesel 1994 dá um argumento semelhante, porém utilizando primorial em vez de fatorial.
82. Riesel 1994, "Large gaps between consecutive primes", pp. 78–79.
83. Sloane, N. J. A. (ed.). «Sequência A100964 (Smallest prime number that begins a prime gap of at least 2n)». On-Line Encyclopedia of Integer Sequences (em inglês). OEIS Foundation
84. Ribenboim 2004, Gaps between primes, pp. 186–192.
85. Ribenboim 2004, p. 183.
86. Chan, Joel (fevereiro de 1996). «Prime time!». Math Horizons. 3 (3): 23–25. JSTOR 25678057. doi:10.1080/10724117.1996.11974965
    Note que Chan lista a conjectura de Legendre como "Sierpinski's Postulate" (Postulado de Sierpinski).
87. Ribenboim 2004, Prime k-tuples conjecture, pp. 201–202.
88. Conforme cálculo feito pelo Wolfram Alpha.
89. Conforme cálculo feito pelo Wolfram Alpha.
90. Hua (2009), p. 176-177"
91. Ver lista dos valores, calculada pelo Wolfram Alpha
92. Ernest Cesàro (1894). «Sur une formule empirique de M. Pervouchine». Comptes rendus hebdomadaires des séances de l'Académie des sciences. 119: 848–849 (em francês)
93. Eric Bach, Jeffrey Shallit (1996). Algorithmic Number Theory. 1. [S.l.]: MIT Press. p. 233. ISBN 0-262-02405-5
94. Pierre Dusart (1999). «The kth prime is greater than k(ln k + ln ln k-1) for k>=2» (PDF). Mathematics of Computation. 68: 411–415
95. Bryant, John; Sangwin, Christopher J. (2008). How Round is Your Circle?: Where Engineering and Mathematics Meet. [S.l.]: Princeton University Press. p. 178. ISBN 978-0-691-13118-4
96. Hardy, Godfrey Harold (2012) [1940]. A Mathematician's Apology. [S.l.]: Cambridge University Press. p. 140. ISBN 978-0-521-42706-7. OCLC 922010634. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.
97. Giblin 1993, p. 39.
98. Weisstein, Eric W. «Primality Test». MathWorld (em inglês). Consultado em 15 de agosto de 2025
99. Kirtland, Joseph (2001). Identification Numbers and Check Digit Schemes. Col: Classroom Resource Materials. 18. [S.l.]: Mathematical Association of America. pp. 43–44. ISBN 978-0-88385-720-5
100. Goodrich, Michael T.; Tamassia, Roberto (2006). Data Structures & Algorithms in Java 4.ª ed. [S.l.]: John Wiley & Sons. ISBN 978-0-471-73884-8 Ver "Quadratic probing", p. 382, e exercício C–9.9, p. 415.
101. Knuth, Donald E. (1998). «3.2.1 The linear congruential model». The Art of Computer Programming, Vol. 2: Seminumerical algorithms 3rd ed. [S.l.]: Addison-Wesley. pp. 10–26. ISBN 978-0-201-89684-8
102. Matsumoto, Makoto; Nishimura, Takuji (1998). «Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995
103. Giblin 1993, p. 54.
104. Riesel 1994, p. 220.
105. Bullynck, Maarten (2010). «A history of factor tables with notes on the birth of number theory 1657–1817». Revue d'Histoire des Mathématiques. 16 (2): 133–216
106. Wagstaff, Samuel S. Jr. (2013). The Joy of Factoring. Col: Student mathematical library. 68. [S.l.]: American Mathematical Society. p. 191. ISBN 978-1-4704-1048-3
107. Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: A Computational Perspective 2nd ed. [S.l.]: Springer. p. 121. ISBN 978-0-387-25282-7
108. Farach-Colton, Martín; Tsai, Meng-Tsung (2015). «On the complexity of computing prime tables». In: Elbassioni, Khaled; Makino, Kazuhisa. Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings. Lecture Notes in Computer Science. 9472. Springer. pp. 677–688. ISBN 978-3-662-48970-3. arXiv:1504.05240. doi:10.1007/978-3-662-48971-0_57
109. Greaves, George (2013). Sieves in Number Theory. Col: Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). 43. [S.l.]: Springer. p. 1. ISBN 978-3-662-04658-6
110. Hromkovič, Juraj (2001). «5.5 Bibliographic Remarks». Algorithmics for Hard Problems. Col: Texts in Theoretical Computer Science. An EATCS Series. [S.l.]: Springer-Verlag, Berlin. pp. 383–385. ISBN 978-3-540-66860-2. MR 1843669. doi:10.1007/978-3-662-04616-6
111. Koblitz, Neal (1987). «Chapter V. Primality and Factoring». A Course in Number Theory and Cryptography. Col: Graduate Texts in Mathematics. 114. [S.l.]: Springer-Verlag, New York. pp. 112–149. ISBN 978-0-387-96576-5. MR 910297. doi:10.1007/978-1-4684-0310-7_5
112. Pieprzyk, Josef; Hardjono, Thomas; Seberry, Jennifer (2013). «2.3.9 Probabilistic Computations». Fundamentals of Computer Security. [S.l.]: Springer. pp. 51–52. ISBN 978-3-662-07324-7
113. Tao, Terence (2010). «1.11 The AKS primality test». An epsilon of room, II: Pages from year three of a mathematical blog. Col: Graduate Studies in Mathematics. 117. Providence, RI: American Mathematical Society. pp. 82–86. ISBN 978-0-8218-5280-4. MR 2780010. doi:10.1090/gsm/117
114. Atkin, A O.L.; Morain, F. (1993). «Elliptic curves and primality proving» (PDF). Mathematics of Computation. 61 (203): 29–68. Bibcode:1993MaCom..61...29A. JSTOR 2152935. MR 1199989. doi:10.1090/s0025-5718-1993-1199989-x
115. Morain, F. (2007). «Implementing the asymptotically fast version of the elliptic curve primality proving algorithm». Mathematics of Computation. 76 (257): 493–505. Bibcode:2007MaCom..76..493M. MR 2261033. arXiv:math/0502097. doi:10.1090/S0025-5718-06-01890-4
116. Lenstra, H. W. Jr.; Pomerance, Carl (2019). «Primality testing with Gaussian periods» (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. MR 3941463. doi:10.4171/JEMS/861. hdl:21.11116/0000-0005-717D-0
117. Pomerance, Carl; Selfridge, John L.; Wagstaff, Jr., Samuel S. (julho de 1980). «The pseudoprimes to 25·10⁹» (PDF). Mathematics of Computation. 35 (151): 1003–1026. JSTOR 2006210. doi:10.1090/S0025-5718-1980-0572872-7
118. Baillie, Robert; Wagstaff, Jr., Samuel S. (outubro de 1980). «Lucas Pseudoprimes» (PDF). Mathematics of Computation. 35 (152): 1391–1417. JSTOR 2006406. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6
119. Monier, Louis (1980). «Evaluation and comparison of two efficient probabilistic primality testing algorithms». Theoretical Computer Science. 12 (1): 97–108. MR 582244. doi:10.1016/0304-3975(80)90007-9
120. Tao, Terence (2009). «1.7 The Lucas–Lehmer test for Mersenne primes». Poincaré's legacies, pages from year two of a mathematical blog. Part I. Providence, RI: American Mathematical Society. pp. 36–41. ISBN 978-0-8218-4883-8. MR 2523047
121. Kraft & Washington 2014, p. 41.
122. Ver, por exemplo, Guy 2013, pp. A3 Mersenne primes. Repunits. Fermat numbers. Primes of shape ${\displaystyle k\cdot 2^{n}+1}$. 13–21
123. «Record 12-Million-Digit Prime Number Nets $100,000 Prize». Electronic Frontier Foundation. 14 de outubro de 2009. Consultado em 4 de janeiro de 2010
124. «EFF Cooperative Computing Awards». Electronic Frontier Foundation. 29 de fevereiro de 2008. Consultado em 4 de janeiro de 2010
125. «PrimeGrid's Seventeen or Bust Subproject» (PDF). Consultado em 3 de janeiro de 2017
126. Caldwell, Chris K. «The Top Twenty: Largest Known Primes». The Prime Pages. Consultado em 3 de janeiro de 2017
127. Caldwell, Chris K. «The Top Twenty: Factorial». The Prime Pages. Consultado em 3 de janeiro de 2017
128. Caldwell, Chris K. «The Top Twenty: Primorial». The Prime Pages. Consultado em 3 de janeiro de 2017
129. Caldwell, Chris K. «The Top Twenty: Twin Primes». The Prime Pages. Consultado em 3 de janeiro de 2017
130. Kraft & Washington 2014, p. 275.
131. Hoffstein, Pipher & Silverman 2014, p. 329.
132. Pomerance, Carl (1996). «A tale of two sieves». Notices of the American Mathematical Society. 43 (12): 1473–1485. MR 1416721
133. Thomé, Emmanuel (2 de dezembro de 2019). «795-bit factoring and discrete logarithms». LISTSERV Archives
134. Rieffel, Eleanor G.; Polak, Wolfgang H. (2011). «Chapter 8. Shor's Algorithm». Quantum Computing: A Gentle Introduction. [S.l.]: MIT Press. pp. 163–176. ISBN 978-0-262-01506-6
135. Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 de outubro de 2012). «Experimental realization of Shor's quantum factoring algorithm using qubit recycling». Nature Photonics. 6 (11): 773–776. Bibcode:2012NaPho...6..773M. arXiv:1111.4147. doi:10.1038/nphoton.2012.259
136. Chirgwin, Richard (9 de outubro de 2016). «Crypto needs more transparency, researchers warn». The Register
137. Hoffstein, Pipher & Silverman 2014, Seção 2.3, Diffie–Hellman key exchange, pp. 65–67.
138. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. «11.3 Universal hashing». Introduction to Algorithms 2.ª ed. [S.l.]: MIT Press and McGraw-Hill. pp. 232–236. ISBN 0-262-03293-7 Para hashing k-independente ver problema 11–4, p. 251. Para os créditos de Carter e Wegman, ver as notas do capítulo, p. 252.
139. Deutsch, P. (maio de 1996). ZLIB Compressed Data Format Specification version 3.3. Network Working Group. doi:10.17487/RFC1950. Request for Comments 1950
140. Roth, Klaus F. (1951). «On a problem of Heilbronn». Journal of the London Mathematical Society. Second Series. 26 (3): 198–204. MR 0041889. doi:10.1112/jlms/s1-26.3.198
141. Cox, David A. (2011). «Why Eisenstein proved the Eisenstein criterion and why Schönemann discovered it first» (PDF). American Mathematical Monthly. 118 (1): 3–31. CiteSeerX 10.1.1.398.3440. doi:10.4169/amer.math.monthly.118.01.003. Consultado em 25 de janeiro de 2018. Arquivado do original (PDF) em 26 de março de 2023
142. Lang, Serge (2002). Algebra. Col: Graduate Texts in Mathematics. 211. Berlin, Germany; New York: Springer-Verlag. Seção II.1, p. 90. ISBN 978-0-387-95385-4. MR 1878556. doi:10.1007/978-1-4613-0041-0
143. Schubert, Horst (1949). «Die eindeutige Zerlegbarkeit eines Knotens in Primknoten». S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (3): 57–104. MR 0031733
144. Milnor, J. (1962). «A unique decomposition theorem for 3-manifolds». American Journal of Mathematics. 84 (1): 1–7. JSTOR 2372800. MR 0142125. doi:10.2307/2372800
145. Peterson, Ivars (28 de junho de 1999). «The Return of Zeta». MAA Online. Consultado em 14 de março de 2008. Arquivado do original em 20 de outubro de 2007
146. Hayes, Brian (2003). «Computing science: The spectrum of Riemannium». American Scientist. 91 (4): 296–300. JSTOR 27858239. doi:10.1511/2003.26.3349
147. Goles, E.; Schulz, O.; Markus, M. (2001). «Prime number selection of cycles in a predator-prey model». Complexity. 6 (4): 33–38. Bibcode:2001Cmplx...6d..33G. doi:10.1002/cplx.1040
148. Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry. Col: CMS Books in Mathematics. 9. New York: Springer-Verlag. pp. 1–2. ISBN 978-0-387-95332-8. MR 1866957. doi:10.1007/978-0-387-21850-2
149. Boklan, Kent D.; Conway, John H. (janeiro de 2017). «Expect at most one billionth of a new Fermat prime!». The Mathematical Intelligencer. 39 (1): 3–5. arXiv:1605.01371. doi:10.1007/s00283-016-9644-3
150. Gleason, Andrew M. (1988). «Angle trisection, the heptagon, and the triskaidecagon». American Mathematical Monthly. 95 (3): 185–194. JSTOR 2323624. MR 935432. doi:10.2307/2323624
151. Ziegler, Günter M. (2015). «Cannons at sparrows». European Mathematical Society Newsletter (95): 25–31. MR 3330472
152. Bengtsson, Ingemar; Życzkowski, Karol (2017). Geometry of quantum states: an introduction to quantum entanglement Second ed. Cambridge: Cambridge University Press. pp. 313–354. ISBN 978-1-107-02625-4. OCLC 967938939
153. Zhu, Huangjun (2010). «SIC POVMs and Clifford groups in prime dimensions». Journal of Physics A: Mathematical and Theoretical. 43 (30). 305305 páginas. Bibcode:2010JPhA...43D5305Z. arXiv:1003.3591. doi:10.1088/1751-8113/43/30/305305
154. Campos, Paulo R. A.; de Oliveira, Viviane M.; Giro, Ronaldo; Galvão, Douglas S. (2004). «Emergence of prime numbers as the result of evolutionary strategy». Physical Review Letters. 93 (9): 098107. Bibcode:2004PhRvL..93i8107C. PMID 15447148. arXiv:q-bio/0406017. doi:10.1103/PhysRevLett.93.098107
155. «Invasion of the Brood». The Economist. 6 de maio de 2004. Consultado em 26 de novembro de 2006
156. Zimmer, Carl (15 de maio de 2015). «Bamboo Mathematicians». Phenomena: The Loom. National Geographic. Consultado em 22 de fevereiro de 2018
157. Hill, Peter Jensen, ed. (1995). The Messiaen companion. Portland, OR: Amadeus Press. Ex. 13.2 Messe de la Pentecôte 1 'Entrée'. ISBN 978-0-931340-95-6
158. Pomerance, Carl (2004). «Prime Numbers and the Search for Extraterrestrial Intelligence» (PDF). In: Hayes, David F.; Ross, Peter. Mathematical Adventures for Students and Amateurs. Col: MAA Spectrum. Washington, DC: Mathematical Association of America. pp. 3–6. ISBN 978-0-88385-548-5. MR 2085842
159. GrrlScientist (16 de setembro de 2010). «The Curious Incident of the Dog in the Night-Time». Science. The Guardian. Consultado em 22 de fevereiro de 2010
160. Schillinger, Liesl (9 de abril de 2010). «Counting on Each Other». Sunday Book Review. The New York Times

Bibliografia

• Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). «The history of the primality of one: a selection of sources». Journal of Integer Sequences (em inglês). 15 (9). MR 3005523
• Dudley, Underwood (1978). Elementary number theory (em inglês) 2.ª ed. [S.l.]: W.H. Freeman and Co. ISBN 978-0-7167-0076-0
• Giblin, Peter (1993). Primes and Programming (em inglês). [S.l.]: Cambridge University Press. ISBN 978-0-521-40988-9
• Guy, Richard (2013). «A1 Prime values of quadratic functions». Unsolved Problems in Number Theory. Col: Problem Books in Mathematics (em inglês) 3.ª ed. [S.l.]: Springer. ISBN 978-0-387-26677-0
• Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (2014). An Introduction to Mathematical Cryptography. Col: Undergraduate Texts in Mathematics (em inglês) 2.ª ed. [S.l.]: Springer. p. 329. ISBN 978-1-4939-1711-2
• Kraft, James S.; Washington, Lawrence C. (2014). Elementary Number Theory. Col: Textbooks in mathematics (em inglês). [S.l.]: CRC Press. p. 7. ISBN 978-1-4987-0269-0
• Neale, Vicky (2017). Closing the Gap: The Quest to Understand Prime Numbers (em inglês). [S.l.]: Oxford University Press. ISBN 978-0-19-109243-5
• Ribenboim, Paulo (2004). The little book of bigger primes (em inglês). Berlim; Nova Iorque: Springer-Verlag. ISBN 978-0-387-20169-6
• Rosen, Kenneth H. (2000). «Theorem 9.20. Proth's Primality Test». Elementary Number Theory and Its Applications (em inglês) 4.ª ed. [S.l.]: Addison-Wesley. ISBN 978-0-201-87073-2
• Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization (em inglês) 2.ª ed. Basel, Switzerland: Birkhäuser. ISBN 978-0-8176-3743-9. MR 1292250. doi:10.1007/978-1-4612-0251-6
• Sandifer, C. Edward (2007). How Euler Did It. Col: MAA Spectrum. EUA: Mathematical Association of America. ISBN 978-0-88385-563-8. doi:10.1090/spec/052
• Sierpiński, Wacław (1988). Elementary Theory of Numbers. Col: North-Holland Mathematical Library (em inglês). 31 2.ª ed. [S.l.]: Elsevier. ISBN 978-0-08-096019-7
• Tao, Terence (2009). Poincaré's legacies, pages from year two of a mathematical blog. Part I. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4883-8. MR 2523047