Primos y criptografía · Definición

Teorema de los números primos

teoría de números elementalprimos y criptografía

Antes de empezar necesitas conocer

Los primos parecen distribuirse de forma irregular, pero su densidad sigue un patrón preciso a gran escala. Este teorema formaliza esa regularidad.

Definición

El teorema de los números primos describe el comportamiento asintótico de π(x), la cantidad de primos menores o iguales que x, cuando x tiende a infinito.

\[\pi(x) \sim \frac{x}{\ln x}\]

Si \(\pi(x) \sim \frac{x}{\ln x}\), entonces el cociente \(\pi(x)/(x/\ln x)\) tiende a 1 cuando \(x\) crece sin límite. Equivalentemente, el \(n\)-ésimo primo \(p_n\) satisface \(p_n \sim n \ln n\). La estimación implica que, en promedio, un entero cercano a \(x\) tiene probabilidad aproximada \(1/\ln x\) de ser primo.

Por ejemplo, para x = 100 se tiene π(100) = 25, mientras que 100/ln 100 ≈ 21.7. El cociente es cercano a 1.15, lo que muestra que la aproximación es buena aunque no exacta para valores pequeños de x. La estimación mejora conforme x crece.

Un error típico es creer que el teorema da una fórmula exacta para π(x) o para el n-ésimo primo. El resultado es asintótico: describe el límite del cociente, no el valor exacto. Confundir ~ con = lleva a conclusiones falsas para valores finitos de x.

Para pensar

¿Por qué el teorema da una estimación y no una fórmula exacta para \(\pi(x)\)?

Porque el resultado es asintótico: describe el límite del cociente \(\pi(x)/(x/\ln x)\), no el valor exacto de \(\pi(x)\) para cada \(x\).

Ejercicios 10

  1. ¿Qué significa π(x) en el teorema de los números primos?
  2. ¿Qué dice el teorema sobre el comportamiento de π(x) cuando x tiende a infinito?
  3. ¿Qué símbolo se usa para indicar que dos funciones son asintóticamente equivalentes?
  4. Según el teorema, ¿a qué tiende el cociente π(x)/(x/ln x) cuando x crece?
  5. ¿Cuál es el valor aproximado de π(100)?
  6. Si π(x) ~ x/ln x, ¿cuál es la estimación aproximada de π(1000) usando x/ln x?
  7. ¿Cuál es la probabilidad aproximada de que un entero cercano a x = 1000 sea primo, según el teorema?
  8. Si \(p_n \sim n \ln n\), ¿qué estimación aproximada da el teorema para el 100-ésimo primo?
  9. ¿Cuál es el valor aproximado del cociente π(100)/(100/ln 100)?
  10. Sea f(x) = π(x) y g(x) = x/ln x. Si π(x) ~ g(x), ¿cuál de las siguientes afirmaciones es verdadera para x grande?

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 16
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 8