Número primo - Prime number

Grupos de dois a doze pontos, mostrando que os números compostos de pontos (4, 6, 8, 9, 10 e 12) podem ser organizados em retângulos, mas os números primos não podem
Os números compostos podem ser organizados em retângulos, mas os números primos não podem

Um número primo (ou primo ) é um número natural maior que 1 que não é produto de dois números 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 ) em que ambos os números são menores do que 4. Os primos são centrais na teoria dos números por causa do teorema fundamental da aritmética : todo número natural maior do que 1 é um primo ou pode ser fatoradocomo um produto de números primos que é exclusivo de acordo com seu pedido.

A propriedade de ser primo é chamada de primalidade . Um método simples, mas lento, de verificar a primalidade de um determinado número , denominado divisão experimental , testa se é um múltiplo de qualquer inteiro entre 2 e . Algoritmos mais rápidos incluem o teste de primalidade de Miller – Rabin , que é rápido, mas tem uma pequena chance de erro, e o teste de primalidade AKS , que sempre produz a resposta correta em tempo polinomial, mas é muito lento para ser prático. Métodos particularmente rápidos estão disponíveis para números de formas especiais, como números de Mersenne . Em dezembro de 2018, o maior número primo conhecido é um primo de Mersenne com 24.862.048 dígitos decimais .

Existem infinitos primos, como demonstrado por Euclides por volta de 300 AC. Nenhuma fórmula simples conhecida separa os números primos dos números compostos. No entanto, a distribuição dos primos dentro dos números naturais no grande pode ser modelada estatisticamente. O primeiro resultado nessa direção é o teorema dos números primos , comprovado no final do século 19, que diz que a probabilidade de um grande número escolhido aleatoriamente ser primo é inversamente proporcional ao seu número de dígitos, ou seja, ao seu logaritmo .

Várias questões históricas relacionadas aos números primos ainda não foram resolvidas. Isso inclui a conjectura de Goldbach , de que todo número par maior do que 2 pode ser expresso como a soma de dois primos, e a conjectura de dois primos gêmeos , de que há infinitos pares de primos tendo apenas um número par entre eles. Essas questões estimularam o desenvolvimento de vários ramos da teoria dos números, com foco nos aspectos analíticos ou algébricos dos números. Os números primos são usados ​​em várias rotinas de tecnologia da informação , como a criptografia de chave pública , que depende da dificuldade de fatorar grandes números em seus fatores primos. Na álgebra abstrata , os objetos que se comportam de maneira generalizada como os números primos incluem elementos primos e ideais primos .

Definição e exemplos

Um número natural (1, 2, 3, 4, 5, 6, etc.) é chamado de número primo (ou primo ) se for 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 . Em outras palavras, é principal se os itens não puderem ser divididos em grupos menores de igual tamanho de mais de um item, ou se não for possível organizar os pontos em uma grade retangular com mais de um ponto de largura e mais de um ponto de altura . Por exemplo, entre os números de 1 a 6, os números 2, 3 e 5 são os números primos, pois não há outros números que os dividam igualmente (sem resto). 1 não é primo, pois está especificamente excluído na definição. 4 = 2 × 2 e 6 = 2 × 3 são ambos compostos.

Demonstração, com hastes Cuisenaire, que 7 é primo, porque nenhum de 2, 3, 4, 5 ou 6 o divide uniformemente
Demonstração, com hastes Cuisenaire , que 7 é primo, porque nenhum de 2, 3, 4, 5 ou 6 o divide uniformemente

Os divisores de um número natural são os números naturais que se dividem uniformemente. Todo número natural tem 1 e a si mesmo como divisor. Se tiver qualquer outro divisor, não pode ser primo. Essa ideia leva a uma definição diferente, mas equivalente, dos primos: eles são os números com exatamente dois divisores positivos , 1 e o próprio número. Outra maneira de expressar a mesma coisa é que um número é primo se for maior que um e se nenhum dos números se dividir igualmente.

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

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 ( sequência A000040 no OEIS ).

Nenhum número par maior que 2 é primo porque qualquer um desses números pode ser expresso como o produto . Portanto, todo número primo diferente de 2 é um número ímpar e é chamado de primo ímpar . Da mesma forma, quando escritos 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 outros dígitos são todos compostos: números decimais que terminam em 0, 2, 4, 6 , ou 8 são pares e os números decimais que terminam em 0 ou 5 são divisíveis por 5.

O conjunto de todos os primos às vezes é denotado por (um negrito maiúsculo P ) ou por (um quadro negro maiúsculo P).

História

O Rhind Mathematical Papyrus , de cerca de 1550 AC, tem expansões de fração egípcia de diferentes formas para números primos e compostos. No entanto, os primeiros registros sobreviventes do estudo explícito dos números primos vêm da matemática grega antiga . Euclides 's Elements (c. 300 aC) comprova a infinitude dos números primos e o teorema fundamental da aritmética , e mostra como construir um número perfeito de um primo de Mersenne . Outra invenção grega, a peneira de Eratóstenes , ainda é usada para construir listas de primos.

Por volta de 1000 DC, o matemático islâmico Ibn al-Haytham (Alhazen) encontrou o teorema de Wilson , caracterizando os números primos como os números que se dividem uniformemente . Ele também conjeturou que todos os números pares perfeitos vêm da construção de Euclides usando primos de Mersenne, mas não foi capaz de prová-lo. Outro matemático islâmico, Ibn al-Banna 'al-Marrakushi , observou que a peneira de Eratóstenes pode ser acelerada testando apenas os divisores até a raiz quadrada do maior número a ser testado. Fibonacci trouxe as inovações da matemática islâmica de volta à Europa. Seu livro Liber Abaci (1202) foi o primeiro a descrever a divisão de teste para testar a primalidade, novamente usando divisores apenas até a raiz quadrada.

