Page 278 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 257

55. Devise an algorithm that, given the binary expansions of 57. Estimate the complexity of Algorithm 1 for finding the
the integers a and b, determines whether a> b, a = b, base b expansion of an integer n in terms of the number
or a< b. of divisions used.
2
∗ 58. Show that Algorithm 5 uses O((log m) log n) bit opera-
n
56. How many bit operations does the comparison algo- tions to find b mod m.
rithm from Exercise 55 use when the larger of a and b 59. Show that Algorithm 4 uses O(q log a) bit operations,
has n bits in its binary expansion? assuming that a> d.

4.3 Primes and Greatest Common Divisors

Introduction

In Section 4.1 we studied the concept of divisibility of integers. One important concept based
on divisibility is that of a prime number. A prime is an integer greater than 1 that is divisible by
no positive integers other than 1 and itself. The study of prime numbers goes back to ancient
times. Thousands of years ago it was known that there are infinitely many primes; the proof of
this fact, found in the works of Euclid, is famous for its elegance and beauty.
We will discuss the distribution of primes among the integers. We will describe some
of the results about primes found by mathematicians in the last 400 years. In particular, we
will introduce an important theorem, the fundamental theorem of arithmetic. This theorem,
which asserts that every positive integer can be written uniquely as the product of primes in
nondecreasing order, has many interesting consequences. We will also discuss some of the many
old conjectures about primes that remain unsettled today.
Primes have become essential in modern cryptographic systems, and we will develop some
of their properties important in cryptography. For example, finding large primes is essential in
modern cryptography. The length of time required to factor large integers into their prime factors
is the basis for the strength of some important modern cryptographic systems.
In this section we will also study the greatest common divisor of two integers, as well as the
least common multiple of two integers. We will develop an important algorithm for computing
greatest common divisors, called the Euclidean algorithm.

Primes

Every integer greater than 1 is divisible by at least two integers, because a positive integer is
divisible by 1 and by itself. Positive integers that have exactly two different positive integer
factors are called primes.

DEFINITION 1 An integer p greater than 1 is called prime if the only positive factors of p are 1 and p.
A positive integer that is greater than 1 and is not prime is called composite.

Remark: The integer n is composite if and only if there exists an integer a such that a | n and
1 <a <n.

EXAMPLE 1 The integer 7 is prime because its only positive factors are 1 and 7, whereas the integer 9 is
composite because it is divisible by 3. ▲

The primes are the building blocks of positive integers, as the fundamental theorem of
arithmetic shows. The proof will be given in Section 5.2.