Documentation

# gcd

Greatest common divisor

## Syntax

``G = gcd(A,B)``
``````[G,U,V] = gcd(A,B)``````

## Description

example

````G = gcd(A,B)` returns the greatest common divisors of the elements of `A` and `B`. The elements in `G` are always nonnegative, and `gcd(0,0)` returns `0`. This syntax supports inputs of any numeric type.```

example

``````[G,U,V] = gcd(A,B)``` also returns the Bézout coefficients, `U` and `V`, which satisfy: `A.*U + B.*V = G`. The Bézout coefficients are useful for solving Diophantine equations. This syntax supports double, single, and signed integer inputs.```

## Examples

collapse all

```A = [-5 17; 10 0]; B = [-15 3; 100 0]; G = gcd(A,B)```
```G = 2×2 5 1 10 0 ```

`gcd` returns positive values, even when the inputs are negative.

```A = uint16([255 511 15]); B = uint16([15 127 1023]); G = gcd(A,B)```
```G = 1x3 uint16 row vector 15 1 3 ```

Solve the Diophantine equation, $30x+56y=8$ for $x$ and $y$.

Find the greatest common divisor and a pair of Bézout coefficients for `30` and `56`.

`[g,u,v] = gcd(30,56)`
```g = 2 ```
```u = -13 ```
```v = 7 ```

`u` and `v` satisfy the Bézout's identity, `(30*u) + (56*v) = g`.

Rewrite Bézout's identity so that it looks more like the original equation. Do this by multiplying by `4`. Use `==` to verify that both sides of the equation are equal.

`(30*u*4) + (56*v*4) == g*4`
```ans = logical 1 ```

Calculate the values of $x$ and $y$ that solve the problem.

`x = u*4`
```x = -52 ```
`y = v*4`
```y = 28 ```

## Input Arguments

collapse all

Input values, specified as scalars, vectors, or arrays of real integer values. `A` and `B` can be any numeric type, and they can be of different types within certain limitations:

• If `A` or `B` is of type `single`, then the other can be of type `single` or `double`.

• If `A` or `B` belongs to an integer class, then the other must belong to the same class or it must be a `double` scalar value.

`A` and `B` must be the same size or one must be a scalar.

Example: `[20 -3 13],[10 6 7]`

Example: `int16([100 -30 200]),int16([20 15 9])`

Example: `int16([100 -30 200]),20`

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `int64` | `uint8` | `uint16` | `uint32` | `uint64`

## Output Arguments

collapse all

Greatest common divisor, returned as an array of real nonnegative integer values. `G` is the same size as `A` and `B`, and the values in `G` are always real and nonnegative. `G` is returned as the same type as `A` and `B`. If `A` and `B` are of different types, then `G` is returned as the nondouble type.

Bézout coefficients, returned as arrays of real integer values that satisfy the equation, `A.*U + B.*V = G`. The data type of `U` and `V` is the same type as that of `A` and `B`. If `A` and `B` are of different types, then `U` and `V` are returned as the nondouble type.

## Algorithms

`g = gcd(A,B)` is calculated using the Euclidian algorithm.[1]

`[g,u,v] = gcd(A,B)` is calculated using the extended Euclidian algorithm.[1]

## References

[1] Knuth, D. “Algorithms A and X.” The Art of Computer Programming, Vol. 2, Section 4.5.2. Reading, MA: Addison-Wesley, 1973.

Download ebook