Número primo

Um número natural (1, 2, 3, 4, 5, 6 etc.) é chamado de número primo se é maior que 1 e não pode ser escrito como o produto de dois números naturais menores. Os números maiores que 1 que não são primos são chamados de números compostos. Noutras palavras, n é primo se n elementos não podem ser divididos em grupos menores, porém maior que apenas um, de mesma quantidade, ou não é possível organizar n pontos em uma grade retangular que possui mais de um ponto de altura ou largura. Por exemplo, entre os números de 1 a 6, os números 2, 3 e 5 são primos, visto que não há nenhum outro número que os divida igualmente (sem deixar resto). 1 não é primo, visto que é especificadamente excluído da definição. 4 = 2 × 2 e 6 = 2 × 3 são ambos compostos. 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. 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.

A origem do conceito número primo é incerta, todavia, há um indício de consciência desses números demonstrado pelo osso de Ishango, um achado ósseo datado do Paleolítico Superior, no qual aparecem sinais representando os números primos entre 10 e 20, mas isso pode ser apenas uma coincidência. Outro indício pode ser observado na mesopotâmia no segundo milênio a.C., onde há tábuas contendo soluções para alguns problemas aritméticos relativos que, para serem solucionados, requerem um conhecimento de fatoração em números primos. No mesmo milênio, datado de aproximadamente 1550 a.C., o Papiro de Rhind tem expansões de frações egípcias de diferentes formas para números primos e compostos. As expansões de números que compartilham o menor dos seus fatores são semelhantes, sugerindo que os egípcios estavam pelo menos cientes da diferença entre números primos e compostos. No mesmo período, há indícios de que os chineses também possuíam um entendimento desses números. Aproximadamente no ano 1000 a.C., associavam características femininas aos números pares e características masculinas aos ímpares, considerando ímpares não primos, como 15, "efeminados". Eles utilizavam um método físico para a identificação de números primos: ao tentar dispor uma certa quantidade de grãos em retângulos, percebiam que números primos, como 17, somente permitiam uma disposição em linha única, enquanto números compostos, como 15, podiam ser arranjados em retângulos menores.

Pierre de Fermat (1601-1665) descobriu que todo número primo da forma 4 n + 1 , {\displaystyle 4n+1,} tal como 5 , 13 , 17 , 29 , 37 , 41 , {\displaystyle 5,13,17,29,37,41,} etc., é a soma de dois quadrados. Por exemplo: 5 = 1 2 + 2 2 , {\displaystyle 5=1^{2}+2^{2},} 13 = 2 2 + 3 2 , {\displaystyle 13=2^{2}+3^{2},} 17 = 1 2 + 4 2 , {\displaystyle 17=1^{2}+4^{2},} 29 = 2 2 + 5 2 , {\displaystyle 29=2^{2}+5^{2},} 37 = 1 2 + 6 2 , {\displaystyle 37=1^{2}+6^{2},} 41 = 4 2 + 5 2 . {\displaystyle 41=4^{2}+5^{2}.} Hoje são conhecidos dois grupos de números primos: 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: 31 {\displaystyle 31} , 331 , 3.331 , 33.331 , 333.331 , 3.333.331 {\displaystyle 331,3.331,33.331,333.331,3.333.331} e 33.333.331 {\displaystyle 33.333.331} são primos mas 333.333.331 {\displaystyle 333.333.331} não é, pois 333.333.331 = 17 × 19.607.843. {\displaystyle 333.333.331=17\times 19.607.843.}

Imagem: Jashir · BY-NC-ND · Openverse

Como consequência do teorema do número primo, uma expressão assintótica para o n-ésimo primo p n {\displaystyle p_{n}} é: p n ∼ n ln ⁡ n . {\displaystyle p_{n}\sim n\ln n.} Uma aproximação melhor é: p n = n ln ⁡ n + n ln ⁡ ln ⁡ n − n + n ln ⁡ n ( ln ⁡ ln ⁡ n − 2 ) − n ln ⁡ ln ⁡ n 2 ( ln ⁡ n ) 2 ( ln ⁡ ln ⁡ n − 6 ) + O ( n ( ln ⁡ n ) 2 ) . {\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).}} O teorema de Rosser mostra que p n {\displaystyle p_{n}} é maior que n ln ⁡ n . {\displaystyle n\ln n.} É possível melhorar esta aproximação com os limites: n ln ⁡ n + n ( ln ⁡ ln ⁡ n − 1 ) < p n < n ln ⁡ n + n ln ⁡ ln ⁡ n {\displaystyle n\ln n+n(\ln \ln n-1)<p_{n}<n\ln n+n\ln \ln n} , para n ≥ 6. {\displaystyle n\geq 6.}

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. 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. 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. 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. 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. Os números primos também são usados na computação para somas de verificação, tabelas de dispersão e geradores de números pseudoaleatórios.

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. 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. 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). 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. A decomposição prima de 3-variedades é outro exemplo desse tipo.