## Prime Numbers and the Unique Factorisation Theorem

For present purposes a prime number is understood to be a positive number other than 1 that is only divisible by itself or ±1. It is easy to see inductively that every positive number is either a prime or can be expressed as a product of primes. A positive number (other than 1) that is not prime is composite.

The ancient Greeks showed that the number of primes is infinite. The proof (by contradiction) is worth repeating:

Suppose the contrary, that there is a largest prime pn. Consider N = p1p2 … pn + 1. N leaves remainder 1 on division by pn and every lesser prime, and thus is not divisible by any of them. Since N is greater than pn it is by hypothesis not prime and thus must be divisible by a prime. Hence there is a contradiction.

The sieve of Eratosthenes yields a list of primes less than or equal to some given number N: We write out a list of the numbers, starting with 2 and ending with N. We take the first number, 2 and assume that it is prime but strike out all its multiples. Then we go to the next number, assume it is prime, and repeat the process. The numbers remaining when we have finished are all prime. An animated demonstration of the sieve can be found at its Wikipedia entry.

Let us denote as π(n) the number of primes less than or equal to n. If the primes were approximately evenly distributed among the integers, then π(n)/n would approximate a constant less than 1. It was conjectured around 1800, and proved in the 1890s, following a proof outline given by Riemann in 1859, that the density of the primes tails off slowly, in such a manner that as n becomes larger the value of π(n)/n becomes progressively closer to 1/ln n.

The Unique Factorisation Theorem (also known as the Fundamental Theorem of Arithmetic) tells us that the expression of a composite number as a product of primes is unique except for the order of the primes. It can be proved with the aid of Euclid’s Lemma (for a proof see pdf link at ‘Common Factors …’ under ‘Notes on Numbers’ – via the sidebar on the home page) which tells us that if p divides mn and (m, n) = 1 then p divides n. It follows that if p is a prime and p divides mn, then either p divides m or p divides n. This can be easily generalised as follows:

If p1, … , pn are primes and if p divides p1p2 … pn then p = pi for one of p1, … , pn.

From here it is easy to prove the Unique Factorisation Theorem by induction on the composite numbers.

An interesting and useful corollary to the theorem is that, if the prime compositions of m and n contain the primes p1, … , pn then the greatest common divisor and least common multiple of m and n consist of the same prime composition with the index of a given prime being the minimum or maximum respectively of the indexes of that prime in the prime compositions of m and n. From this it is easy to show that the product of the gcd and lcm of m and n is mn.

The content of this post in pdf form, and in a little more detail, can be found via the link with the same title in ‘Notes on Numbers’ via the side-bar on the home page.