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.
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) .
Paul Trow's math software.
Copyright 2009 by Paul Trow