Em 1640, Pierre de Fermat afirmou (sem prova) o pequeno teorema de Fermat (mais tarde provado por Leibniz e Euler ). Fermat também investigou a primalidade dos números de Fermat , e Marin Mersenne estudou os primos de Mersenne , números primos da forma em que ele próprio é primo. Christian Goldbach formulou a conjectura de Goldbach , de que todo número par é a soma de dois primos, em uma carta de 1742 a Euler. Euler provou a conjectura de Alhazen (agora o teorema de Euclides-Euler ) de que todos os números pares perfeitos podem ser construídos a partir dos primos de Mersenne. Ele introduziu métodos de análise matemática a essa área em suas provas da infinitude dos primos e da divergência da soma dos recíprocos dos primos . No início do século XIX, Legendre e Gauss conjeturavam que, conforme tende ao infinito, o número de primos até é assintótico a , onde está o logaritmo natural de . Uma consequência mais fraca dessa alta densidade de primos foi o postulado de Bertrand , de que para cada há um primo entre e , provado em 1852 por Pafnuty Chebyshev . As idéias de Bernhard Riemann em seu artigo de 1859 sobre a função zeta esboçaram um esboço para provar a conjectura de Legendre e Gauss. Embora a hipótese de Riemann intimamente relacionada permaneça sem comprovação, o esboço de Riemann foi concluído em 1896 por Hadamard e de la Vallée Poussin , e o resultado agora é conhecido como o teorema dos números primos . Outro resultado importante do século 19 foi o teorema de Dirichlet sobre progressões aritméticas , de que certas progressões aritméticas contêm infinitos primos.

Muitos matemáticos trabalharam em testes de primalidade para números maiores do que aqueles em que a divisão experimental é praticável. Métodos que são restritos a formas de número específicas incluem o teste de Pépin para números de Fermat (1877), o teorema de Proth (c. 1878), o teste de primalidade de Lucas-Lehmer (originado em 1856) e o teste de primalidade generalizado de Lucas .

Desde 1951, todos os maiores primos conhecidos foram encontrados usando esses testes em computadores . A busca por números primos cada vez maiores gerou interesse fora dos círculos matemáticos, por meio da Great Internet Mersenne Prime Search e outros projetos de computação distribuída . A ideia de que os números primos tinham poucas aplicações fora da matemática pura foi destruída na década de 1970, quando a criptografia de chave pública e o criptosistema RSA foram inventados, usando os números primos como base.

A crescente importância prática dos testes de primalidade computadorizados e da fatoração levou ao desenvolvimento de métodos aprimorados, capazes de lidar com um grande número de formas irrestritas. A teoria matemática dos números primos também avançou com o teorema de Green-Tao (2004) de que existem progressões aritméticas arbitrariamente longas dos números primos, e a prova de Yitang Zhang de 2013 de que existem infinitas lacunas primos de tamanho limitado.

Primalidade de um

A maioria dos primeiros gregos nem mesmo considerava 1 como um número, portanto não podiam considerar sua primalidade. Alguns matemáticos dessa época também consideraram os números primos como uma subdivisão dos números ímpares, portanto também não consideraram 2 como primos. No entanto, Euclides e a maioria dos outros matemáticos gregos consideraram 2 como primo. Os matemáticos islâmicos medievais seguiram amplamente os gregos ao ver 1 como não sendo um número. Na Idade Média e na Renascença, os matemáticos começaram a tratar 1 como um número e alguns deles o incluíram como o primeiro número primo. Em meados do século 18, Christian Goldbach listou 1 como primeiro em sua correspondência com Leonhard Euler ; no entanto, o próprio Euler não considerou 1 como primo. No século 19, muitos matemáticos ainda consideravam 1 como primo, e as listas de primos que incluíam 1 continuaram a ser publicadas até 1956.

Se a definição de um número primo fosse alterada para chamar 1 de primo, muitas afirmações envolvendo números primos precisariam ser reformuladas de uma maneira mais estranha. Por exemplo, o teorema fundamental da aritmética precisaria ser reformulado em termos de fatorações em números primos maiores que 1, porque cada número teria várias fatorações com diferentes números de cópias de 1. Da mesma forma, a peneira de Eratóstenes não funcionaria corretamente se tratou 1 como primo, porque eliminaria todos os múltiplos de 1 (ou seja, todos os outros números) e produziria apenas o único número 1. Algumas outras propriedades mais técnicas dos números primos também não valem para o número 1: por exemplo, as fórmulas para a função totiente de Euler ou para a função da soma dos divisores são diferentes para os números primos do que para 1. No início do século 20, os matemáticos começaram a concordar que 1 não deveria ser listado como primo, mas sim em sua própria categoria especial como uma " unidade ".

Propriedades elementares

Fatoração única

Escrever um número como produto de números primos é chamado de fatoração primo do número. Por exemplo:

Os termos do produto são chamados de fatores principais . O mesmo fator principal pode ocorrer mais de uma vez; este exemplo tem duas cópias do fator primo Quando um primo ocorre várias vezes, a exponenciação pode ser usada para agrupar várias cópias do mesmo número primo: por exemplo, na segunda forma de escrever o produto acima, denota o quadrado ou segunda potência de

A importância central dos números primos para a teoria dos números e a matemática em geral deriva do teorema fundamental da aritmética . Este teorema afirma que todo inteiro maior que 1 pode ser escrito como produto de um ou mais primos. Mais fortemente, este produto é único no sentido de que quaisquer duas fatorações primos do mesmo número terão o mesmo número de cópias dos mesmos primos, embora sua ordem possa ser diferente. Portanto, embora existam muitas maneiras diferentes de encontrar uma fatoração usando um algoritmo de fatoração de número inteiro , todas elas devem produzir o mesmo resultado. Os primos podem, portanto, ser considerados os "blocos de construção básicos" dos números naturais.

