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, 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) \]