4.7 Applications of prime factorization

The Fundamental Theorem of Arithmetic (Theorem 4.6.5) has a number of important consequences; in this section we shall explore some of them. The first goes back all the way to Euclid (again!), and concerns the question of how many prime numbers there are.

At the beginning of Section 4.6 we saw the technique of the Sieve of Eratosthenes to find the first few prime numbers; it consisted of taking a grid of the first so many natural numbers and crossing out all multiples of $2$, then all multiples of $3$, then all multiples of $5$ and so on, and afterwards the numbers which remained were the primes. We took only a fairly small grid, with the numbers up to $100$; if we had taken a larger grid (say, all the numbers up to $1\>000\>000$), we would have had to go through rather more times crossing out. Is it possible that, if we were to go far enough, there would come a point beyond which all the numbers were crossed out? In other words, might there only be a finite number of prime numbers? Euclid was able to show that the answer to these questions is ‘‘no’’. We shall give Euclid’s proof, essentially unchanged after more than $2000$ years.

Proof. The proof is by contradiction. Assume that there are only finitely many prime numbers, say $p_{1},p_{2},\dots,p_{n}$, where $n\in\mathbb{N}$, and consider the number

Theorem 4.6.5 implies that $N$ can be written as a product of primes, so $p_{j}$ must divide $N$ for some $j\in\{1,2,\ldots,n\}$; but this is a contradiction, since $N$ is of the form $qp_{j}+1$ for some $q\in\mathbb{N}$. Thus there must be infinitely many prime numbers in $\mathbb{N}$. $\Box$

There we are; just a few short lines of argument, but they settle the matter beyond any doubt, showing in particular how powerful the technique of proof by contradiction is.

Euclid’s result above did not require the full force of the Fundamental Theorem of Arithmetic, since it only needed the existence of prime factorizations, not their uniqueness. In the other applications which we shall consider, both parts of the Fundamental Theorem of Arithmetic will be needed.

We begin with a notational convention: it is customary to write the factors in a product of primes in ascending order of size, and to collect together equal factors, writing $p^{a}$ for $a$ factors equal to $p$. Thus we write a given number $n$ as ${p_{1}}^{a_{1}}{p_{2}}^{a_{2}}\cdots{p_{r}}^{a_{r}}$ for some $r\in\mathbb{N}$, where $p_{1},p_{2},\ldots,p_{r}$ are prime numbers with $p_{1}<p_{2}<\cdots<p_{r}$, and $a_{1},a_{2},\ldots,a_{r}\in\mathbb{N}$. (Note that this notation does not imply that $p_{1},p_{2},\dots,p_{r}$ are the first $r$ prime numbers.)

It is often convenient to relax the requirement $a_{1},\ldots,a_{r}\in\mathbb{N}$ to $a_{1},\ldots,a_{r}\in\mathbb{N}_{0}$, with the obvious convention that $p^{0}=1$ (this is particularly useful when comparing the prime factorizations of two or more numbers). Given the prime factorization of a natural number, it is now easy to obtain its positive factors.

Proof. ‘‘$\Rightarrow$.’’ Suppose that $m\in\mathbb{N}$ is a factor of $n$, say $n=mq$, where $q\in\mathbb{N}$. Since the prime factorization of $mq$ is obtained by joining together those of $m$ and $q$, the only possible prime factors of $m$ and $q$ are $p_{1},p_{2},\dots,p_{r}$. Writing

we obtain

Using the uniqueness of prime factorization, we may equate powers of $p_{j}$, from which we conclude that $a_{j}=b_{j}+c_{j}\geqslant b_{j}$ for each $j\in\{1,2,\ldots,r\}$.

‘‘$\Leftarrow$’’. Conversely, it is clear that each number of the form $m={p_{1}}^{b_{1}}{p_{2}}^{b_{2}}\cdots{p_{r}}^{b_{r}}$, where $b_{j}\in\{0,1,\ldots,a_{j}\}$ for each $j\in\{1,2,\ldots,r\}$, is a factor of $n$. $\Box$

This result enables us to compute the number of positive factors of a given number.

Proof. This follows from Proposition 4.7.3, as there are $a_{j}+1$ choices for each $b_{j}.$ $\Box$

We next introduce a standard piece of notation.

Proof. We may assume $a\leqslant b$, and then $\min\{a,b\}=a$ and $\max\{a,b\}=b.$ $\Box$

We can now explain how prime factorizations can be used to find the highest common factor and lowest common multiple of two natural numbers.

Proof. By Proposition 4.7.3, each factor $k$ of $m$ has the form $k={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots{p_{r}}^{e_{r}}$, where $e_{j}\leqslant a_{j}$ for each $j\in\{1,2,\ldots,r\}$; if $k$ is also to be a factor of $n$, we require that $e_{j}\leqslant b_{j}$ for each $j\in\{1,2,\ldots,r\}$ as well. Thus the set of common factors of $m$ and $n$ consists of the numbers $k={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots{p_{r}}^{e_{r}}$ with $e_{j}\leqslant a_{j},b_{j}$ for each $j\in\{1,2,\ldots,r\}$; the largest possible such value of $e_{j}$ is $c_{j}=\min\{a_{j},b_{j}\}$, so the highest common factor is as described.

Theorem 4.5.5 implies that

where, for each $j\in\{1,2,\ldots,r\}$,

by Lemma 4.7.9, as required. $\Box$