Número primo

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Números primos)
Os números compostos podem ser organizados em retângulos, já os números primos não.

Um número primo é um número natural maior que 1 que não pode ser formado pela multiplicação de outros dois naturais menores. Um número natural maior que 1 que não é primo é chamado de número composto. Por exemplo, 5 é primo porque as únicas maneiras de escrevê-lo como um produto, 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 por causa do teorema fundamental da aritmética: todo número natural maior que 1 é ou um primo em si mesmo ou pode ser fatorado como um produto de primos de maneira única, salvo pela ordem dos fatores.

A propriedade de ser primo é chamada primalidade. Um método simples, mas lento, de verificar a primalidade de um número dado n, chamado de divisão tentativa, testa se n é 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 número primo de Mersenne com 24 862 048 algarismos.[1]

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 dentro dos 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 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 ainda estão 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 que diferem por 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.

Os átomos da aritmética[editar | editar código-fonte]

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

Assim obtemos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ... A partir desse procedimento podemos simplificar a descobertas de primos usando o lema: Se um número natural n > 1 não é divisível por nenhum primo p tal que ≤ n, então ele é primo. (demonstrado adiante). Este lema fornece um teste de primalidade, pois, para verificar se um dado número n é primo, basta verificar que não é divisível por nenhum p que não supere

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

Teoria dos números[editar | editar código-fonte]

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 qual é a proporção de números primos entre os números menores que ?

  • 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 os primos. Seja o número tal que

= onde denota o produtório.

Se é um número primo, é necessariamente diferente dos primos pois sua divisão por qualquer um deles tem um resto de 1.
Por outro lado, se é composto, existe um número primo tal que é divisor de
Mas obviamente Logo existe um novo número primo.
Há um novo número primo, seja 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 Temos que, necessariamente, é coprimo de (números coprimos são os que não têm nenhum fator comum maior do que ). Provamos isto imaginando que a divisão do menor pelo maior tem resultado e resto e do maior pelo menor tem resultado e resto Assim, tem, necessariamente, ao menos dois factores primos.
Tomemos o sucessor deste, que representamos como Pelo mesmo raciocínio, ele é coprimo a Ao multiplicar os dois números, temos 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 onde é o logaritmo natural.
  • Para qualquer número inteiro existem números inteiros consecutivos todos compostos.
  • O produto de qualquer sequência de números inteiros consecutivos é divisível por
  • Se não é primo, então possui, necessariamente, um fator primo menor do que ou igual a
  • 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[editar | editar código-fonte]

Pierre de Fermat (1601-1665) descobriu que todo número primo da forma tal como etc., é a soma de dois quadrados. Por exemplo:

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

  • - que podem sempre ser escritos na forma (); e
  • - nunca podem ser escritos na forma ().

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:

, e são primos mas não é, pois

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 é seguido de cento e onze[2] números compostos e não existem[3] primos entre os números e

Algumas fórmulas produzem muitos números primos, por exemplo fornece primos quando [4][5] Veja que para x = 41, a fórmula resulta em que não é primo.

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

Não se sabe se há uma expressão polinomial com que represente infinitos números primos. Dirichlet usou métodos para provar que se e não têm fator primo em comum, a expressão polinomial a duas variáveis

representa infinitos primos, quando e assumem valores positivos inteiros.

Fermat pensou que a fórmula forneceria números primos para Este números são chamados de números de Fermat e são comumente denotados por Os cinco primeiros números são:

sendo todos primos.

Aproximações para o n-ésimo primo[editar | editar código-fonte]

Como consequência do teorema do número primo, uma expressão assintótica para o n-ésimo primo é:

Uma aproximação melhor é:

[6]

O teorema de Rosser mostra que é maior que É possível melhorar esta aproximação com os limites[7][8]: , para

Maior número primo conhecido[editar | editar código-fonte]

Em Janeiro de 2013, foi divulgado o maior número primo já calculado até então. Tem 17.425.170 dígitos e, se fosse escrito por extenso, ocuparia 3,4 mil páginas impressas com cinco mil caracteres cada. É o número . Foi descoberto por Curtis Cooper, da Universidade Central do Missouri em Warrensburg, EUA, como parte do Great Internet Mersenne Prime Search (GIMPS), um projeto internacional de computação compartilhada desenhado para encontrar números primos de Mersene.[9]

Em janeiro de 2016, um grupo de matemáticos da mesma universidade descobriu um número primo com 22.338.618 dígitos, que recebeu o nome "M74207281".[10] É o número que tem 5 milhões de dígitos a mais que o último conhecido.[11] O achado foi divulgado pelo programa GIMPS.

Em dezembro de 2017 um engenheiro eletrotécnico da empresa de entregas FedEx descobriu um número primo ainda maior: “M77232917”, como foi batizado, tem mais de 23 milhões de dígitos. O homem que o descobriu chama-se Jonathan Pace, tem 51 anos, é norte-americano e também participa do GIMPS.[12] Em dezembro de 2018 uma nova marca de maior número primo foi registrada, alcançando a quantidade de 24 milhões de dígitos.