Algumas provas da singularidade das fatorações primos são baseadas no lema de Euclides : Se é um número primo e divide um produto de inteiros e então divide ou divide (ou ambos). Por outro lado, se um número tem a propriedade de que, ao dividir um produto, sempre divide pelo menos um fator do produto, então deve ser primo.

Infinitude

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

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

de números primos nunca termina. Esta afirmação é conhecida como teorema de Euclides em homenagem ao antigo matemático grego Euclides , uma vez que a primeira prova conhecida para esta afirmação é atribuída a ele. Muitas outras provas da infinitude de primos são conhecidas, incluindo uma prova analítica de Euler , a prova de Goldbach baseada em números de Fermat , a prova de Furstenberg usando topologia geral e a prova elegante de Kummer .

A prova de Euclides mostra que toda lista finita de primos é incompleta. A ideia chaveéa multiplicação dos números primos em qualquer lista e adicionar Se a lista consistir em números primos isto dá o número

Pelo teorema fundamental, tem uma fatoração primária

com um ou mais fatores primos. é igualmente divisível por cada um desses fatores, mas tem o resto de um quando dividido por qualquer um dos números primos na lista fornecida, portanto, nenhum dos fatores primos de pode estar na lista fornecida. Como não há uma lista finita de todos os primos, deve haver um número infinito de primos.

Os números formados pela adição de um aos produtos dos menores primos são chamados de números de Euclides . Os primeiros cinco deles são primos, mas o sexto,

é um número composto.

Fórmulas para números primos

Não existe uma fórmula eficiente conhecida para os primos. Por exemplo, não há polinômio não constante , mesmo em várias variáveis, que leva apenas valores primos. No entanto, existem inúmeras expressões que codificam todos os primos, ou apenas primos. Uma fórmula possível é baseada no teorema de Wilson e gera o número 2 muitas vezes e todos os outros primos exatamente uma vez. Existe 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 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.

Outros exemplos de fórmulas geradoras de primos vêm do teorema de Mills e de um teorema de Wright . Estes afirmam que existem constantes reais e tais que

são primos para qualquer número natural na primeira fórmula e qualquer número de expoentes na segunda fórmula. Aqui representa a função de base , o maior inteiro menor ou igual ao número em questão. No entanto, eles não são úteis para gerar números primos, já que os números primos devem ser gerados primeiro para calcular os valores de ou

Perguntas abertas

Muitas conjecturas girando em torno dos primos foram feitas. Muitas vezes tendo uma formulação elementar, muitas dessas conjecturas resistiram à prova por décadas: todos os quatro problemas de Landau de 1912 ainda não foram resolvidos. Um deles é a conjectura de Goldbach , que afirma que todo número par maior que 2 pode ser escrito como uma soma de dois primos. A partir de 2014, essa conjectura foi verificada para todos os números até declarações mais fracas do que isso foram provadas, por exemplo, o teorema de Vinogradov diz que todo inteiro ímpar suficientemente grande pode ser escrito como uma soma de três primos. O teorema de Chen diz que todo número par suficientemente grande pode ser expresso como a soma de um primo e um semiprimo (o produto de dois primos). Além disso, qualquer número inteiro par maior que 10 pode ser escrito como a soma de seis primos. O ramo da teoria dos números que estuda essas questões é chamado de teoria aditiva dos números .

Outro tipo de problema diz respeito às lacunas dos primos , as diferenças entre os primos consecutivos. A existência de intervalos primos arbitrariamente grandes pode ser vista observando que a sequência consiste em números compostos, para qualquer número natural. No entanto, intervalos primos grandes ocorrem muito antes do que este argumento mostra. Por exemplo, a primeira lacuna primo de comprimento 8 está entre os primos 89 e 97, muito menor do que. Presume-se que haja infinitos primos gêmeos , pares de primos com diferença 2; esta é a conjectura do primeiro gêmeo . A conjectura de Polignac estados mais geral que, para cada inteiro positivo existem infinitos pares de primos consecutivos que diferem por conjectura de Andrica , conjectura de Brocard , Conjectura de Legendre , e conjectura de Oppermann , tudo sugere que as maiores lacunas entre primos de que deve ser, no máximo, cerca de resultado isso é conhecido por seguir a hipótese de Riemann, enquanto a conjectura de Cramér muito mais forte define o maior tamanho de lacuna em lacunas Prime pode ser generalizado para -tuples primos , padrões nas diferenças entre mais de dois números primos. Sua infinitude e densidade são o assunto da primeira conjectura de Hardy-Littlewood , que pode ser motivada pela heurística de que os números primos se comportam de maneira semelhante a uma sequência aleatória de números com densidade dada pelo teorema dos números primos.

Propriedades analíticas

A teoria analítica dos números estuda a teoria dos números através das lentes de funções contínuas , limites , séries infinitas e a matemática relacionada do infinito e do infinitesimal .

Esta área de estudo começou com Leonhard Euler e seu primeiro grande resultado, a solução para o problema de Basileia . O problema pedia o valor da soma infinita que hoje pode ser reconhecida como o valor da função zeta de Riemann . Essa função está intimamente ligada aos números primos e a um dos problemas não resolvidos mais significativos da matemática, a hipótese de Riemann . Euler mostrou isso . O recíproco desse número ,, é a probabilidade limite de que dois números aleatórios selecionados uniformemente em um grande intervalo sejam relativamente primos (não têm fatores em comum).

A distribuição dos primos no grande, como a questão de quantos primos são menores do que um determinado limite grande, é descrita pelo teorema dos números primos , mas nenhuma fórmula eficiente para o -ésimo primo é conhecida. O teorema de Dirichlet sobre progressões aritméticas , em sua forma básica, afirma que polinômios lineares

