# gcd

GCD of numbers and polynomials

## Description

`[`

finds
the greatest common divisor of `G`

,`C,D`

]
= gcd(`A`

,`B`

,`X`

)`A`

and `B`

, and also
returns the Bézout coefficients, `C`

and `D`

, such
that `G = A*C + B*D`

. For multivariate expressions, specify the polynomial
variable `X`

such that it does not appear in the denominator of
`C`

and `D`

. If you do not specify
`X`

, then `gcd`

uses the default variable determined
by `symvar`

.

## Examples

### Greatest Common Divisor of Four Integers

To find the greatest common divisor of three or more values, specify those values as a symbolic vector or matrix.

Find the greatest common divisor of these four integers, specified as elements of a symbolic vector.

A = sym([4420, -128, 8984, -488]) gcd(A)

A = [ 4420, -128, 8984, -488] ans = 4

Alternatively, specify these values as elements of a symbolic matrix.

A = sym([4420, -128; 8984, -488]) gcd(A)

A = [ 4420, -128] [ 8984, -488] ans = 4

### Greatest Common Divisor of Polynomials

Find the greatest common divisor of univariate and multivariate polynomials.

Find the greatest common divisor of these univariate polynomials.

syms x gcd(x^3 - 3*x^2 + 3*x - 1, x^2 - 5*x + 4)

ans = x - 1

Find the greatest common divisor of these multivariate polynomials. Because there are more than two polynomials, specify them as elements of a symbolic vector.

syms x y gcd([x^2*y + x^3, (x + y)^2, x^2 + x*y^2 + x*y + x + y^3 + y])

ans = x + y

### Greatest Common Divisor of Rational Numbers

The greatest common divisor of rational numbers
`a`

is a number
_{1},a_{2},...`g`

, such that
`g/a`

are
integers, and _{1},g/a_{2},...`gcd(g/a`

._{1},g/a_{2},...) =
1

Find the greatest common divisor of these rational numbers, specified as elements of a symbolic vector.

gcd(sym([1/4, 1/3, 1/2, 2/3, 3/4]))

ans = 1/12

### Greatest Common Divisor of Complex Numbers

`gcd`

computes the greatest common divisor of
complex numbers over the Gaussian integers (complex numbers with integer real and
imaginary parts). It returns a complex number with a positive real part and a nonnegative
imaginary part.

Find the greatest common divisor of these complex numbers.

gcd(sym([10 - 5*i, 20 - 10*i, 30 - 15*i]))

ans = 5 + 10i

### Greatest Common Divisor of Elements of Matrices

For vectors and matrices, `gcd`

finds the greatest
common divisors element-wise. Nonscalar arguments must be the same size.

Find the greatest common divisors for the elements of these two matrices.

A = sym([309, 186; 486, 224]); B = sym([558, 444; 1024, 1984]); gcd(A,B)

ans = [ 3, 6] [ 2, 32]

Find the greatest common divisors for the elements of matrix `A`

and
the value `200`

. Here, `gcd`

expands
`200`

into the `2`

-by-`2`

matrix with
all elements equal to `200`

.

gcd(A,200)

ans = [ 1, 2] [ 2, 8]

### GCD Is Positive Linear Combination of Inputs

A theorem in number theory states that the GCD of two numbers is the
smallest positive linear combination of those numbers. Show that the GCD is a positive
linear combination for `64`

and `44`

.

A = sym([64 44]); [G,M] = gcd(A)

G = 4 M = [ -2, 3]

isequal(G,sum(M.*A))

ans = logical 1

### Bézout Coefficients

Find the greatest common divisor and the Bézout coefficients of
these polynomials. For multivariate expressions, use the third input argument to specify
the polynomial variable. When computing Bézout coefficients, `gcd`

ensures that the polynomial variable does not appear in their denominators.

Find the greatest common divisor and the Bézout coefficients of these polynomials
with respect to variable `x`

.

[G,C,D] = gcd(x^2*y + x^3, (x + y)^2, x)

G = x + y C = 1/y^2 D = 1/y - x/y^2

Find the greatest common divisor and the Bézout coefficients of
the same polynomials with respect to variable `y`

.

[G,C,D] = gcd(x^2*y + x^3, (x + y)^2, y)

G = x + y C = 1/x^2 D = 0

If you do not specify the polynomial variable, then the toolbox uses
`symvar`

to determine the variable.

[G,C,D] = gcd(x^2*y + x^3, (x + y)^2)

G = x + y C = 1/y^2 D = 1/y - x/y^2

### 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,C,D] = gcd(sym(30),56)

G = 2 C = -13 D = 7

`C = -13`

and `D = 7`

satisfy the Bézout's
identity, `(30*(-13)) + (56*7) = 2`

.

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.

isAlways((30*C*4) + (56*D*4) == G*4)

ans = logical 1

Calculate the values of `x`

and `y`

that solve the
Diophantine equation.

x = C*4 y = D*4

x = -52 y = 28

## Input Arguments

## Output Arguments

## Tips

Calling

`gcd`

for numbers that are not symbolic objects invokes the MATLAB^{®}`gcd`

function.The MATLAB

`gcd`

function does not accept rational or complex arguments. To find the greatest common divisor of rational or complex numbers, convert these numbers to symbolic objects by using`sym`

, and then use`gcd`

.Nonscalar arguments must be the same size. If one input argument is nonscalar, then

`gcd`

expands the scalar into a vector or matrix of the same size as the nonscalar argument, with all elements equal to the corresponding scalar.

## Version History

**Introduced in R2014b**