Main Content

GCD of numbers and polynomials

`[`

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`

.

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

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

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

`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

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]

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

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

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

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.