com números inteiros relativamente primos e recebem um número infinito de valores primos. As formas mais fortes do teorema afirmam que a soma dos recíprocos desses valores primos divergem e que diferentes polinômios lineares com os mesmos têm aproximadamente as mesmas proporções de primos. Embora conjecturas tenham sido formuladas sobre as proporções de primos em polinômios de alto grau, elas permanecem não comprovadas e não se sabe se existe um polinômio quadrático que (para argumentos inteiros) é primo com frequência infinita.

Prova analítica do teorema de Euclides

A prova de Euler de que existem infinitos primos considera as somas dos recíprocos dos primos,

Euler mostrou que, para qualquer número real arbitrário , existe um primo para o qual essa soma é maior que . Isso mostra que existem infinitos primos porque, se houvesse muitos primos finitos, a soma alcançaria seu valor máximo no maior primo, em vez de crescer além de todos . A taxa de crescimento dessa soma é descrita mais precisamente pelo segundo teorema de Mertens . Para comparação, a soma

não cresce ao infinito como vai ao infinito (veja o problema da Basiléia ). Nesse sentido, os números primos ocorrem com mais frequência do que os quadrados dos números naturais, embora ambos os conjuntos sejam infinitos. O teorema de Brun afirma que a soma dos recíprocos dos primos gêmeos ,

é finito. Por causa do teorema de Brun, não é possível usar o método de Euler para resolver a conjectura dos primos gêmeos , de que existem infinitos primos gêmeos.

Número de primos abaixo de um determinado limite

O erro relativo de e a integral logarítmica como aproximações para a função de contagem de primos . Ambos os erros relativos diminuem para zero conforme aumenta, mas a convergência para zero é muito mais rápida para a integral logarítmica.

A função de contagem de primos é definida como o número de primos não maior que . Por exemplo, uma vez que existem cinco primos menores ou iguais a 11. Métodos como o algoritmo de Meissel-Lehmer podem calcular valores exatos mais rápido do que seria possível listar cada primo até . O teorema dos números primos afirma que é assintótico a , que é denotado como

e significa que a razão de para a fração direita se aproxima de 1 conforme cresce para o infinito. Isso implica que a probabilidade de que um número escolhido aleatoriamente menor que seja primo é (aproximadamente) inversamente proporcional ao número de dígitos em . Também implica que o ésimo número primo é proporcional a e, portanto, que o tamanho médio de uma lacuna primo é proporcional a . Uma estimativa mais precisa para é dada pela integral logarítmica de deslocamento

Progressões aritméticas

Uma progressão aritmética é uma sequência finita ou infinita de números, de modo que todos os números consecutivos na sequência têm a mesma diferença. Essa diferença é chamada de módulo de progressão. Por exemplo,

3, 12, 21, 30, 39, ...,

é uma progressão aritmética infinita com módulo 9. Em uma progressão aritmética, todos os números têm o mesmo resto quando divididos pelo módulo; neste exemplo, o resto é 3. Como o módulo 9 e o resto 3 são múltiplos de 3, o mesmo ocorre com todos os elementos da sequência. Portanto, essa progressão contém apenas um número primo, o próprio 3. Em geral, a progressão infinita

pode ter mais de um primo apenas quando seu resto e módulo são relativamente primos. Se eles são relativamente primos, o teorema de Dirichlet sobre progressões aritméticas afirma que a progressão contém infinitos primos.

Números primos na progressão aritmética mod 9.
Primos nas progressões aritméticas módulo 9. Cada linha da fina faixa horizontal mostra uma das nove progressões possíveis mod 9, com os números primos marcados em vermelho. As progressões de números que são 0, 3 ou 6 mod 9 contêm no máximo um número primo (o número 3); as progressões restantes de números que são 2, 4, 5, 7 e 8 mod 9 têm infinitamente muitos números primos, com números semelhantes de primos em cada progressão

O teorema de Green-Tao mostra que existem progressões aritméticas finitas arbitrariamente longas que consistem apenas em primos.

Valores principais de polinômios quadráticos

A espiral Ulam
A espiral Ulam . Os números primos (vermelhos) agrupam-se em algumas diagonais e não em outras. Os valores principais de são mostrados em azul.

Euler observou que a função

produz números primos para , embora números compostos apareçam entre seus valores posteriores. A busca por uma explicação para esse fenômeno levou à profunda teoria algébrica dos números de Heegner e ao problema do número de classes . A conjectura F de Hardy-Littlewood prevê a densidade dos primos entre os valores dos polinômios quadráticos com coeficientes inteiros em termos da integral logarítmica e dos coeficientes polinomiais. Nenhum polinômio quadrático foi comprovado para assumir infinitos valores primos.

A espiral Ulam organiza os números naturais em uma grade bidimensional, espiralando em quadrados concêntricos ao redor da origem com os números primos destacados. Visualmente, os primos parecem agrupar-se em certas diagonais e não em outras, sugerindo que alguns polinômios quadráticos assumem valores primos com mais frequência do que outros.

Função Zeta e a hipótese de Riemann

Gráfico dos valores absolutos da função zeta
Gráfico dos valores absolutos da função zeta, mostrando algumas de suas características

Uma das questões não resolvidas mais famosas da matemática, datada de 1859, e um dos Problemas do Prêmio do Milênio , é a hipótese de Riemann , que pergunta onde os zeros da função zeta de Riemann estão localizados. Esta função é uma função analítica dos números complexos . Para números complexos com parte real maior que um, é igual a uma soma infinita sobre todos os inteiros e um produto infinito sobre os números primos,

Essa igualdade entre uma soma e um produto, descoberta por Euler, é chamada de produto de Euler . O produto de Euler pode ser derivado do teorema fundamental da aritmética e mostra a estreita conexão entre a função zeta e os números primos. Isso leva a outra prova de que existem infinitos primos: se houvesse apenas finitos muitos, então a igualdade soma-produto também seria válida em , mas a soma seria divergente (é a série harmônica ) enquanto o produto seria finito, uma contradição.

