gcd

Purpose

Greatest common divisor.

Synopsis

g = gcd(a,b)
[g,c,d] = gcd(a,b)

Description

g = gcd(a,b) is the greatest common divisor of the integers a and b. By convention, gcd(0,0) returns a value of 0; all other inputs return positive integers.

[g,c,d] = gcd(a,b) also returns the scalars c and d such that g = a*c+b*d.

Examples

[g,c,d] = gcd(80,120)
          
g =
    40
          
c =
    -1
          
d =
     1

See Also

lcm

References

[1] Donald Knuth. The Art of Computer Programming, Vol. 2, Addison-Wesley:Reading MA, 1973. Section 4.5.2, Algorithm X.

(c) Copyright 1994 by The MathWorks, Inc.