Greatest Common Divisor (GCD)

The greatest common divisor (GCD) of two positive integers is an integer that is a divisor for both integers. Example: The GCD of 6 and 9 is 3 because 3 x 2 = 6, and 3 x 3 = 9.

The GCD is found easily using Euclid's method. Euclid's method recursively subtracts the smaller integer from the larger integer until a base case with equal integers is reached. The greatest common divisor is the...