The greatest common divisor (gcd) of two non-zero integers a and b is the largest integer d such that both a and b are divisible by d. To find the greatest common divisor, enter a and b in the boxes below and press Find gcd.
The program finds the gcd using the Euclidean algorithm, first described by the Greek mathematician Euclid around 300 BC. The algorithm also returns integers x and y, so that d = x · a + y · b, where d is the gcd of a and b. This linear combination is also shown above.
The program uses the Perl BigInt module, so you can enter very large values for a and b—for example, on the order of a googol (1 followed by 100 zeros).
The greatest common divisor is used in modular arithmetic (among many other things) .
Paul Trow's math software.
Copyright 2009 by Paul Trow