MATLAB Function Reference |

**Syntax**

**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:

where `g`

is the greatest common divisor of `a`

and `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 `x`

and `y`

in the Diophantine equation `30x + 56y = 8`

.

By the definition, for scalars `c`

and `d`

:

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

**See Also**

**References**

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

gcbo | gcf |