|MATLAB Function Reference|
Greatest common divisor
G = gcd(A,B)
returns an array containing the greatest common divisors of the corresponding elements of integer arrays
B. By convention,
gcd(0,0) returns a value of
0; all other inputs return positive integers for
[G,C,D] = gcd(A,B)
returns both the greatest common divisor array
G, and the arrays
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.
The first example involves elementary Hermite transformations.
For any two integers
b there is a
E with integer entries and determinant =
1 (a unimodular matrix) such that:
g is the greatest common divisor of
b as returned by the command
[g,c,d] = gcd(a,b).
In the case where
a = 2 and
b = 4:
In the next example, we solve for
y in the Diophantine equation
30x + 56y = 8.
By the definition, for scalars
Multiplying through by 8/2:
Comparing this to the original equation, a solution can be read by inspection:
 Knuth, Donald, The Art of Computer Programming, Vol. 2, Addison-Wesley: Reading MA, 1973. Section 4.5.2, Algorithm X.