Change language to:
English - Français - Português - Русский

See the recommended documentation of this function

# gcd

Greatest (positive) Common Divisor

### Syntax

```gpcd = gcd(P)
[gpcd, U] = gcd(P)```

### Arguments

P

array of decimal integers, encoded integers, or of polynomials.

gpcd

single element of `P` type: the greatest common divisor of all `P` components.

U

Square matrix of the `P` type, with integer components or of minimal degrees. Its last column `B = U(:,\$)` holds Bezout coefficients, such that `B(1)*P(1) + B(2)*P(2) + .... + B(\$)*P(\$) == gpcd`.

### Description

`[gpcd, U] = gcd(P)` computes the greatest common divisor `gpcd` of components of `P`, and an unimodular matrix `U`.

If `P` components are decimal or encoded integers, they are priorly converted into `int64` signed integers.

If `P` has an unsigned inttype `uint8`, `uint16`, `uint32` or `uint64`, `U` gets the corresponding signed inttype.

When `P` are integers, the returned GCD is always positive.

When a second output is expected, an unimodular matrix `U` of the `P` type is returned, such that

• `size(U) == [length(P) length(P)]`
• `matrix(P,1,-1)*U = [0...0 gpcd]` with `length(P)-1` leading zeros
• `det(U)` is `1` or `-1`.

Its last column provides Bezout coefficients.

 `gcd([0 0])` returns `0`.
 For big `P` values (smaller but of the order of 2^63, depending also on the number of input values), results may be corrupted by integer overflow and wrapping (int8(127)+1 == -128).

### Examples

```// With polynomials
s = %s;
p = [s  s*(s+1)^2  2*s^2+s^3];
[GCD, U] = gcd(p)
p*u

// With encoded integers
V = uint16([2^2*3^5 2^3*3^2 2^2*3^4*5])
[GCD, U] = gcd(V)
typeof(GCD)
typeof(U)
V*U

// With decimal integers
V = [2^2*3^5 2^3*3^2 2^2*3^4*5];
[GCD, U] = gcd(V)
type(GCD)
type(U)
V*U

gcd([0 60])
gcd([0 0])```

 Version Description 6.0.1 `int64` and `uint64` input integers are now supported. The input `P` may be any array instead of a row vector. For input integers possibly negative, the returned GCD is now always positive.