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 =  
21 = 3 · 273 + -2 · 399

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.