# gcd

Greatest common divisor

## Syntax

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

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

### Greatest Common Divisors of Double Values

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

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

### Greatest Common Divisors of Unsigned Integers

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

### Solution to Diophantine Equation

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 = 1 ```

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

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

## Input Arguments

collapse all

### `A,B` — Input valuesscalars, vectors, or arrays of real integer values

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

### `G` — Greatest common divisorreal, nonnegative integer values

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.

### `U,V` — Bézout coefficientsreal integer values

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.

collapse all

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