A hipótese de Riemann afirma que os zeros da função zeta são todos números pares negativos ou números complexos com parte real igual a 1/2. A prova original do teorema dos números primos foi baseada em uma forma fraca dessa hipótese, de que não há zeros com parte real igual a 1, embora outras provas mais elementares tenham sido encontradas. A função de contagem de primos pode ser expressa pela fórmula explícita de Riemann como uma soma em que cada termo vem de um dos zeros da função zeta; o termo principal dessa soma é a integral logarítmica e os termos restantes fazem com que a soma flutue acima e abaixo do termo principal. Nesse sentido, os zeros controlam a regularidade com que os números primos são distribuídos. Se a hipótese de Riemann for verdadeira, essas flutuações serão pequenas, e a distribuição assintótica dos primos dada pelo teorema dos números primos também se manterá em intervalos muito mais curtos (de comprimento sobre a raiz quadrada de para intervalos próximos a um número ).

Álgebra abstrata

Aritmética modular e campos finitos

A aritmética modular modifica a aritmética usual usando apenas os números , para um número natural chamado módulo. Qualquer outro número natural pode ser mapeado neste sistema substituindo-o por seu resto após a divisão por . As somas modulares, diferenças e produtos são calculados realizando a mesma substituição pelo restante no resultado da soma usual, diferença ou produto de inteiros. A igualdade dos inteiros corresponde à congruência na aritmética modular: e são congruentes ( mod escrito ) quando têm o mesmo resto após a divisão por . No entanto, neste sistema de números, a divisão por todos os números diferentes de zero é possível se e somente se o módulo for primo. Por exemplo, com o número primo como módulo, a divisão por é possível :, porque limpar os denominadores multiplicando ambos os lados por fornece a fórmula válida . No entanto, com o módulo composto , a divisão por é impossível. Não há uma solução válida para : limpar os denominadores multiplicando por faz com que o lado esquerdo se torne ou . Na terminologia da álgebra abstrata , a capacidade de realizar a divisão significa que o módulo aritmético modular um número primo forma um campo ou, mais especificamente, um corpo finito , enquanto outros módulos fornecem apenas um anel, mas não um campo.

Vários teoremas sobre primos podem ser formulados usando aritmética modular. Por exemplo, o pequeno teorema de Fermat afirma que se (mod ), então (mod ). A soma de todas as opções de dá a equação

válido sempre que for primo. A conjectura de Giuga diz que essa equação também é condição suficiente para ser primo. O teorema de Wilson diz que um inteiro é primo se e somente se o fatorial é congruente ao mod . Para um número composto, isso não pode valer, uma vez que um de seus fatores divide tanto n e , portanto, é impossível.

números p -adic

A ordem -adic de um inteiro é o número de cópias de na fatoração principal de . O mesmo conceito pode ser estendido de inteiros para números racionais, definindo a ordem -adic de uma fração a ser . O valor absoluto -adic de qualquer número racional é então definido como . Multiplicar um número inteiro por seu valor absoluto -adic cancela os fatores de em sua fatoração, deixando apenas os outros primos. Assim como a distância entre dois números reais pode ser medida pelo valor absoluto de sua distância, a distância entre dois números racionais pode ser medida por sua distância -adic, o valor absoluto -adic de sua diferença. Para esta definição de distância, dois números estão próximos (eles têm uma pequena distância) quando sua diferença é divisível por uma alta potência de . Da mesma forma que os números reais podem ser formados a partir dos números racionais e suas distâncias, adicionando valores limite extras para formar um campo completo , os números racionais com a distância -adic podem ser estendidos para um campo completo diferente, o -adic números .

Esta imagem de uma ordem, valor absoluto e campo completo derivado deles pode ser generalizada para campos de números algébricos e suas avaliações (certos mapeamentos do grupo multiplicativo do campo para um grupo aditivo totalmente ordenado , também chamado de ordens), valores absolutos ( certos mapeamentos multiplicativos do campo para os números reais, também chamados de normas), e lugares (extensões para campos completos nos quais o campo dado é um conjunto denso , também chamados de completamentos). A extensão dos números racionais aos reais , por exemplo, é um lugar em que a distância entre os números é o valor absoluto usual de sua diferença. O mapeamento correspondente a um grupo aditivo seria o logaritmo do valor absoluto, embora isso não atenda a todos os requisitos de uma avaliação. De acordo com o teorema de Ostrowski , até uma noção natural de equivalência, os números reais e os números -adic, com suas ordens e valores absolutos, são as únicas avaliações, valores absolutos e lugares nos números racionais. O princípio local-global permite que certos problemas sobre os números racionais sejam resolvidos juntando soluções de cada um de seus lugares, novamente sublinhando a importância dos primos para a teoria dos números.

Elementos principais em anéis

Os primos gaussianos com norma inferior a 500

Um anel comutativo é uma estrutura algébrica onde são definidas adição, subtração e multiplicação. Os inteiros são um anel, e os números primos nos inteiros foram generalizados para anéis de duas maneiras diferentes, elementos primos e elementos irredutíveis . Um elemento de um anel é chamado de primo se for diferente de zero, não tem inverso multiplicativo (ou seja, não é uma unidade ) e satisfaz o seguinte requisito: sempre que divide o produto de dois elementos de , também divide pelo menos um de ou . Um elemento é irredutível se não for uma unidade nem o produto de dois outros elementos não unitários. No anel de inteiros, os elementos primos e irredutíveis formam o mesmo conjunto,

Em um anel arbitrário, todos os elementos primos são irredutíveis. O inverso não é válido em geral, mas é válido para domínios únicos de fatoração .

