The Integers - Introduction to Cryptography with Java Applets - page 66

Prime numbers play a huge role in number theory, and in modern cryptography as well.
Thus, the definition of a prime number follows.

Definition
A prime number, or a prime, is an integer greater than 1 divisible by no positive inte-
gers other than itself and 1. A positive integer greater than 1 that is not prime is said to
be composite.

E XAMPLES . All of the following integers are primes: 2, 7, 23, 29, and 163. None of these num-
bers has positive factors except themselves and 1. On the other hand, the following num-
bers are composite: 4 = 2 2, 100 = 2 2 5 5, and 39 = 3 13. You should be
careful to note, however, that many integers are neither prime nor composite, as all primes
and composite numbers are positive integers greater than 1. For example, the following
integers are neither prime nor composite: 1, 0, 21, and 5.

It is important to establish that every positive integer greater than 1 has a prime divisor,
for it helps us establish that there are infinitely many primes. It also helps us determine the
whereabouts of a prime factor for composite numbers.

PROPOSITION 4

Every positive integer greater than 1 has a prime divisor.

Proof. First, assume there is a positive integer greater than 1 having no prime divisors.

Thus, the set of all such integers is not empty, and so has a least element, say m . Since m

has no prime divisors and m | m , m is not prime. So m is composite, and we write m = bc where

1 < b < m and 1 < c < m. Now, since b < m , b must have a prime divisor, say p , since m is

the least nonnegative integer having no prime divisors. But p then also divides m by Propo-

sition 1, and so m has a prime divisor, a contradiction.

PROPOSITION 5 There are infinitely many primes.

Proof. Take the integer z = n !+1, where n ≥ 1. Proposition 4 says z has a prime divisor,

say p . Suppose p ≤ n . Then we would have p | n !. This is so since

n n n n

! = ( 1)( 2) . . . 3 · 2 · 1,

and if , it must divide one of the numbers in the sequence. But then, by Proposition 2,

we would have

p ≤ n

p |( z n !) = 1, an impossibility. So the prime p must be greater than n , and

since n is completely arbitrary, we have found a prime larger than n for any integer n . This

establishes that there must be infinitely many primes.

It is important for us to establish that there are infinitely many primes, as we must be able
to freely select primes for use in cryptographic applications. The primes we choose are usu-
ally kept secret, so there must be enough primes scattered about to make finding the primes
you choose very difficult for an attacker.