## 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**.

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