O teorema fundamental da aritmética continua a valer (por definição) em domínios únicos de fatoração. Um exemplo de tal domínio é um dos inteiros de Gauss , o anel de números complexos da forma em que denota a unidade imaginária e e são números inteiros arbitrárias. Seus elementos principais são conhecidos como primos gaussianos . Nem todo número primo entre os inteiros permanece primo nos inteiros gaussianos; por exemplo, o número 2 pode ser escrito como um produto dos dois primos gaussianos e . Os primos racionais (os elementos primos nos inteiros) congruentes com 3 mod 4 são primos gaussianos, mas os primos racionais congruentes com 1 mod 4 não são. Isso é uma consequência do teorema de Fermat sobre as somas de dois quadrados , que afirma que um primo ímpar pode ser expresso como a soma de dois quadrados e , portanto, fatorável como , exatamente quando é 1 mod 4.

Ideais primordiais

Nem todo anel é um domínio de fatoração único. Por exemplo, no anel de números (para inteiros e ) o número tem duas fatorações , onde nenhum dos quatro fatores pode ser reduzido ainda mais, então ele não tem uma fatoração única. A fim de estender a fatoração única a uma classe maior de anéis, a noção de um número pode ser substituída pela de um ideal , um subconjunto dos elementos de um anel que contém todas as somas dos pares de seus elementos e todos os produtos de seus elementos com elementos de anel. Ideais primos, que generalizam elementos primos no sentido de que o ideal principal gerado por um elemento primo é um ideal primo, são uma ferramenta importante e objeto de estudo em álgebra comutativa , teoria dos números algébricos e geometria algébrica . Os ideais principais do anel de inteiros são os ideais (0), (2), (3), (5), (7), (11), ... O teorema fundamental da aritmética generaliza para o teorema de Lasker-Noether , que expressa cada ideal em um anel comutativo Noetheriano como uma interseção de ideais primários , que são as generalizações apropriadas de potências primárias .

O espectro de um anel é um espaço geométrico cujos pontos são os ideais principais do anel. A geometria aritmética também se beneficia dessa noção, e muitos conceitos existem tanto na geometria quanto na teoria dos números. Por exemplo, a fatoração ou ramificação de ideais primos quando elevados a um campo de extensão , um problema básico da teoria algébrica dos números, tem alguma semelhança com a ramificação na geometria . Esses conceitos podem até mesmo ajudar em questões teóricas dos números preocupadas apenas com números inteiros. Por exemplo, ideais primos no anel de inteiros de campos de números quadráticos podem ser usados ​​para provar a reciprocidade quadrática , uma afirmação que diz respeito à existência de números primos inteiros de módulo de raízes quadradas. As primeiras tentativas de provar o Último Teorema de Fermat levaram à introdução de Kummer dos primos regulares , números primos inteiros conectados com o fracasso da fatoração única nos inteiros ciclotômicos . A questão de quantos números primos inteiros influenciam em um produto de ideais primos múltiplos em um campo de números algébricos é abordada pelo teorema da densidade de Chebotarev , que (quando aplicado aos inteiros ciclotômicos) tem o teorema de Dirichlet sobre primos em progressões aritméticas como um caso especial.

Teoria do grupo

Na teoria dos grupos finitos, os teoremas de Sylow implicam que, se uma potência de um número primo divide a ordem de um grupo , então o grupo tem um subgrupo de ordem . Pelo teorema de Lagrange , qualquer grupo de ordem primária é um grupo cíclico , e pelo teorema de Burnside qualquer grupo cuja ordem seja divisível por apenas dois primos é solucionável .

Métodos computacionais

A engrenagem pequena neste equipamento agrícola tem 13 dentes, um número primo, e a engrenagem do meio tem 21, relativamente primo a 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 de matemática pura, sem nenhuma aplicação fora da matemática a não ser o uso de dentes de engrenagens com números primos para distribuir uniformemente o desgaste. Em particular, os teóricos dos números, como o matemático britânico GH Hardy, orgulhavam-se de fazer um trabalho que não tinha absolutamente nenhum significado militar.

Essa visão da pureza da teoria dos números foi destruída 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 . Essas aplicações 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 de teste de primalidade mais básica, a divisão de teste, é muito lenta para ser útil para grandes números. 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 diz se seu 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 . Os números primos também são usados ​​na computação para somas de verificação , tabelas de hash e geradores de números pseudo - aleatórios .

Divisão de teste

O método mais básico de verificar a primalidade de um dado inteiro é chamado de divisão experimental . Este método divide por cada inteiro de 2 até a raiz quadrada de . Qualquer divisão inteira é estabelecida uniformemente como composto; caso contrário, é primo. Os inteiros maiores que a raiz quadrada não precisam ser verificados porque, sempre que um dos dois fatores e é menor ou igual à raiz quadrada de . Outra otimização é verificar apenas os primos como fatores nesta faixa. Por exemplo, para verificar se 37 é primo, este método o divide pelos primos no intervalo de 2 a , que são 2, 3 e 5. Cada divisão produz um resto diferente de zero, então 37 é realmente primo.

Embora esse método seja simples de descrever, ele é impraticável para testar a primalidade de inteiros grandes, porque o número de testes que ele realiza cresce exponencialmente em função do número de dígitos desses inteiros. No entanto, a divisão experimental 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 neste filtro.

Peneiras

Animação da peneira de Eratóstenes
A peneira 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 composto (cores mais claras). Depois de marcar os múltiplos de 2 (vermelho), 3 (verde), 5 (azul) e 7 (amarelo), todos os números primos até a raiz quadrada do tamanho da mesa foram processados ​​e todos os números não marcados restantes (11, 13 , etc.) são marcados como primos (magenta).

