324 ARITHMETIC 4.5.2 the (Yahoo web space) greatest common divisor is
324 ARITHMETIC 4.5.2 the greatest common divisor is taken to be zero; otherwise if only one uj is nonzero, it is the greatest common divisor; otherwise replace uk by uk mod uj for all k # j, where Uj is the minimum of the nonzero u s. The algorithm sketched in the preceding paragraph is a natural generaliza- tion of Euclid s method, and it can be justified in a similar manner. But there is a simpler method available, based on the easily verified identity gcd(w,u2,… , un) = gcd(ul, .sd(uz, . . . ,un,). (14 To calculate gcd(ur, uz, . . . , u,), we may therefore proceed as follows: Cl. Set d t u,, j +-n -1. C2. If d # 1 and j > 0, set d c gcd(uj, d) and j c j -1 and repeat this step. Otherwise d = gcd(ul, . . . , u,). This method reduces the calculation of gcd(ui, . . . , u,) to repeated calculations of the greatest common divisor of two numbers at a time. It makes use of the fact that gcd(ui, . . . , uj, 1) = 1; and this will be helpful, since we will already have gcd(u,-1, u,) = 1 over 60 percent of the time if u,-1 and u, are chosen at random. In most cases, the value of d will decrease rapidly during the first few stages of the calculation, and this will make the remainder of the computation quite fast. Here Euclid s algorithm has an advantage over Algorithm B, in that its running time is primarily governed by the value of min(u, v), while the running time for Algorithm B is primarily governed by max(u, v); it would be reasonable to perform one iteration of Euclid s algorithm, replacing u by u modv if u is much larger than V, and then to continue with Algorithm B. The assertion that gcd(u,-l, u,) will be equal to unity more than 60 percent of the time for random inputs is a consequence of the following well-known result of number theory: Theorem D (G. Lejeune Dirichlet, Abhandlungen Kbniglich PreuB. Akad. Wiss. (1849), 69-83). If u and v are integers chosen at random, the probability that gcd(u, V) = 1 is 6/.rr2 z .60793. A precise formulation of this theorem, which carefully defines what is meant by being chosen at random, appears in exercise 10 with a rigorous proof. Let us content ourselves here with a heuristic argument that shows why the theorem is plausible. If we assume, without proof, the existence of a well-defined probability p that gcd(u, w) equals unity, then we can determine the probability that gcd(u, TJ) = d for any positive integer d, because gcd(u, w) = d if and only if u is a multiple of d and v is a multiple of d and gcd(u/d, v/d) = 1. Thus the probability that gcd(u, ZJ) = d is equal to l/d times l/d times p, namely p/d2. Now let us sum these probabilities over all possible values of d; we should get 1 = c p/d2 = p(1 + ; + ; + ; + . . . ). d>l Since the sum 1 + 4 + 4 + . . . = HE) is equal to .rr2/6 (cf. Section 1.2.7), we need p = 6/n2 in order to make this equation come out right. 1