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

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

© 1994-2005 The MathWorks, Inc.