Antes dos computadores, eram comumente impressas tabelas matemáticas que listavam todos os primos ou fatorações primos até um determinado limite. O método mais antigo para gerar uma lista de primos é chamado de peneira de Eratóstenes. A animação mostra uma variante otimizada deste método. Outro método de peneiramento assintoticamente mais eficiente para o mesmo problema é a peneira de Atkin . Em matemática avançada, a teoria do crivo aplica métodos semelhantes a outros problemas.

Teste de primalidade versus prova de primalidade

Alguns dos testes modernos mais rápidos para saber se um determinado número arbitrário é primo são algoritmos probabilísticos (ou de Monte Carlo ), o que significa que eles têm uma pequena chance aleatória de produzir uma resposta incorreta. Por exemplo, o teste primality Solovay-Strassen num determinado número escolhe um número aleatoriamente a partir de meio e utiliza exponenciação modular para verificar se é divisível por . Em caso afirmativo, responde sim e caso contrário, responde não. Se realmente for primo, sempre responderá sim, mas se for composto, responderá sim com probabilidade no máximo 1/2 e não com probabilidade no mínimo 1/2. Se este teste for repetido vezes no mesmo número, a probabilidade de que um número composto passe no teste todas as vezes é no máximo . Como isso diminui exponencialmente com o número de testes, fornece alta confiança (embora não seja certeza) de que um número que passa no teste repetido é primo. Por outro lado, se o teste falhar, então o número é certamente composto. Um número composto que passa nesse teste é chamado de pseudoprime .

Em contraste, alguns outros algoritmos garantem que sua resposta sempre será correta: os primos sempre serão determinados como primos e os compostos sempre serão determinados como compostos. Por exemplo, isso é verdade para a divisão experimental. Os algoritmos com saída correta garantida incluem algoritmos determinísticos (não aleatórios), como o teste de primalidade AKS , e algoritmos aleatórios de Las Vegas em que as escolhas aleatórias feitas pelo algoritmo não afetam sua resposta final, como algumas variações elípticas prova de primalidade de curva . Quando o método da curva elíptica conclui que um número é primo, ele fornece um certificado de primalidade que pode ser verificado rapidamente. O teste de primalidade da curva elíptica é o mais rápido na prática dos testes de primalidade com garantia certa, mas sua análise de tempo de execução é baseada em argumentos heurísticos em vez de provas rigorosas. O teste de primalidade AKS provou matematicamente a complexidade do tempo, mas é mais lento do que a prova de primalidade da curva elíptica na prática. 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 de correção garantida seja usado para verificar se os números restantes são primos.

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

Teste Desenvolvido em Modelo Tempo de execução Notas Referências
Teste de primalidade AKS 2002 determinista
Prova de primalidade de curva elíptica 1986 Las vegas heuristicamente
Teste de primalidade Baillie – PSW 1980 Monte carlo
Teste de primalidade de Miller-Rabin 1980 Monte carlo probabilidade de erro
Teste de primalidade Solovay-Strassen 1977 Monte carlo probabilidade de erro

Algoritmos de propósito especial e o maior primo conhecido

Além dos testes mencionados acima que se aplicam a qualquer número natural, alguns números de uma forma 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, ao mesmo tempo que uma única iteração do teste de Miller-Rabin. É por isso que, desde 1992 (em dezembro de 2018), o maior primo conhecido sempre foi um primo de Mersenne. Presume-se que existam infinitos primos de Mersenne.

A tabela a seguir fornece os maiores primos conhecidos de vários tipos. Alguns desses primos foram encontrados usando computação distribuída . Em 2009, o projeto Great Internet Mersenne Prime Search recebeu um prêmio de US $ 100.000 pela primeira vez em que descobriu um primo com pelo menos 10 milhões de dígitos. A Electronic Frontier Foundation também oferece $ 150.000 e $ 250.000 para números primos com pelo menos 100 milhões de dígitos e 1 bilhão de dígitos, respectivamente.

Modelo melhor Número de dígitos decimais Encontro Encontrado por
Mersenne Prime 2 82.589.933 - 1 24.862.048 7 de dezembro de 2018 Patrick Laroche, Great Internet Mersenne Prime Search
Proth Prime 10.223 × 2 31.172.165 + 1 9.383.761 31 de outubro de 2016 Péter Szabolcs, PrimeGrid
primo fatorial 208.003! - 1 1.015.843 Julho de 2016 Sou Fukui
primo primorial 1.098.133 # - 1 476.311 Março de 2012 James P. Burt, PrimeGrid
primos gêmeos 2.996.863.034.895 × 2 1290000 ± 1 388.342 Setembro 2016 Tom Greer, PrimeGrid

Fatoração de inteiros

Dado um número inteiro composto , a tarefa de fornecer um (ou todos) os fatores primos é chamada de fatoração de . É significativamente mais difícil do que o teste de primalidade e, embora muitos algoritmos de fatoração sejam conhecidos, eles são mais lentos do que os métodos de teste de primalidade mais rápidos. A divisão experimental e o algoritmo rho de Pollard podem ser usados ​​para encontrar fatores muito pequenos de , e a fatoração da curva elíptica pode ser eficaz quando tem fatores de tamanho moderado. Métodos adequados para grandes números arbitrários que não dependem do tamanho de seus fatores incluem a peneira quadrática e a peneira de campo de número geral . Tal como acontece com o teste de primalidade, também existem algoritmos de fatoração que exigem que sua entrada tenha uma forma especial, incluindo a peneira de campo de número especial . Em dezembro de 2019, o maior número conhecido por ter sido fatorado por um algoritmo de uso geral é RSA-240 , que tem 240 dígitos decimais (795 bits) e é o produto de dois grandes números primos.

O algoritmo de Shor pode fatorar qualquer número inteiro em um número polinomial de etapas em um computador quântico . No entanto, a tecnologia atual só pode executar esse algoritmo para números muito pequenos. Em outubro de 2012, o maior número fatorado por um computador quântico executando o algoritmo de Shor era 21.

