MATLAB Function Reference

gcd

Greatest common divisor

Syntax

G = gcd(A,B)
[G,C,D] = gcd(A,B)

Description

G = gcd(A,B) returns an array containing the greatest common divisors of the corresponding elements of integer arrays A and B. By convention, gcd(0,0) returns a value of 0; all other inputs return positive integers for G.

[G,C,D] = gcd(A,B) returns both the greatest common divisor array G, and the arrays C and D, which satisfy the equation: A(i).*C(i) + B(i).*D(i) = G(i). These are useful for solving Diophantine equations and computing elementary Hermite transformations.

Examples

The first example involves elementary Hermite transformations.

For any two integers a and b there is a 2-by-2 matrix E with integer entries and determinant = 1 (a unimodular matrix) such that:

E * [a;b] = [g,0],

where g is the greatest common divisor of a and b as returned by the command
[g,c,d] = gcd(a,b).

The matrix E equals:

c       d 
-b/g    a/g 

In the case where a = 2 and b = 4:

[g,c,d] = gcd(2,4)
g =
     2
c =
     1
d =
     0

So that:

E =
    1     0
    -2     1

In the next example, we solve for x and y in the Diophantine equation
30x + 56y = 8.

[g,c,d] = gcd(30,56)
g =
     2
c =
    -13
d =
     7

By the definition, for scalars c and d:

30(-13) + 56(7) = 2, 

Multiplying through by 8/2:

30(-13*4) + 56(7*4) = 8

Comparing this to the original equation, a solution can be read by inspection:

x = (-13*4) = -52; y = (7*4) = 28

See Also

lcm

References

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

gcbo

gcf