Primes and cryptography · Definition

Prime number theorem

elementary number theoryprimes and cryptography

Before you start you need to know

Primes appear to be distributed irregularly, yet their density follows a precise pattern on a large scale. This theorem formalizes that regularity.

Definition

The prime number theorem describes the asymptotic behavior of π(x), the number of primes less than or equal to x, as x tends to infinity.

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

If \(\pi(x) \sim \frac{x}{\ln x}\), then the ratio \(\pi(x)/(x/\ln x)\) tends to 1 as \(x\) grows without bound. Equivalently, the \(n\)-th prime \(p_n\) satisfies \(p_n \sim n \ln n\). The estimate implies that, on average, an integer near \(x\) has approximate probability \(1/\ln x\) of being prime.

For example, for x = 100 we have π(100) = 25, while 100/ln 100 ≈ 21.7. The ratio is about 1.15, showing the approximation is good though not exact for small x. The estimate improves as x grows.

A typical mistake is believing the theorem gives an exact formula for π(x) or for the n-th prime. The result is asymptotic: it describes the limit of the ratio, not the exact value. Confusing ~ with = leads to false conclusions for finite x.

Think about it

Why does the theorem give an estimate rather than an exact formula for \(\pi(x)\)?

Because the result is asymptotic: it describes the limit of the ratio \(\pi(x)/(x/\ln x)\), not the exact value of \(\pi(x)\) for each \(x\).

Exercises 10

  1. What does π(x) mean in the prime number theorem?
  2. What does the theorem say about the behavior of π(x) as x tends to infinity?
  3. Which symbol denotes that two functions are asymptotically equivalent?
  4. According to the theorem, what does the ratio π(x)/(x/ln x) tend to as x grows?
  5. What is the approximate value of π(100)?
  6. If π(x) ~ x/ln x, what is the approximate estimate of π(1000) using x/ln x?
  7. What is the approximate probability that an integer near x = 1000 is prime, according to the theorem?
  8. If \(p_n \sim n \ln n\), what approximate estimate does the theorem give for the 100th prime?
  9. What is the approximate value of the ratio π(100)/(100/ln 100)?
  10. Let f(x) = π(x) and g(x) = x/ln x. If π(x) ~ g(x), which statement is true for large x?

References

  • 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