# Teorema dos números primos

Em matemática, sobretudo na teoria dos números, o teorema dos números primos é um importante resultado sobre a distribuição dos números primos, que afirma que o número de primos menores ou iguais a n é aproximadamente n / ln n. Este resultado foi primeiramente demonstrado independentemente por dois matemáticos, Jacques Hadamard e Charles-Jean de La Vallée Poussin, através do estudo da função zeta de Riemann. Uma demonstração elementar, sem apelo à teoria analítica dos números, foi dada posteriormente por Atle Selberg e Paul Erdős.

## Enunciado

Seja $\Pi (n)\,$ a função de contagem de números primos, que retorna o número de números primos entre 1 e n. Então vale o limite:
    $\lim _{n\to \infty }{\frac {\Pi (n)}{n/\ln n}}=1\,$
É possível mostrar que este limite é equivalente a este outro:
    $\lim _{n\to \infty }{\frac {p_{n}}{n\ln n}}=1\,$
onde $p_{n}\,$ é o enésimo número primo.
Usando-se notação assimptótica, pode-se expressar o teorema como:
    $\Pi (n)\sim {\frac {n}{\ln n}}.\!$

## História

Com base nas tabelas de Anton Felkel e Jurij Vega, Adrien-Marie Legendre conjecturou em 1797 ou 1798 que π(a) é aproximado pela função a/(A ln(a) + B), onde A e B são constantes não especificadas. Na segunda edição de seu livro sobre a teoria dos números (1808) ele então fez uma conjectura mais precisa, com A = 1 e B = −1,08366. Carl Friedrich Gauss considerou essa mesma questão quando tinha 15 ou 16 anos "ins Jahr 1792 oder 1793", segundo a sua própria recordação em 1849. Em 1838 Peter Gustav Lejeune Dirichlet desenvolveu sua própria função aproximadora, a integral logarítmica li(x) (sob a forma ligeiramente diferente de uma série, que ele comunicou a Gauss). Ambas as fórmulas, de Legendre e Dirichlet, implicam a mesma equivalência assimptótica conjecturada de π(x) e x / ln(x) enunciada acima, embora tenha sido descoberto que a aproximação de Dirichlet é consideravelmente melhor se considerarmos as diferenças em vez dos quocientes.
Em dois artigos de 1848 e 1850, o matemático russo Pafnuty L'vovich Chebyshev tentou provar a lei assintótica de distribuição dos números primos. Seu trabalho é notável por usar a função zeta ζ(s) (para valores reais do argumento "s", como nas obras de Leonhard Euler, de 1737) precedendo o celebrado ensaio de Riemann de 1859, e ele obteve sucesso em provar uma forma ligeiramente mais fraca da lei assintótica, a saber, que se o limite de π(x)/(x/ln(x)) quando x vai ao infinito existe definitivamente,então ele é necessariamente igual a um. Ele foi capaz de provar de forma incondicional que esta razão é limitada acima e abaixo por duas explicitamente dadas constantes próximas de 1 para todo x. Embora em seu artigo Chebyshev não tenha provado o teorema dos números primos, suas estimativas para π(x) eram fortes o suficiente para ele provar o postulado de Bertrand que afirma que existe um número primo entre n e 2n para todo inteiro n ≥ 2.
Um importante artigo a respeito da distribuição dos números primos foi o ensaio de Riemann de 1859 Sobre o Número de Primos Menores Que uma Dada Magnitude, o único artigo que ele escreveu sobre o assunto. Riemann introduziu novas ideias ao tópico, a maior delas sendo a de que a distribuição dos números primos é intimamente conectada aos zeros da analiticamente estendida função zeta de Riemann de uma variável complexa. Em particular, foi nesse artigo de Riemann que a ideia de aplicar métodos de análise complexa ao estudo da função real π(x) teve origem. Estendendo as ideias de Riemann, duas provas da lei assintótica da distribuição de números primos foram obtidas de forma independente por Jacques Hadamard e Charles Jean de la Vallée-Poussin e apareceram no mesmo ano (1896). Ambas as provas utilizaram métodos de análise complexa, estabelecendo como um passo importante da prova que a função zeta de Riemann ζ(s) é não negativa para todos os valores complexos da variável s que tem a forma s = 1 + it com t > 0.
Durante o século XX, o teorema de Hadamard e de la Vallée-Poussin tornou-se conhecido como o teorema dos números primos. Várias provas diferentes dele foram encontradas, incluindo as provas "elementares" de Atle Selberg e Paul Erdős (1949). Enquanto as provas originais de Hadamard e de la Vallée-Poussin são longas e complicadas, provas posteriores introduziram várias simplificações através do uso dos teoremas de Tauberian mas mantiveram-se difíceis de assimilar. Uma prova curta foi descoberta em 1980 pelo matemático estadunidense Donald J. Newman. A prova de Newman é talvez a prova mais simples conhecida do teorema, embora seja não elementar, uma vez que usa o teorema integral de Cauchy de análise complexa.

