Prime Numbers Overview

Overview

This lecture explores the nature, distribution, and patterns of prime numbers, focusing on their unpredictability and the mathematical quest to understand how primes are distributed along the number line.

What Are Prime Numbers?

• A prime number is a whole number greater than one that has exactly two factors: 1 and itself.
• Composite numbers can be factored into smaller factors and ultimately into primes.
• The fundamental theorem of arithmetic states that every integer >1 is uniquely a product of primes.

Identifying Prime Numbers

• To check if a number n is prime, only test divisibility by primes up to the square root of n (square root shortcut).
• All whole numbers greater than 1 are either prime or products of primes.

Infinitude of Primes and Euclid’s Proof

• Assume a finite list of primes; multiply them and add 1 to get a new number n.
• n is either prime or has prime factors not in the original list, showing there are infinitely many primes.

Finding Primes: Sieve of Eratosthenes

• Cross out multiples of each prime starting from 2 to identify all primes within a range.
• The Sieve efficiently lists primes and reveals their thinning density as numbers grow.

Prime Density and Patterns

• The proportion of primes among integers decreases as numbers get larger.
• Average gap between consecutive primes grows slowly as numbers increase.

Logarithms and Prime Gaps

• The average gap between primes, x/π(x), resembles the shape of the natural logarithm, ln(x).
• As x grows, the difference between the actual average gap and ln(x) decreases.

The Prime Number Theorem

• π(x), the number of primes up to x, is approximately x/ln(x) as x becomes very large.
• The ratio π(x) to x/ln(x) approaches 1 as x tends to infinity.
• The logarithmic integral, Li(x), is an even better approximation for π(x).

Historical Contributions

• Legendre proposed a formula for π(x) involving a constant correction in the denominator.
• Carl Friedrich Gauss, at age 15, conjectured that the distribution of primes follows the logarithmic integral.
• In 1859, Riemann introduced the zeta function, linking it to prime distribution and making the famous Riemann Hypothesis.
• The Prime Number Theorem was rigorously proved in 1896 by Hadamard and de la Vallée-Poussin.

Key Terms & Definitions

• Prime Number — A number with exactly two distinct positive divisors: 1 and itself.
• Composite Number — A number with more than two factors.
• Fundamental Theorem of Arithmetic — Every integer >1 is the product of primes in exactly one way.
• π(x) — The prime counting function; number of primes ≤ x.
• Sieve of Eratosthenes — An algorithm for finding all primes ≤ n.
• Natural Logarithm (ln(x)) — The logarithm to base e, where e ≈ 2.718.
• Logarithmic Integral (Li(x)) — An integral used to approximate π(x).
• Prime Number Theorem — States π(x) ~ x/ln(x) as x → ∞.

Action Items / Next Steps

• Practice identifying primes and using the square root shortcut.
• Understand and apply the Sieve of Eratosthenes.
• Review the statements and implications of the Prime Number Theorem.