Main Content

gcd

GCD of numbers and polynomials

collapse all in page

Syntax

G = gcd(A)
G = gcd(A,B)
[G,M] = gcd(A)
[G,C,D] = gcd(A,B,X)

Description

G = gcd(A) finds the greatest common divisor of all elements of A.

example

G = gcd(A,B) finds the greatest common divisor of A and B.

example

[G,M] = gcd(A) returns the GCD G of all elements of A, and returns in M the linear combination of A that equals G.

example

[G,C,D] = gcd(A,B,X) finds the greatest common divisor of 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.

example

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 a1,a2,... is a number g, such that g/a1,g/a2,... are integers, and gcd(g/a1,g/a2,...) = 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

collapse all

Input value, specified as a number, symbolic number, variable, expression, function, or a vector or matrix of numbers, symbolic numbers, variables, expressions, or functions.

Input value, specified as a number, symbolic number, variable, expression, function, or a vector or matrix of numbers, symbolic numbers, variables, expressions, or functions.

Polynomial variable, specified as a symbolic variable.

Output Arguments

collapse all

Greatest common divisor, returned as a symbolic number, variable, expression, function, or a vector or matrix of symbolic numbers, variables, expressions, or functions.

Linear combination of input that equals GCD of input, returned as a symbolic vector, matrix, or array.

Bézout coefficients, returned as symbolic numbers, variables, expressions, functions, or vectors or matrices of symbolic numbers, variables, expressions, or functions.

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

See Also