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.

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

    Send comments.

   Paul Trow's math software.

Copyright 2009 by Paul Trow