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

10

THEORY OF NUMBERS

~ 3. PRIME NUMBERS. THE SIEVE OF ERATOSTHENES
DEFINITION. If an integer p is different from i and has
no divisor except itself and I it is said to be a prime number
or to be a prime.
DEFINITION. An integer which has at least one divisor
other than itself and I is said to be a composite number or to
be composite.
All integers are thus divided into three classes:
I) The unit;
2) Prime numbers;
3) Composite numbers.
We have seen that the first class contains only a single
number. The third class evidently contains an infinitude of
numbers; for, it contains all the numbers 2?, 23, 2,..
In the next section we shall show that the second class also
contains an infinitude of numbers. We shall now show that
every number of the third class contains one of the second
class as a factor, by proving the following theorem:
I. Every integer greater than I has a prime factor.
Let m be any integer which is greater than I. We have
to show that it has a prime factor. If m is prime there is the
prime factor m itself. If m is not prime we have
m = mlm2,
where ml and m2 are positive integers both of which are less than
m. If either mi or m2 is prime we have thus obtained a prime
factor of m. If neither of these numbers is prime, then write
m1=m m'l2, ml> I, /2> I.
Both m'\ and m'2 are factors of m and each of them is less than
ml. Either we have now found in m'l or 'm'2 a prime factor
of m or the process can be continued by separating one of these
numbers into factors. Since for any given m there is evidently
only a finite number of such steps possible, it is clear that we