The Series of Primes

Either \(n\) is prime, when there is nothing to prove, or \(n\) has divisors between 1 and n. If \(m\) is the least of these divisors, \(m\) is prime; for otherwise \[ \exists~l \ . \ 1 < l < m \ . \ l \mid m; \] and \[ l \mid m \rightarrow l \mid n, \] which contradicts the definition of \(m\).

Hence \(n\) is prime or divisible by a prime less than \(n\), say \(p_{1}\), in which case \[ n = p_{1}n_{1}, \quad 1 < n_{1} < n. \] Here either \(n_{1}\) is prime, in which case the proof is completed, or it is divisible by a prime \(p_{2}\) less than \(n_{1}\), in which case \[ n = p_{1}n_{1} = p_{1}p_{2}n_{2}, \quad 1 < n_{2} < n_{1} < n. \] Repeating the argument, we obtain a sequence of decreasing numbers \(n, n_{1}, \dots , n_{k-1}, \dots\), all greater than \(1\), for each of which the same alternative presents itself. Sooner or later we must accept the first alternative, that \(n_{k-1}\) is a prime, say \(p_{k}\), and then \[ n = p_{1}p_{2}\dots p_{k} \] thus \(666 = 2\cdot 3 \cdot 3 \cdot 37\).

If \(ab = n\), then \(a\) and \(b\) cannot both exceed \(\sqrt{n}\). Hence any composite n is divisible by a prime \(p\), which does not exceed \(\sqrt{n}\).

The primes in the permutation are not necessarily distinct, nor arranged in any particular order.

If we arrange them in increasing order, associate sets of equal primes into single factors, and change the notation appropriately, we obtain \[ n = p^{a_{1}}_{1}p^{a_{2}}_{2}\dots p^{a_{k}}_{k} \quad (a_{1}>0, a_{2}>0, \dots,\quad p_{1} < p_{2} < \dots). \] We then say that \(n\) is expressed in standard form.

If we take Theorem 3 for granted for the moment, we can deduce Theorem 2:

It is an obvious corollary of Theorem 3 that \[ p \mid abc \dots l \rightarrow p \mid a \ or \ p \mid b \ or \ p\mid c \dots or \ p\mid l, \] and in particular that, if \(a, b,\dots,l\) are primes, then \(p\) is one of \(a,b,c,\dots,l\).

Suppose now that \[ n = p^{a_{1}}_{1}p^{a_{2}}_{2}\dots p^{a_{k}}_{k} = q^{b_{1}}_{1}q^{b_{2}}_{2} \dots q^{b_{j}}_{j}, \] each product being a product of primes in standard form. Then \(p_{i}\mid q^{b_{1}}_{1}q^{b_{2}}_{2}\dots q^{b_{k}}_{k}\) for every \(i\), so that every \(p\) is a \(q\), and similarly every \(q\) is a \(p\).

Hence \(k=j\) and, since both sets are arranged in increasing order, \(p_{i} = q_{i}\) for every \(i\).

If \(a_{i} > b_{i}\), and we divide by \(p^{a_{i}}_{i}\), we obtain \[ p^{a_{1}}_{1}\dots p^{a_{i}-b_{i}} \dots p^{a_{k}}_{k} = p^{b_{1}}_{1} \dots p^{b_{i-1}}_{i-1} p^{b_{i+1}}_{i+1} \dots p^{b_{k}}_{k}. \] The left-hand side is divisible by \(p_{i}\) while the right-hand side is not; a contradict.

Similarity, \(b_{i}>a_{i}\) yields a contradict. It follows that \(a_{i}=b_{i}\), and this completes the proof of Theorem 2.

It will now be obvious why \(1\) should not be counted as a prime. If it were, Theorem 2 would be false, since we could insert any number of unit factors.

Let \(2, 3, 5, \dots, p\) be the aggregate of primes up to \(p\), and let \[ q = 2 \cdot 3 \cdot 5 \cdots p + 1 \] Then \(q\) is not divisible by any of the numbers \(2, 3, 5, \dots, p\). It is therefore either prime, or divisible by a prime between \(p\) and \(q\). In either case there is a prime greater than \(p\), which proves the theorem.

The theorem is equivalent to \[ \pi(x) \rightarrow \infty \]

If \(p\) is the \(n\)th prime \(p_n\), and \(q\) is defined as in (2.1.1), it is plain that \[ q < p_n^n + 1 \] for \(n > 1\), and so that \[ p_{n+1} < p_n^n + 1. \]

This inequality enables us to assign an upper limit to the rate of increase of \(p_n\), and a lower limit to that of \(\pi(x)\).

We can, however, obtain better limits as follows. Suppose that

\begin{equation} p_n < 2^{2^n} \tag{2.2.1} \end{equation}

for \(n = 1, 2, \ldots, N\). Then Euclid’s argument shows that

\begin{equation} p_{N+1} \le p_1 p_2 \cdots p_N + 1 < 2^{2+4+\cdots+2^N} + 1 < 2^{2^{N+1}}. \tag{2.2.2} \end{equation}

Since (2.2.1) is true for \(n = 1\), it is true for all \(n\).

Suppose now that \(n \ge 4\) and \[ e^{e^{n-1}} < x \le e^{e^n}. \] Then \[ e^{n-1} > 2^n, \qquad e^{e^{n-1}} > 2^{2^n}; \] and so \[ \pi(x) \ge \pi(e^{e^{n-1}}) \ge \pi(2^{2^n}) \ge n, \] by (2.2.1). Since \(\log\log x \le n\), we deduce that \[ \pi(x) \ge \log\log x \] for \(x > e^{e^3}\); and it is plain that the inequality holds also for \(2 \le x \le e^{e^3}\). We have therefore proved Theorem 10.