## Demonstrações elementares

Na primeira metade do século XX, alguns matemáticos (notavelmente, G. H. Hardy) acreditavam que existe uma hierarquia de métodos de demonstração em matemática, dependendo do tipo de números (inteiros, reais, complexos) que uma demonstração requer, e que o teorema dos números primos (TNP) é um teorema "profundo" em virtude de requerer análise complexa. Essa crença foi um pouco abalada por uma demonstração do TNP com base no teorema tauberiano de Wiener, embora isso pudesse ser posto de lado se o teorema de Wiener fosse considerado como tendo uma "profundidade" equivalente a dos métodos de variáveis complexas. Não existe uma definição rigorosa e amplamente aceita da noção de demonstração elementar em teoria dos números. Uma definição é "uma prova de que pode ser realizada com aritmética de Peano de primeira ordem." Há enunciados de teoria dos números (por exemplo, o teorema de Paris–Harrington) que são demonstráveis usando-se aritmética de segunda ordem mas não com métodos de aritmética de primeira ordem, mas até o presente momento conhece-se poucos teoremas assim.
Em março de 1948, Atle Selberg estabeleceu, por métodos elementares, a fórmula assintótica
    $\vartheta \left(x\right)\log \left(x\right)+\sum \limits _{p\leq x}{\log \left(p\right)}\ \vartheta \left({\frac {x}{p}}\right)=2x\log \left(x\right)+O\left(x\right)$
em que
    $\vartheta \left(x\right)=\sum \limits _{p\leq x}{\log \left(p\right)}$
para primos $p$. Em julho daquele ano, Selberg e Paul Erdös tinham cada um obtido demonstrações elementares do TNP, ambos usando a fórmula assintótica de Selberg como ponto de partida. Essas provas efetivamente colocaram para descansar a noção de que o TNP era "profundo", e mostraram que, tecnicamente, métodos "elementares" (em outras palavras, aritméticas de Peano) eram mais poderosos do que se acreditava ser o caso. Em 1994, Charalambos Cornaros e Costas Dimitracopoulos demonstraram o TNP usando apenas $I\Delta _{0}+\exp$, um sistema formal muito mais fraco do que a aritmética de Peano.

## Tabela de π(x), x / ln x e Li(x)

A tabela seguinte compara os valores de π(x) com as aproximações x / ln x e Li(x). A quarta coluna, x / π(x), é a distância média entre os primos abaixo de x.
    x π(x) π(x) / (x / ln x) x / π(x) π(x) − x / ln x Li(x) − π(x) 10 4 0,921 2,500 −0,3 2,2 10² 25 1,151 4,000 3,3 5,1 10³ 168 1,161 5,952 23 10 10$^4$ 1.229 1,132 8,137 143 17 10$^5$ 9.592 1,104 10,425 906 38 10$^6$ 78.498 1,084 12,740 6.116 130 10$^7$ 664.579 1,071 15,047 44.158 339 10$^8$ 5.761.455 1,061 17,357 332.774 754 10$^9$ 50.847.534 1,054 19,667 2.592.592 1.701 10$^{10}$ 455.052.511 1,048 21,975 20.758.029 3.104 10$^{11}$ 4.118.054.813 1,043 24,283 169.923.159 11.588 10$^{12}$ 37.607.912.018 1,039 26,590 1.416.705.193 38.263 10$^{13}$ 346.065.536.839 1,034 28,896 11.992.858.452 108.971 10$^{14}$ 3.204.941.750.802 1,033 31,202 102.838.308.636 314.890 10$^{15}$ 29.844.570.422.669 1,031 33,507 891.604.962.452 1.052.619 10$^{16}$ 279.238.341.033.925 1,029 35,812 7.804.289.844.393 3.214.632 10$^{17}$ 2.623.557.157.654.233 1,027 38,116 68.883.734.693.281 7.956.589 10$^{18}$ 24.739.954.287.740.860 1,025 40,420 612.483.070.893.536 21.949.555 10$^{19}$ 234.057.667.276.344.607 1,024 42,725 5.481.624.169.369.960 99.877.775 10$^{20}$ 2.220.819.602.560.918.840 1,023 45,028 49.347.193.044.659.701 222.744.644 10$^{21}$ 21.127.269.486.018.731.928 1,022 47,332 446.579.871.578.168.707 597.394.254 10$^{22}$ 201.467.286.689.315.906.290 1,021 49,636 4.060.704.006.019.620.994 1.932.355.208 10$^{23}$ 1.925.320.391.606.818.006.727 1,020 51,939 37.083.513.766.592.669.113 7.236.148.412