Outras Aplicações[editar | editar código-fonte]

Biologia[editar | editar código-fonte]

  • A estratégia evolutiva usada por cigarras do gênero "Magicicada" faz uso de números primos. Evolutivamente, à medida que algumas espécies foram alongando seus períodos de "hibernação", também os de seus predadores naturais foram se alongando. Foram favorecidas aquelas que só emergiam após número primo de anos (13, 17), pois isso reduz ao máximo as chances de encontrar seus predadores naturais.[13] Um exemplo para entender isso é: Imagine uma espécie de cigarra que vire ninfa a cada 2 anos, e uma outra a cada 4. Um predador natural de cigarras que fique hibernando 4 anos, quando sair de sua hibernação, terá como fonte de alimentação ambas espécies, aumentando a quantidade de comida disponível. Já com as cigarras que ficam hibernando um número primo de anos, seus predadores naturais terão que hibernar esse período de temp também, e terão menos opções de comida.
  • Há uma espécie de bambu, "Phyllostachys bambusoides", que tem sua florada a cada 23 anos.[14] Cientistas acreditam que esse "número primo de tempo" para cada floração é um diferencial evolutivo dessa espécie frente as demais.

Mecânica quântica[editar | editar código-fonte]

Começando com o trabalho de Hugh Montgomery e Freeman Dyson na década de 1970, matemáticos e físicos especularam que os zeros da função zeta Riemann estão conectados aos níveis de energia dos sistemas quânticos.[15][16] Os números primos também são significativos na ciência da informação quântica, graças a estruturas matemáticas como bases mutuamente imparciales e medidas de valor positivo de operadores positivos.[17][18]

Ver também[editar | editar código-fonte]

Referências

  1. «GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1». Mersenne Research, Inc. 21 December 2018. Consultado em 21 December 2018  Verifique data em: |acessodata=, |data= (ajuda)
  2. Conforme cálculo feito pelo Wolfram Alpha.
  3. Conforme cálculo feito pelo Wolfram Alpha.
  4. Hua (2009), p. 176-177"
  5. Ver lista dos valores, calculada pelo Wolfram Alpha
  6. 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)
  7. Eric Bach, Jeffrey Shallit (1996). Algorithmic Number Theory. 1. [S.l.]: MIT Press. p. 233. ISBN 0-262-02405-5 
  8. 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 
  9. «World's largest prime number discovered -- all 17 million digits» 
  10. «Missouri Mathematicians Discover New Prime Number» 
  11. BBC. «Largest known prime number discovered in Missouri» 
  12. «Descoberto o maior número primo conhecido. Tem mais de 23 milhões de dígitos» 
  13. ideiasesquecidas.com/ Cigarras e números primos
  14. nationalgeographic.com/ Zimmer, Carl (May 15, 2015). "Bamboo Mathematicians". Phenomena: The Loom. National Geographic. Retrieved February 22, 2018.
  15. 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 
  16. Hayes, Brian (2003). «Computing science: The spectrum of Riemannium». American Scientist. 91 (4): 296–300. JSTOR 27858239. doi:10.1511/2003.26.3349 
  17. 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 
  18. 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.3591Acessível livremente. doi:10.1088/1751-8113/43/30/305305 

Bibliografia[editar | editar código-fonte]

  • Hua, L. K. (2009). Additive Theory of Prime Numbers. Col: Translations of Mathematical Monographs. 13. [S.l.]: AMS Bookstore. ISBN 978-0-8218-4942-2 
  • Marcus du Sautoy, Os mistérios dos números: Uma viagem pelos grandes enigmas da matemática (que até hoje ninguém foi capaz de resolver), Jorge Zahar Editor Ltda, 2013 ISBN 8-537-81099-1
  • Luogeng Hua, Additive theory of prime numbers, American Mathematical Soc. ISBN 0-821-89750-0 (em inglês)
  • Mary Jane Sterling, Álgebra I Para Leigos, Alta Books Editora, 2013 ISBN 8-576-08256-X
  • Edward S. Wall, Teoria dos Números para Professores do Ensino Fundamental, McGraw Hill Brasil, 2014 ISBN 8-580-55353-9
  • PAULO BOUHID, NÚMEROS CRUZADOS, biblioteca24horas ISBN 8-578-93055-X
  • LAURA LEMAY, ROGERS CADENHEAD, APRENDA EM 21 DIAS JAVA 2 - TRADUÇÃO DA 4a ED. Elsevier Brasil ISBN 8-535-21685-5

Ligações externas[editar | editar código-fonte]

Wikilivros
Wikilivros
O wikilivro Teoria de números tem uma página intitulada Números primos