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 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.


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:

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:

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

So that

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

By the definition, for scalars c and d:

Multiplying through by 8/2:

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

See Also



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

  gcbo gcf