NTIC The Prime Counting Function

Chapter 21 The Prime Counting Function

Up to now, our examples of arithmetic functions

f (n)

have been clearly based on some property of the number

n

itself, such as its divisors, the numbers coprime to it, and so forth.

🔗

However, there is one function of prime importance which, as far as we yet know, bears no particularly obvious relation to the input – yet in the aggregate bears amazing relations to the input! It is the most mysterious one of all.

🔗

Definition 21.0.1.

The prime counting function $π (x)$ is defined, for all positive numbers $x,$ as the number of primes less than or equal to $x,$ denoted

π (x) = # {p \leq x ∣ p is prime} .

🔗

Summary: The Prime Counting Function

Here, we harness the power of the Legendre symbol to find a deep correlation between solutions of two seemingly unrelated congruences – a correlation that enables us to tell very quickly whether any quadratic congruence has a solution!

Section 21.1 introduces the prime counting function $π (x) .$
Section 21.2 gives some history and cool graphics to help suggest there is some regularity in this behavior.
In the next section we state the Theorem 21.3.1, and show that $π (x)$ is $O (x / \log (x))$ in Proposition 21.3.7.
Then in Section 21.4 we see a small piece of the methods one might use in proving the whole theorem.

The Exercises help fill in details of the proofs and give experience thinking about asymptotic behavior.