Chapter 3 Prime Numbers
In this chapter we will examine:
- The Fundamental Theorem of Arithmetic
- Euclid’s proof that there are infinitely many prime numbers
- The Prime Number Theorem.
The first two results will be proved, but the last, concerning the distribution of primes will only be discussed.
- An integer \(p>1\) is said to be irreducible if the only positive divisors of \(p\) are \(1\) and \(p\) itself.
- It is said to be prime if for all integers \(a\) and \(b\), whenever \(p|ab\) either \(p|a\) or \(p|b\).
Note that (by definition) \(1\) is not irreducible. The smallest irreducible is \(2\), and all the other irreducibles (such as \(3, 5, 7, 11, \ldots\)) are odd.
An integer \(n>1\) which is not irreducible (such as \(4, 6, 8, 9, \ldots\)) is said to be composite; such an integer has the form \(n=ab\) where \(1<a<n\) and \(1<b<n\).
In school the definition of a prime that is given actually coincides with our definition of an irreducible number. Our first result shows that this confusion is justified:
Let \(a,p\) be integers.
- if \(p\) is irreducible, either \(p\) divides \(a\), or \(a\) and \(p\) are coprime;
- if \(p\) is irreducible then it is also prime, i.e., if \(p\) divides \(ab\), then \(p\) divides \(a\) or \(p\) divides \(b\).
- if \(p\) is prime then it is irreducible.
Proof. Let \(a,p\) be integers.
- As \(p\) is irreducible and since \(\gcd(a,p)\) is a positive divisor of \(p\), then \(\gcd(a,p)\) must be \(1\) or \(p\). If \(\gcd(a,p)=p\), then since it follows that \(p|a\) since \(\gcd(a,p)\) divides \(a\). On the other hand, if \(\gcd(a,p)=1\) then \(a\) and \(p\) are coprime.
- Suppose \(p|ab\) and that \(p\) does not divide \(a\). Then by part (1) \(\gcd(a,p)=1\). Hence by Corollary 2.25(b) it follows that \(p|b\) as required.
- Suppose that \(p\) is prime and that \(p=ab\). Notice that we can assume that \(a,b>0\). Since \(p\) is prime then \(p|a\) or \(p|b\). Suppose, without loss of generality, that \(p|a\) so that \(a=kp\) for some integer \(k\). Then \(p=kpb\) and hence by the cancellation lemma, it follows that \(kb=1\) and so \(b\le 1\). But \(b>0\) and so \(b=1\), and \(p\) is irreducible as required.
If \(p\) is prime and \(p\) divides \(a_1\ldots a_k\), then \(p\) divides \(a_i\) for some \(i\).
Proof. We will carry out (weak) induction on \(k\). If \(k=1\) then the assumption is that \(p|a_1\), so the conclusion is automatically true (with \(i=1\)).
Now assume, by way of induction, that \(k\ge1\) and that the result is proved for all products of \(k\) factors \(a_i\). Let \(a=a_1\ldots a_k\) and \(b=a_{k+1}\) so that \(a_1\ldots a_{k+1}=ab\) and then \(p|ab\). Since \(p\) is prime it follows that \(p|a\) or \(p|b\). In the first case we have \(p|a_1\ldots a_k\) and the induction hypothesis implies that \(p|a_i\) for some \(i=1, \ldots, k\). Otherwise we have \(p|a_{k+1}\). Thus in either case \(p|a_i\) for some \(i\), as required.
We now come to one of the most important theorems in elementary number theory.
Each integer \(n>1\) has a prime-power factorisation \[n=p_1^{e_1}\ldots p_k^{e_k}\,,\] where \(p_1, \ldots, p_k\) are distinct primes and \(e_1, \ldots, e_k\) are positive integers; this factorisation is unique, apart from permutations of the factors.
\(392\) has prime-power factorisation \(2^37^2\), or alternatively \(7^22^3\) if we permute the factors, but it has no other prime-power factorisations.
Proof. We use strong induction to prove the existence of prime-power factorisations. Since we are assuming that \(n>1\), the induction starts with \(n=2\). In this case the factorisation is simply \(n=2^1\). Now assume that \(n>2\) and that every integer strictly between \(1\) and \(n\) has a prime-power factorisation. If \(n\) is prime then there is nothing to do - \(n=n^1\) is the required factorisation of \(n\). So we can assume that \(n\) is composite, which means that \(n=ab\) where \(1<a, b<n\). By the induction hypothesis, both \(a\) and \(b\) have prime-power factorisations, so by substituting these into the equation \(n=ab\) and then collecting together powers of each prime \(p_i\) we get a prime-power factorisation of \(n\). We now prove that the factorisation is in fact unique. Suppose that \(n\) has prime-power factorisations \[n=p_1^{e_1}\ldots p_k^{e_k}=q_1^{f_1}\ldots q_l^{f_l}\] where \(p_1,\ldots,p_k\) and \(q_1,\ldots,q_l\) are two sets of distinct primes, and the exponents \(e_i\) and \(f_j\) are all positive integers. The first factorisation shows that \(p_1|n\), so Corollary 3.2 (applied to the second factorisation) implies that \(p_1|q_j\) for some \(j=1,\ldots, l\). By renumbering the prime-powers in the second factorisation if necessary, we may assume, for simplicities sake, that \(j=1\). Hence we have that \(p_1|q_1\). Since \(q_1\) is prime, it follows that \(p_1=q_1\) and so cancelling this prime from the two factorisations we get \[p_1^{e_1-1}p_2^{e_2}\ldots p_k^{e_k}=q_1^{f_1-1}q_2^{f_2}\ldots q_l^{f_l}.\] We repeat this argument, cancelling primes in the two factorisations, until we run out of primes in one of the factorisations. If one factorisation runs out before the other, then at that stage our reduced factorisations express \(1\) as a product of primes \(p_i\) or \(q_j\), which is impossible since \(p_i, q_j>1\).
It follows that both factorisations run out of primes simultaneously, so we must have cancelled the \(e_i\) copies of each \(p_i\) with the same number \((f_i)\) of copies of \(q_i\). Consequently \(k=l\), each \(p_i=q_i\), and each \(e_i=f_i\) and it follows that the factorisation is unique.
Find the prime power factorisation of 115, of 188 and of 2020.
As an example of an application of the Fundamental Theorem of Arithmetic, consider the following useful and interesting property (you may have come across the case when \(m=2\)).
If a positive integer \(m\) is not a perfect square then \(\sqrt m\) is irrational.
Proof. It is sufficient to prove the contrapositive, that if \(\sqrt m\) is rational then \(m\) is a perfect square. Since we are now considering integers as real numbers we allow ourselves to divide by them (division by \(b\) means multiplication by the real number \(1/b\)) Suppose that \(\sqrt m=a/b\) where \(a\) and \(b\) are coprime positive integers and assume, by way of contradiction, that \(a, b\geq 2\).
Then the prime factorisations \(a=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}\), \(b=q_1^{f_1}q_2^{f_2}\ldots q_l^{f_l}\) cannot have any primes in common, otherwise the common prime would be a common factor, and coprime integers have no common factors.
Furthermore the prime factorisations of \(a^2\) and of \(b^2\) can have no common prime factors since they are obtained by squaring the prime factorisations for \(a\) and \(b\) respectively. Since \(mb^2=a^2\), the prime factorisation of \(mb^2\) has the form \(mb^2=p_1^{2e_1}p_2^{2e_2}\ldots p_k^{2e_k}\), so \(p_i^{2e_i}\) divides \(mb^2\) for each \(i\).
But \(b^2\) is coprime to \(p_i^{2e_i}\) so by Corollary 2.25 (b) \(p_i^{2e_i}\) must be a factor of \(m\). Furthermore by Corollary 2.25 (a) since the prime factors \(p_i^{2e_i}\) are mutually coprime, their product divides \(m\), hence \(a^2|m\) and in particular \(a^2\le m\).
But \(b\geq2\) so \(m< 4m\le mb^2\) and together we get \(a^2\le m< mb^2=a^2\). This is a contradiction so our assumption that \(\sqrt{m}=a/b\) was false with \(a, b\geq 2\).
It follows that if \(\sqrt{m}=a/b\) then either \(b=1\) (in which case \(\sqrt{m}=a\), and \(m=a^2\) as required) or \(a=1\) (in which case \(mb^2=1\) and so \(m=1=1^2\) as required).
Distribution of Primes
There are infinitely many primes.
The fact that there are infinitely many primes, is one of the oldest and most attractive results in mathematics. Here we give the proof given in Book IX of Euclid’s Elements.
Proof. The proof is by contradiction: we assume that there are only finitely many primes, and then we obtain a contradiction from this, so it follows that there must be infinitely many primes.
Suppose that the only primes are \(p_1, p_2, \ldots, p_k\) and let \[m=p_1p_2\ldots p_k+1\,.\]
Since \(m\) is an integer greater than \(1\), the Fundamental Theorem of Arithmetic (Theorem 3.3) implies that it is divisible by some prime \(p\).
But we assumed that the only primes are \(\{p_1,\ldots,p_k\}\) and so \(p=p_i\) for some \(i\).
Since \(p\) divides both \(m\) and \(p_1p_2\ldots p_k\) it divides the difference, \(m-p_1p_2\ldots p_k=1\), which is impossible.
Consequently, our initial assumption was false, and so there must be infinitely many primes.
Let \(s_n = n!-1\). Use the sequence \(s_n\) and Theorem 3.3 to show that there are infinitely many primes.
We can use Euclid’s proof to obtain a little more information about how frequently prime numbers occur. Let us order the primes with \(p_n\) denoting the \(n\)-th prime, so that \(p_1=2,\, p_2=3,\, p_3=5\), and so on.
The \(n\)-th prime \(p_n\) satisfies \(p_n\le 2^{2^{n-1}}\) for all \(n\geq 1\).
NOTE: This is not a very useful result as the difference between \(p_n\) and \(2^{2^{n-1}}\) grows very large, very quickly.
\[ \begin{array}{c|c|l} n&p_n&2^{2^{n-1}}\\\hline 1&2&2\\ 2&3&4\\ 3&5&16\\ 4&7&256\\ 5&11&65536\\ 6&13&4294967296\\ 7&17&18446744073709551616\\ 8&19&3.4028236692093846346337460743177\times 10^{38}\\ \end{array} \]
Proof. We use strong induction on \(n\). The result is true for \(n=1\), since \(p_1=2=2^{2^0}\). Now assume that the result is true for each \(n=1, 2, \ldots, k\).
As in the proof of Theorem 3.7, \(p_1p_2\ldots p_k+1\) must be divisible by some prime \(p\), which cannot be one of \(p_1, p_2,\ldots, p_k\), for then it would divide \(1\) - a contradiction.
Now this new prime \(p\) must be at least as large as the \((k+1)\)-th prime, \(p_{k+1}\), so, using the strong induction hypothesis, that \(p_i\le 2^{2^{i-1}}\) for \(i\le k\), \[p_{k+1}\le p\le p_1p_2\ldots p_k+1 \le 2^{2^0}2^{2^1}\ldots 2^{2^{k-1}}+1\]
Hence: \[ p_{k+1}\le2^{1+2+4+\cdots+2^{k-1}}+1.\] Recalling the formula for the sum of the finite geometric series \[\sum\limits_{i=0}^{k-1}2^i=2^k-1.\] we get: \[ p_{k+1}\le2^{2^k-1}+1 =\frac{1}{2}.2^{2^k}+1\le \frac{1}{2}.2^{2^k}+\frac{1}{2}.2^{2^k}=2^{2^k}.\] This proves the inequality for \(n=k+1\), so by induction it is true for all \(n\geq 1\).
Corollary 3.9 is a VERY weak estimate.
By compiling extensive lists of primes, Gauss conjectured in 1793 that the number of primes less than \(x\), which we denote by \(\pi(x)\), is approximated by the function \[\text{li}\,x=\int_2^x\frac{dt}{\ln t}\,\] or equivalently by \(x/\ln x\) in the sense that \[\frac{\pi(x)}{x/\ln x}\to 1\quad\text{as}\quad x\to\infty\,.\]
Here \(\ln x=\log_{\text{e}}x\) is the natural logarithm \(\int_1^xt^{-1}dt\) of \(x\). This result, known as the Prime Number Theorem, was eventually proved by Hadamard and de la Vall'ee Poussin in 1896.
One can interpret the Prime Number Theorem as showing that the proportion \(\pi(x)/\lfloor x\rfloor\) of primes among the positive integers \(i\le x\) is approximately \(1/\ln x\) for large \(x\). \[ \begin{array}{r|r|r|r} x&\pi(x)&\pi(x)/\lfloor x\rfloor&1/\ln(x)\\\hline 2&1&0.5&1.44\\ 3&2&0.67&0.91\\ 10&4&0.4&0.434\\ 20&8&0.4&0.334\\ 50&15&0.3&0.256\\ 100&25&0.25&0.217\\ 1000&168&0.168&0.145\\ 10000&1229&0.1229&0.109\\ 100000&9592&0.09592&0.087\\ \end{array} \] Since \(1/\ln(x)\to0\) as \(x\to\infty\), this shows that the primes occur less frequently among larger integers than among smaller integers. For instance there are \(168\) primes between \(1\) and \(1000\), then \(135\) primes between \(1001\) and \(2000\), then \(127\) between \(2001\) and \(3000\), and so on.
You can read a lot more about this topic in the book: The Music of the Primes: Why an Unsolved Problem in Mathematics Matters, by Marcus du Sautoy.
Decide how many zeros there are at the end of the integer \(100!\) in its decimal notation.
Solution. If an integer has exactly \(n\) zeros at the end then it is divisible by \(10^n\) but not by \(10^{n+1}\). It is clear that this is true if it is divisible by \(2^n\) and by \(5^n\) but not by \(2^{n+1}\) and \(5^{n+1}\).
Now by the prime factorisation theorem the prime factors of \(100!\) are precisely the prime factors of its factors \(1,\ldots , 100\). Half of these are even and these each contribute at least one factor of \(2\). Hence we obtain \(50\) factors of \(2\). However of these fifty integers half are divisible by \(4\) so these 25 each contribute an additional factor of \(2\). Now of these 25, 12 are divisible by \(8\) so each contribute three factors of \(2\), and of these \(6\) contribute four factors of \(2\). Three of these contribute five factors of \(2\), one contributes \(6\), so in total we see \(50+25+12+6+3+1= 97\) factors of \(2\) in \(100!\).
Similarly we see \(20+4=24\) factors of \(5\) in \(100!\). So there are \(24\) zeros at the end of \(100!\).