Home page for accesible maths 4 Number theory 4.5 Lowest common multiples 4.7 Applications of prime factorization

Style control - access keys in brackets

Font (2 3) - + Letter spacing (4 5) - + Word spacing (6 7) - + Line spacing (8 9) - +

4.6 Prime numbers

The concept of a prime number is fundamental to number theory. For the next two sections we confine ourselves to the natural numbers $\mathbb{N}$ .

Definition 4.6.1

Let $p\in\{2,3,4,\ldots\}$ . We say that $p$ is prime if the only natural numbers which divide $p$ are $1$ and $p$ itself; otherwise $p$ is composite.

Note that $1$ is neither prime nor composite. If $n$ is composite, then for some natural number $a$ satisfying $1<a<n$ we have $a|n$ ; so $n=ab$ with $a,b\in\{2,3,\ldots,n-1\}$ .

It is easy to list the first few prime numbers: $2,3,5,7,\ldots$ A convenient way of obtaining a longer list is called the Sieve of Eratosthenes: begin with a grid listing the first $100$ (say) natural numbers.

\begin{array}[]{|c|c|c|c|c|c|c|c|c|c|}\omit&\omit&\omit&\omit&\omit&\omit&% \omit&\omit&\omit&\omit\\ \hline\vrule width 0.0pt depth 10.0pt height 18.0pt1&2&3&4&5&6&7&8&9&10\\ \hline\vrule height 18.0pt depth 10.0pt width 0.0pt11&12&13&14&15&16&17&18&19&% 20\\ \hline\vrule height 18.0pt width 0.0pt depth 10.0pt21&22&23&24&25&26&27&28&29&% 30\\ \hline\vrule depth 10.0pt width 0.0pt height 18.0pt31&32&33&34&35&36&37&38&39&% 40\\ \hline\vrule height 18.0pt depth 10.0pt width 0.0pt41&42&43&44&45&46&47&48&49&% 50\\ \hline\vrule width 0.0pt depth 10.0pt height 18.0pt51&52&53&54&55&56&57&58&59&% 60\\ \hline\vrule height 18.0pt depth 10.0pt width 0.0pt61&62&63&64&65&66&67&68&69&% 70\\ \hline\vrule depth 10.0pt width 0.0pt height 18.0pt71&72&73&74&75&76&77&78&79&% 80\\ \hline\vrule width 0.0pt depth 10.0pt height 18.0pt81&82&83&84&85&86&87&88&89&% 90\\ \hline\vrule width 0.0pt depth 10.0pt height 18.0pt91&92&93&94&95&96&97&98&99&% 100\\ \hline\end{array}

Cross out $1$ , which is neither prime nor composite. Take the first remaining entry, circle it, and cross out all its successive multiples; then take the next remaining entry, circle it, and cross out all its successive multiples; and so on. At the end of the process the circled entries are the prime numbers.

The most important property of prime numbers is the following, which is a consequence of Euclid’s Lemma.

Proposition 4.6.2

Let $p,a,b\in\mathbb{N}$ . If $p$ is prime and $p|ab$ , then $p|a$ or $p|b$ .

Example 4.6.3

We have $7|28$ and $28=2\cdot 14$ , so $7|2$ or $7|14$ . (Of course, we know that it is the latter statement which is true.)

Proof. Take $a,b\in\mathbb{N}$ with $p|ab$ . If $p|a$ then we have the desired conclusion, so assume that $p\!\!\!\!\;\not\!\!\!\;|\!\;a$ ; then $\mathrm{hcf}(p,a)\neq p$ , so as $\mathrm{hcf}(p,a)|p$ we must have $\mathrm{hcf}(p,a)=1.$ By Theorem 4.4.8 we therefore have $p|b$ as required. $\Box$

