Page 279 - Discrete Mathematics and Its Applications

258 4 / Number Theory and Cryptography

THEOREM 1 THE FUNDAMENTAL THEOREM OF ARITHMETIC Every integer greater than 1
can be written uniquely as a prime or as the product of two or more primes where the prime
factors are written in order of nondecreasing size.

Example 2 gives some prime factorizations of integers.

EXAMPLE 2 The prime factorizations of 100, 641, 999, and 1024 are given by

2 2
100 = 2 · 2 · 5 · 5 = 2 5 ,
641 = 641,
3
999 = 3 · 3 · 3 · 37 = 3 · 37,
10
1024 = 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 = 2 .
▲

Trial Division

It is often important to show that a given integer is prime. For instance, in cryptology, large
primes are used in some methods for making messages secret. One procedure for showing that
an integer is prime is based on the following observation.

√
THEOREM 2 If n is a composite integer, then n has a prime divisor less than or equal to n.

Proof: If n is composite, by the definition of a composite integer, we know that it has a factor
a with 1 <a <n. Hence, by the definition of a factor of a positive integer, we have n = ab,
√ √ √
where b is a positive integer greater than 1.We will show that a ≤ n or b ≤ n.If a> n and
√ √ √ √ √
b> n, then ab > n · n = n, which is a contradiction. Consequently, a ≤ n or b ≤ n.
√
Because both a and b are divisors of n, we see that n has a positive divisor not exceeding n.
This divisor is either prime or, by the fundamental theorem of arithmetic, has a prime divisor
√
less than itself. In either case, n has a prime divisor less than or equal to n.
From Theorem 2, it follows that an integer is prime if it is not divisible by any prime less
than or equal to its square root. This leads to the brute-force algorithm known as trial division.
√
To use trial division we divide n by all primes not exceeding n and conclude that n is prime
if it is not divisible by any of these primes. In Example 3 we use trial division to show that 101
is prime.

EXAMPLE 3 Show that 101 is prime.
√
Solution: The only primes not exceeding 101 are 2, 3, 5, and 7. Because 101 is not divisible
by 2, 3, 5, or 7 (the quotient of 101 and each of these integers is not an integer), it follows that
101 is prime. ▲

Because every integer has a prime factorization, it would be useful to have a procedure for
finding this prime factorization. Consider the problem of finding the prime factorization of n.
Begin by dividing n by successive primes, starting with the smallest prime, 2. If n has a prime
√
factor, then by Theorem 3 a prime factor p not exceeding n will be found. So, if no prime