The theory of numbers, by Robert D. Carmichael ...

12

THEORY OF NUMBERS

~ 4. THE NUMBER OF PRIMES IS INFINITE
I. The number of primes is infinite.
We shall prove this theorem by supposing that the number
of primes is not infinite and showing that this leads to a contradiction. If the number of primes is not infinite there is a
greatest prime number, which we shall denote by p. Then
form the number
V —.2.*3.e.. Xp d+ —I.
Now by theorem I of ~ 3 N has a prime divisor q. But every
non-unit divisor of N is obviously greater than p. Hence q
is greater than p, in contradiction to the conclusion that p is
the greatest prime. Thus the proof of the theorem is complete.
In a similar way we may prove the following theorem:
II. Among the integers of the arithmetic progression 5, II,
17, 23,..., there is an infinite number of primes.
If the number of primes in this sequence is not infinite
there is a greatest prime number in the sequence; supposing
that this greatest prime number exists we shall denote it by p.
Then the number N,
N=Ir-23....p-I,
is not divisible by any number less than or equal to p. This
number N, which is of the form 6n-i, has a prime factor.
If this factor is of the form 6k- we have already reached a
contradiction, and our theorem is proved. If the prime is of
the form 6k1 + the complementary factor is of the form 6k2 -.
Every prime factor of 6k2 —I is greater than p. Hence we
may treat 6k2 - I as we did 6n - I, and with a like result. Hence
we must ultimately reach a prime factor of the form 6k3-I;
for, otherwise, we should have 6n-I expressed as a product
of prime factors all of the form 6t+i-a result which is clearly
impossible. Hence we must in any case reach a contradiction
of the hypothesis. Thus the theorem is proved.
The preceding results are special cases of the following more
general theorem: