## Greatest Common Divisor

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) .

Send comments.

Paul Trow's math software.

Copyright 2009 by Paul Trow