What is Mathematics: Prime numbers

This is the second in the series of posts on the book What is Mathematics. This post is about some important results on prime numbers.

One of the most basic results is that there are infinitely many primes. As a kid in middle or high school, I remember being fascinated by the proof of this result. The proof, given by Euclid, is straightforward and is a great example of an "indirect proof". You start by assuming that there are only a finite number of primes. Then consider the number, n, that is one more than the product of all these primes. Since n is larger than all the primes, it is not prime, and must have prime factors. But n is clearly not divisible by any of these primes (by construction, dividing by any prime leaves a remainder of 1). This leads to a contradiction, so that our assumption must be false and there are, indeed, infinitely many primes.

The fundamental theorem of arithmetic (again given by Euclid) states that every integer greater than 1 can be factored into a product of primes in only one way. The book has a very nice proof of this theorem (again an "indirect proof" that starts by assuming that the prime factorization is not unique).

There have been various attempts to find formulae that produce primes, though no such general formula has been found. However, the prime number theorem provides a remarkable formula for the distribution of primes. Let A_n denote the number of primes from 1 to n. Then the prime number theorem states that (A_n / n) tends to (1 / log n) as n tends to infinity (where log n is the natural logarithm of n). The proof of this theorem requires advanced methods and is not discussed in the book (though there's apparently some discussion toward the end).

The book introduces some interesting open problems related to primes. Of these, the most famous is Goldbach's conjecture. This conjecture states that any even number greater than 2 can be expressed as a sum of two primes. Goldbach proposed this in 1742 in a letter to Euler, asking Euler to prove or disprove it. Empirically the result appears to be true. However, while much progress has been made, the proof remains elusive.

Finally, a fundamentally important theorem due to Fermat (also called Fermat's little theorem) states that if p is a prime that does not divide the integer a then

a^{p - 1} ≡ 1 (mod p)

where (mod p) says that the congruence (≡) is modulo p (i.e., both sides have the same remainder when divided by p). The proof in the book is based on observing that no pair of multiples of a of the form ka (where 1 ≤ k < p) can be congruent modulo p. For if k₁a ≡ k₂a (mod p), then (k₁ - k₂)a ≡ 0 (mod p) which implies that a is divisible by p (since both k₁ and k₂ are less than p). Similarly, ka cannot be congruent to 0 (mod p). Thus, each of the above (p - 1) multiples of a are congruent to (a distinct) one of 1, 2, ..., (p - 1), and therefore

1 × 2 × ... × (p - 1) a^{p - 1} ≡ 1 × 2 × ... × (p - 1) (mod p)

from which the result follows.

On a side note, Fermat's little theorem plays a central role in the Miller-Rabin primality test. Primality testing is essential to the RSA public key cryptosystem that is used to secure various web-based activities like ecommerce, online banking, and online stock trading using https.