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

If d is the gcd of a and b, there are integers x and y such that d = x · a + y · b, as shown above. The values of d, x, and y are calculated using the extended Euclidean algorithm.

The gcd is used in modular arithmetic (among many other things) .

    Send comments.

   Paul Trow's math software.

Copyright 2009 by Paul Trow