chapter  3
22 Pages

Greatest Common Divisor

For integers a and b, the greatest common divisor of a and b is the largest integer d such that d is a factor of both a and b. The greatest common divisor is denoted gcd(a,b). We say a and b are relatively prime provided gcd(a,b) = 1. In this chapter we develop many C++ concepts by studying a particular problem involving the gcd of integers. Here is the classic problem: Let n be a positive integer. Two integers, a and b,

are selected independently and uniformly from the set {1,2, . . . ,n}. Let pn be the probability that a and b are relatively prime. Does limn→∞ pn exist and, if so, what is its value? The computer cannot solve this problem for us, but it can help us to formulate

a conjecture. We try a number of approaches including exhaustive enumeration, generating pairs of numbers at random and recording the results, and the use of Euler’s totient. The first order of business, however, is to develop a procedure to compute the

greatest common divisor of two integers.