Outras aplicações computacionais

Vários algoritmos de criptografia de chave pública , como RSA e a troca de chaves Diffie – Hellman , são baseados em grandes números primos (números primos de 2048 bits são comuns). RSA se baseia na suposição de que é muito mais fácil (ou seja, mais eficiente) realizar a multiplicação de dois (grandes) números e do que calcular e ( coprime assumido ) se apenas o produto for conhecido. A troca de chaves Diffie – Hellman depende do fato de que existem algoritmos eficientes para exponenciação modular (computação ), enquanto a operação reversa (o logaritmo discreto ) é considerada um problema difícil.

Os números primos são freqüentemente usados ​​para tabelas de hash . Por exemplo, o método original de Carter e Wegman para hashing universal foi baseado na computação de funções hash pela escolha de funções lineares aleatórias módulo de grandes números primos. Carter e Wegman generalizaram este método para hashing independente usando polinômios de alto grau, novamente números primos grandes. Assim como na função hash, os números primos são usados ​​para o tamanho da tabela hash em tabelas hash baseadas em sondagem quadrática para garantir que a sequência de sondagem cubra toda a tabela.

Alguns métodos de checksum baseiam-se na matemática dos números primos. Por exemplo, as somas de verificação usadas no International Standard Book Numbers são definidas pelo restante do número módulo 11, um número primo. Como 11 é o primo, esse método pode detectar erros de um único dígito e transposições de dígitos adjacentes. Outro método de checksum, Adler-32 , usa o módulo aritmético 65521, o maior número primo menor que . Os números primos também são usados ​​em geradores de números pseudo-aleatórios, incluindo geradores congruenciais lineares e o Mersenne Twister .

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 números primos de pontos em uma grade bidimensional de forma que não haja três em uma linha , ou de forma que cada triângulo formado por três dos pontos tenha uma grande área . Outro exemplo é o critério de Eisenstein , um teste para determinar se um polinômio é irredutível com base na divisibilidade de seus coeficientes por um número primo e seu quadrado.

A soma conectada de dois nós principais

O conceito de número primo é tão importante que foi generalizado de diferentes maneiras em vários ramos da matemática. Geralmente, "primo" indica minimalidade ou indecomponibilidade, em um sentido apropriado. Por exemplo, o campo primo de um determinado campo é seu menor subcampo que contém 0 e 1. É o campo dos números racionais ou um campo finito com um número primo de elementos, de onde vem o nome. Freqüentemente, um segundo significado adicional é pretendido com o uso da palavra primo, a saber, que qualquer objeto pode ser, essencialmente de maneira única, decomposto em seus componentes principais. Por exemplo, na teoria do nó , um nó principal é um indecomponível 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 principais. A decomposição primária de três variedades é outro exemplo desse tipo.

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

Polígonos construtíveis e partições poligonais

Construção de um pentágono regular usando régua e compasso
Construção de um pentágono regular usando régua e compasso. Isso só é possível porque 5 é um primo de Fermat .

Os primos de Fermat são primos da forma

com um número inteiro não negativo . Eles foram nomeados em homenagem a Pierre de Fermat , que conjeturou que todos esses números são primos. Os primeiros cinco desses números - 3, 5, 17, 257 e 65.537 - são primos, mas são compostos, assim como todos os outros números de Fermat que foram verificados em 2017. Um -gon regular é construtível usando régua e compasso se e apenas se os fatores primos ímpares de (se houver) forem primos de Fermat distintos. Da mesma forma, um -gon regular pode ser construído usando régua, compasso e um trissetor de ângulo se e somente se os fatores primos de forem qualquer número de cópias de 2 ou 3 juntamente com um conjunto (possivelmente vazio) de primos Pierpont distintos , primos de o formulário .

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

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 de Riemann estão conectados aos níveis de energia dos sistemas quânticos . 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 imparciais e medidas simétricas informacionais com valor de operador positivo .

Biologia

A estratégia evolutiva usada pelas cigarras do gênero Magicicada faz uso de números primos. Esses insetos passam a maior parte de suas vidas como larvas no subsolo. Eles só se transformam em pupas e emergem de suas tocas após 7, 13 ou 17 anos, quando então voam, procriam e morrem após algumas semanas, no máximo. Os biólogos teorizam que esses ciclos de reprodução com números primos evoluíram para evitar que os predadores se sincronizem com esses ciclos. Em contraste, os períodos plurianuais entre a floração em plantas de bambu são considerados como números suaves , tendo apenas pequenos números primos em suas fatorações.

Artes e literatura

Os números primos influenciaram muitos artistas e escritores. O compositor francês Olivier Messiaen usou 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-50), ele simultaneamente emprega motivos com durações dadas por diferentes números primos para criar ritmos imprevisíveis: os primos 41, 43, 47 e 53 aparecem no terceiro estudo, "Neumes rythmiques". Segundo Messiaen, esta forma de compor foi "inspirada nos movimentos da natureza, movimentos de durações livres e desiguais".

Em seu romance de ficção científica Contact , o cientista Carl Sagan sugeriu que a fatoração primária poderia ser usada como um meio de estabelecer planos de imagens bidimensionais em comunicações com alienígenas, uma ideia que ele havia desenvolvido informalmente com o astrônomo americano Frank Drake em 1975. novel The Curious Incident of the Dog in the Night-Time por Mark Haddon , os arranjos narrador as seções da história por números primos consecutivos como uma forma de transmitir o estado mental de seu personagem principal, um adolescente matematicamente dotado com síndrome de Asperger . Os números primos são usados ​​como uma metáfora para a solidão e o isolamento no romance de Paolo Giordano , A Solidão dos Números Primos , no qual são retratados como "estranhos" entre os inteiros.

Notas

Referências

links externos

Geradores e calculadoras