The following algorithm is known as Euclids Algorithm because it appears in Euclids Elements (Book 7, ca. 300 B.C.). It may be the oldest nontrivial algorithm. The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation gcd(a, b) = gcd(b, r) to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example, gcd(36, 20) = gcd(20, 16) = gcd(16, 4) = gcd(4, 0) = 4