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.

a =  
b =  
gcd =  
8034992 = 55079800112751 · 155723252246745780240 + -1292562032069 · 6635817387370379792192

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