Suppose that \(2, 3, \ldots, p_j\) are the first \(j\) primes and let \(N(x)\) be the number of \(n\) not exceeding \(x\) which are not divisible by any prime \(p > p_j\). If we express such an \(n\) in the form \[ n = n_1^2 m, \] where \(m\) is `quadratfrei’, i.e. is not divisible by the square of any prime, we have \[ m = 2^{b_1} 3^{b_2} \cdots p_j^{b_j}, \] with every \(b\) either \(0\) or \(1\). There are just \(2^j\) possible choices of the exponents and so not more than \(2^j\) different values of \(m\).

Again, \[ n_1 \le \sqrt{n} \le \sqrt{x}, \] and so there are not more than \(\sqrt{x}\) different values of \(n_1\).

Hence

\begin{equation} N(x) \le 2^j \sqrt{x}. \tag{2.6.1} \end{equation}

If Theorem 4 is false, so that the number of primes is finite, let the primes be \(2, 3, \ldots, p_j\). In this case \(N(x) = x\) for every \(x\) and s \[ x \le 2^j \sqrt{x}, \qquad x \le 2^{2j}, \] which is false as we can always find a larger number \(x\) that is greater than \(2^{2j}\).

We can use this argument to prove two further results.

Any modulus, other than the null modulus, is the aggregate of integral multiples of a positive number \(d\).

We define the highest common divisor \(d\) of two integers \(a\) and \(b\), not both zero, as the largest positive integer which divides both \(a\) and \(b\); and write \[ d = (a,b). \] Thus \((0,a) = |a|\). We may define the highest common divisor \[ (a,b,c,\ldots,k) \] of any set of positive integers \(a, b, c, \ldots, k\) in the same way.

The aggregate of numbers of the form \[ xa + yb, \] for integral \(x, y\), is a modulus which, by Theorem 23, is the aggregate of multiples \(zc\) of a certain positive \(c\). Since \(c\) divides every number of \(S\), it divides \(a\) and \(b\), and therefore \[ c \le d. \]

On the other hand, \[ d \mid a,\quad d \mid b \;\Rightarrow\; d \mid xa + yb, \] so that \(d\) divides every number of \(S\), and in particular \(c\). It follows that \[ c = d \] and that \(S\) is the aggregate of multiples of \(d\). Thus we have proved:

The modulus \(xa+yb\) is the aggregate of multiples of \(d=(a,b)\)

The equation \[ ax+by=n \] is soluble in integers \(x, y\) if and only if \(d \mid n\). In particular, \[ ax+by=d \] is soluble.

Proof:

\(ax+by=n\) is soluble in integers \(x, y\), which is equivalent to that \(n\) can be written to some form of \(ax+by\) where \(x, y \in \mathbb{Z}\). That is: \[ n \in \{ax+by : x, y \in \mathbb{Z}\} = S \] We have proved that \[ S = d\mathbb{Z}. \] Hence \[ n \in S \Longleftrightarrow n \in d\mathbb{Z} \Longleftrightarrow d\mid n \]

Any common divisor of \(a\) and \(b\) divides \(d\).

Proof:

By Theorem 25, there must exist interal \(x,y\) such that \[ ax+by = d. \] Now if \(c\mid a\) and \(c\mid b\), then \[ c \mid ax, \qquad c\mid by, \] then \[ c \mid (ax+by) = d \] Thus any common divisor of \(a\) and \(b\) divides \(d\).

Suppose that \(p\) is prime and \(p \mid ab\). If \(p \nmid a\) then \((a,p)=1\), and therefore, by theorem 24, there are an \(x\) and a \(y\) for which \(xa+yp=1\) or \[ xab+ypb = b \] But \(p\mid ab\) and \(p \mid pb\), and therefore \(p \mid b\).

Practically the same argument proves

For there are an \(x\) and a \(y\) for which \(xa+yb =d\) or \[ xac+ybc=dc. \] Hence \((ac, bc) \mid dc\).

On the other hand, \(d \mid a \Rightarrow dc \mid ac\), and \(d \mid b \Rightarrow dc \mid bc\), and therefore, by Theorem 26, \(dc \mid (ac, bc)\).

Hence \((ac, bc) = dc\).

We call numbers which can be factorized into primes in more than one way abnormal. Let \(n\) be the least abnormal number. The same prime \(P\) cannot appear in two different factorizations of \(n\), for, if it did, \(n/P\) would be abnormal and \(n/P < n\). We have then

\[ n = p_1 p_2 p_3 \cdots = q_1 q_2 \cdots, \]

where the \(p\) and \(q\) are primes, no \(p\) is a \(q\) and no \(q\) is a \(p\).

We may take \(p_1\) to be the least \(p\); since \(n\) is composite, \(p_1^2 \le n\). Similarly, if \(q_1\) is the least \(q\), we have \(q_1^2 \le n\) and, since \(p_1 \ne q_1\), it follows that \(p_1 q_1 < n\). Hence, if

\[ N = n - p_1 q_1, \]

we have \(0 < N < n\) and \(N\) is not abnormal. Now \(p_1 \mid n\) and so \(p_1 \mid N\); similarly \(q_1 \mid N\). Hence \(p_1\) and \(q_1\) both appear in the unique factorization of \(N\) and

\[ p_1 q_1 \mid N. \]

From this it follows that \(p_1 q_1 \mid n\) and hence that \(q_1 \mid n/p_1\). But \(n/p_1\) is less than \(n\) and so has the unique prime factorization \(p_2 p_3 \cdots\). Since \(q_1\) is not a \(p\), this is impossible. Hence there cannot be any abnormal numbers and this is the Theorem 2.

Suppose that, as in usual, we define \[ \pi(x) \] to be the number of primes which do not exceed x, so that \(\pi(1) = 0, \pi(2)=1, \pi(20)=8\).

If \(p_{n}\) is the n-th prime then \[ \pi(p_{n}) = n, \] so that \(\pi(x)\), as function of \(x\), and \(p_{n}\), as function of \(n\), are inverse functions.

If \[ y = \frac{x}{\ln(x)} \] then \[ \ln(y) = \ln(x)-\ln(\ln(x)) \] and \(\ln(\ln(x))=o(\ln(x))\) so that \[ \ln(y) \sim \ln(x), \qquad x = y\ln(x) \sim y\ln(y) \] From this remark we infer that Theorem 6 is equivalent to

\[ p_{n} \sim n\ln(n) \] Similarly, Theorem 7 is equivalent to to

\[ p_{n} \asymp n\ln(n) \]

There are infinitely many primes of the form \(4n+3\).

Define \(q\) by

\[ q = 2^2 \cdot 3 \cdot 5 \cdots p - 1. \]

Then \(q\) is of the form \(4n+3\), and is not divisible by any of the primes up to \(p\). It cannot be a product of primes \(4n+1\) only, since the product of two numbers of this form is of the same form; and therefore it is divisible by a prime \(4n+3\), greater than \(p\).

There are infinitely many primes of the form \(6n+5\).

The proof is similar. We define \(q\) by

\[ q = 2 \cdot 3 \cdot 5 \cdots p - 1, \]

and observe that any prime number, except \(2\) or \(3\), is \(6n+1\) or \(6n+5\), and that the product of two numbers of the form \(6n+1\) is of the same form.

The progression \(4n+1\) is more difficult. We must assume the truth of a theorem which we shall prove later (§ 20.3).

If \(a\) and \(b\) have no common factor, then any odd prime divisor of \(a^2+b^2\) is of the form \(4n+1\).

If we take this for granted, we can prove that there are infinitely many primes \(4n+1\). In fact we can prove

There are infinitely many primes of the form \(8n+5\).

We take

\[ q = 3^2 \cdot 5^2 \cdot 7^2 \cdots p^2 + 2^2, \]

a sum of two squares which have no common factor. The square of an odd number \(2m+1\) is

\[ 4m(m+1) + 1 \]

and is \(8n+1\), so that \(q\) is \(8n+5\). Observing that, by Theorem 13, any prime factor of \(q\) is \(4n+1\), and so \(8n+1\) or \(8n+5\), and that the product of two numbers \(8n+1\) is of the same form, we can complete the proof as before.

All these theorems are particular cases of a famous theorem of Dirichlet.

If \(a\) is positive and \(a\) and \(b\) have no common divisor except \(1\), then there are infinitely many primes of the form \(an+b\).

The proof of this theorem is too difficult for insertion in this book. There are simpler proofs when \(b\) is \(1\) or \(-1\).

If \(a \ge 2\) and \(a^n+1\) is prime, then \(a\) is even and \(n = 2^m\).

For if \(a\) is odd then \(a^n+1\) is even; and if \(n\) has an odd factor \(k\) and \(n = kl\), then \(a^n+1\) is divisible by

\[ \frac{a^{kl}+1}{a^l+1} = a^{(k-1)l} - a^{(k-2)l} + \cdots + 1. \]

It is interesting to compare the fate of Fermat’s conjecture with that of another famous conjecture, concerning primes of the form \(2^n-1\). We begin with another trivial theorem of much the same type as Theorem 17.

If \(n > 1\) and \(a^n-1\) is prime, then \(a = 2\) and \(n\) is prime.

For if \(a > 2\), then \(a-1 \mid a^n-1\); and if \(a = 2\) and \(n = kl\), then

\[ 2^k - 1 \mid 2^n - 1. \]

The problem of the primality of \(a^n-1\) is thus reduced to that of the primality of \(2^p-1\). It was asserted by Mersenne in 1644 that

\[ M_p = 2^p - 1 \]

is prime for

\[ p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, \]

and composite for the other 44 values of \(p\) less than \(257\). The first mistake in Mersenne’s statement was found about 1886, when Pervusin and Seelhoff discovered that \(M_{61}\) is prime. Subsequently four further mistakes were found in Mersenne’s statement and it need no longer be taken seriously. In 1876 Lucas found a method for testing whether \(M_p\) is prime and used it to prove \(M_{127}\) prime. This remained the largest known prime until 1951, when, using different methods, Ferrier found a larger prime (using only a desk calculating machine) and Miller and Wheeler (using the EDSAC 1 electronic computer at Cambridge) found several large primes, of which the largest was

\[ 180M_{127}^2 + 1, \]

which is larger than Ferrier’s. But Lucas’s test is particularly suitable for use on a binary digital computer and it has been applied by a succession of investigators (Lehmer and Robinson using the SWAC and Hurwitz and Selfridge using the IBM 7090, Riesel using the Swedish BESK, and Gillies using the ILLIAC II). As a result it is now known that \(M_p\) is prime for

\[ p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, \]

\[ 127, 521, 607, 1279, 2203, 2281, 3217, \]

\[ 4253, 4423, 9689, 9941, 11213 \]

and composite for all other \(p < 12000\). The largest known prime is thus \(M_{11213}\), a number of \(3375\) digits.

We describe Lucas’s test in § 15.5 and give the test used by Miller and Wheeler in Theorem 101.

The problem of Mersenne’s numbers is connected with that of “perfect” numbers, which we shall consider in § 16.8.

We return to this subject in § 6.15 and § 15.5.