Divisibility and Primes - Applications

The theory of divisibility has profound applications throughout mathematics. One of the most beautiful classical results is the infinitude of primes, first proved by Euclid around 300 BCE using an elegant argument by contradiction.

TheoremInfinitude of Primes

There are infinitely many prime numbers.

Euclid's proof is a masterpiece of mathematical reasoning. Suppose, for contradiction, that there are only finitely many primes $p_1, p_2, \ldots, p_n$ . Consider the number: $N = p_1 p_2 \cdots p_n + 1$

By the Fundamental Theorem of Arithmetic, $N$ has a prime divisor $p$ . This prime $p$ must be one of $p_1, \ldots, p_n$ , say $p = p_i$ . Then $p_i \mid N$ and $p_i \mid p_1 p_2 \cdots p_n$ , so: $p_i \mid (N - p_1 p_2 \cdots p_n) = 1$

This is impossible since no prime divides $1$ . The contradiction shows our assumption was false.

Remark

There are many other proofs of the infinitude of primes. Euler proved it using the divergence of the harmonic series of primes: $\sum_{p \text{ prime}} \frac{1}{p} = \infty$

This analytic approach opened the door to analytic number theory and the study of prime number distribution.

TheoremDirichlet's Theorem on Arithmetic Progressions

Let $a$ and $d$ be coprime positive integers with $\gcd(a, d) = 1$ . Then the arithmetic progression: $a, a + d, a + 2d, a + 3d, \ldots$ contains infinitely many prime numbers.

Dirichlet's theorem, proved in 1837, is a far-reaching generalization of the infinitude of primes. Its proof requires sophisticated techniques from analytic number theory, including Dirichlet $L$ -functions and character theory.

ExamplePrimes in Arithmetic Progressions

Consider primes of the form $4k + 3$ : $3, 7, 11, 19, 23, 31, 43, 47, \ldots$

Dirichlet's theorem guarantees infinitely many such primes. Similarly, there are infinitely many primes of the form $4k + 1$ : $5, 13, 17, 29, 37, 41, 53, 61, \ldots$

For the progression $3k + 1$ (with $a = 1, d = 3$ ), we have $\gcd(1, 3) = 1$ , so: $7, 13, 19, 31, 37, 43, 61, 67, \ldots$ contains infinitely many primes.

TheoremBertrand's Postulate

For every integer $n \geq 1$ , there exists at least one prime $p$ such that $n < p < 2n$ .

Bertrand's Postulate, conjectured by Joseph Bertrand in 1845 and proved by Chebyshev in 1850, shows that primes are relatively dense. A simpler proof was later given by Erdős using binomial coefficients.

ExampleBertrand's Postulate Verified

For $n = 10$ : the prime $11$ satisfies $10 < 11 < 20$
For $n = 20$ : the prime $23$ satisfies $20 < 23 < 40$
For $n = 100$ : the prime $101$ satisfies $100 < 101 < 200$

In fact, there are usually many primes in the interval $(n, 2n)$ , not just one. For $n = 100$ , there are 21 primes between 100 and 200.

These classical results demonstrate the rich structure of prime numbers and have inspired centuries of mathematical research into their distribution and properties.