Note that this property characterizes prime numbers; if $n$ is composite we may write $n=ab$ for some $a,b\in\{2,3,4,\ldots,n-1\}$ , and then $n|ab$ but $n\!\!\!\!\;\not\!\!\!\;|\!\;a$ and $n\!\!\!\!\;\not\!\!\!\;|\!\;b$ , so that $n$ fails to have the property. (Example: $6|6$ and $6=2\cdot 3$ , but $6\!\!\!\!\;\not\!\!\!\;|\!\;2$ and $6\!\!\!\!\;\not\!\!\!\;|\!\;3$ .)

Remark 4.6.4

We can easily extend Proposition 4.6.2 to cover products of more than two factors. Suppose that $p\in\mathbb{N}$ is prime and that $p|abc$ for some $a,b,c\in\mathbb{N}$ ; regarding the product as $(ab)c$ , Proposition 4.6.2 shows that we must have $p|ab$ or $p|c$ , and in the former case Proposition 4.6.2 again shows that $p|a$ or $p|b$ ; so all in all, $p$ divides one of the three factors. Likewise if $a,b,c,d\in\mathbb{N}$ with $p|abcd$ , we deduce that $p|abc$ or $p|d$ , and in the former case we have just seen that $p$ divides $a$ , $b$ or $c$ ; so again $p$ divides one of the factors. Continuing in this way (or, strictly speaking, by induction), we see that whenever $p$ divides a product of any number of factors, it must divide one of them.

We now come to a most important result, the Fundamental Theorem of Arithmetic. By a product of primes we mean an expression of the form $p_{1}p_{2}\cdots p_{n}$ for some $n\in\mathbb{N}$ and prime numbers $p_{1},p_{2},\dots,p_{n}$ ; note that if $n=1$ we obtain $p_{1}$ as the ‘‘product’’ of a single prime number.

Theorem 4.6.5

Every natural number greater than or equal to $2$ can be expressed as a product of primes; this product is unique up to the order of the factors.

The proof of this theorem relies on the Principle of Induction, which will be introduced in MATH101. We shall postpone it until the end of the module (see Appendix A).

We conclude this section with a couple of examples which highlight the difference between a proof and a counterexample.

Example 4.6.6

For each $n\in\mathbb{N}$ , consider the statement

$P(n)\colon$ ‘‘the natural number $6n-1$ is prime’’.

It is tempting to believe that $P(n)$ is true for all $n\in\mathbb{N}$ because

$\displaystyle 6\cdot 1-1$	$\displaystyle=5$	$\displaystyle\text{is prime},$
$\displaystyle 6\cdot 2-1$	$\displaystyle=11$	$\displaystyle\text{is prime},$
$\displaystyle 6\cdot 3-1$	$\displaystyle=17$	$\displaystyle\text{is prime},$
$\displaystyle 6\cdot 4-1$	$\displaystyle=23$	$\displaystyle\text{is prime},$

so that $P(n)$ is true for $n=1,2,3,4$ . However, $P(n)$ is not true in general, because

6\cdot 6-1=35=5\cdot 7\quad\text{is}\ \textsl{not}\ \text{prime,}

that is, $P(6)$ is false.

Our second example is similar, but much harder to resolve; it goes back to Fermat and is known as Fermat’s Prime Conjecture.

Example 4.6.7

For each $n\in\mathbb{N}$ , consider the statement

$P(n)\colon$ ‘‘the natural number $2^{2^{n}}+1$ is prime’’.

Then $P(n)$ is true for $n=1,2,3,4$ because $2^{2}+1=5$ , $2^{4}+1=17$ , $2^{8}+1=257$ and $2^{16}+1=65\>537$ are prime numbers. Based on these observations, Fermat conjectured that $P(n)$ is true for all $n\in\mathbb{N}$ . Euler, however, gave a counterexample to Fermat’s conjecture by showing that $P(5)$ is false; indeed, we have

2^{2^{5}}+1=2^{32}+1=4\>294\>967\>297=641\cdot 6700417.