gcd

Greatest common divisor of symbolic numbers and polynomials

Syntax

G = gcd(A)

G = gcd(A,B)

[G,M] = gcd(A)

[G,U,V] = gcd(A,B,X)

Description

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

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

[G,M] = gcd(A) also returns the coefficients M for the linear combination of elements in A that results in G.

[G,U,V] = gcd(A,B,X) also returns the Bézout coefficients, U and V, such that G = A*U + B*V. For multivariate polynomials, specify the polynomial variable X such that it does not appear in the denominator of U and V. If you do not specify X, then gcd uses the default variable determined by symvar.

Examples

Greatest Common Divisor of Symbolic Integers

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

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

G = $$4$$

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

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

G = $$4$$

Greatest Common Divisor of Rational Numbers

The greatest common divisor of rational numbers $a_1,a_2,\dots ,a_n$ is a number $g$, such that $a_1/g,a_2/g,\dots ,a_n/g$ are integers, and $\gcd \left(a_1/g,a_2/g,\dots ,a_n/g\right)=1$.

Find the greatest common divisor of five rational numbers.

A = sym([1/4 1/3 1/2 2/3 3/4])

A = 
$$\left(\begin{array}{ccccc}\frac{1}{4}& \frac{1}{3}& \frac{1}{2}& \frac{2}{3}& \frac{3}{4}\end{array}\right)$$

G = gcd(A)

G = 
$$\frac{1}{12}$$

Greatest Common Divisor of Complex Numbers

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

Find the greatest common divisor of three complex numbers.

A = sym([3 + 1i, 4 - 2i, -5 - 5i]);
G = gcd(A)

G = $$3+\mathrm{i}$$

Greatest Common Divisor of Elements of Matrices

If you specify two input arguments and at least one of them is nonscalar, gcd finds the greatest common divisors element-wise.

Find the greatest common divisors for the elements of two matrices. When you specify two nonscalar input arguments, they must be the same size.

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

G = 
$$\left(\begin{array}{cc}3& 6\\ 2& 32\end{array}\right)$$

Find the greatest common divisors for the elements of matrix A and the value 200. Here, gcd expands 200 into a 2-by-2 matrix with all elements equal to 200.

G = gcd(A,200)

G = 
$$\left(\begin{array}{cc}1& 2\\ 2& 8\end{array}\right)$$

Greatest Common Divisor of Polynomials

Find the greatest common divisor of two univariate polynomials.

syms x
A = x^3 - 3*x^2 + 3*x - 1;
B = x^2 - 5*x + 4;
G = gcd(A,B)

G = $$x-1$$

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

syms x y
A = [x^2*y + x^3, (x + y)^2, x^2 + x*y^2 + x*y + x + y^3 + y];
G = gcd(A)

G = $$x+y$$

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 of 64 and 44 is a positive linear combination of those numbers.

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

G = $$4$$

M = $$\left(\begin{array}{cc}-2& 3\end{array}\right)$$

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

tf = logical
   1

Bézout Coefficients

Find the greatest common divisor and the Bézout coefficients of two polynomials with respect to variable x. When computing Bézout coefficients, gcd ensures that the polynomial variable does not appear in the denominators of these coefficients.

syms x y
[G,U,V] = gcd(x^2*y + x^3, (x + y)^2, x)

G = $$x+y$$

U = 
$$\frac{1}{y^2}$$

V = 
$$\frac{1}{y}-\frac{x}{y^2}$$

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

[G,U,V] = gcd(x^2*y + x^3, (x + y)^2, y)

G = $$x+y$$

U = 
$$\frac{1}{x^2}$$

V = $$0$$

If you do not specify the polynomial variable, then the toolbox uses symvar to determine the variable.

[G,U,V] = gcd(x^2*y + x^3, (x + y)^2)

G = $$x+y$$

U = 
$$\frac{1}{y^2}$$

V = 
$$\frac{1}{y}-\frac{x}{y^2}$$

Solve Diophantine Equation

Solve the Diophantine equation $\left(1-z\right)x+z\left(1-2z\right)y=3$ for $x$ and $y$.

Start by defining the coefficients for $x$ and $y$, and the right side of this Diophantine equation.

syms z
A = 1 - z;
B = z*(1 - 2*z);
R = 3;

Use the syntax [G,U,V] = gcd(A,B) to find the greatest common divisor G of the polynomials A and B and the Bézout coefficients U and V, such that G = A*U + B*V.

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

G = $$1$$

U = $$2\hspace{0.17em}z+1$$

V = $$-1$$

If the GCD divides the right side of the equation, or in other words, R/G is an integer, then the Diophantine equation has a solution. Use the Bézout coefficients U and V to compute one particular solution and the general solution for the Diophantine equation.

if mod(R,G) == 0
  S = R/G;
  disp("Particular solution:")
  x1 = U*S
  y1 = V*S
  disp("General solution:")
  syms k integer
  x = x1 + B/G*k
  y = y1 - A/G*k
  params = assumptions(k)
else
  disp("This Diophantine equation does not have a solution.")
end

Particular solution:

x1 = $$6\hspace{0.17em}z+3$$

y1 = $$-3$$

General solution:

x = $$6\hspace{0.17em}z-k\hspace{0.17em}z\hspace{0.17em}\left(2\hspace{0.17em}z-1\right)+3$$

y = $$k\hspace{0.17em}\left(z-1\right)-3$$

params = $$k\in \mathbb{Z}$$

Finally, confirm that the general solution satisfies the Diophantine equation.

eqCheck = simplify(A*x + B*y) == R

eqCheck = $$3=3$$

Input Arguments

A — Input value

symbolic number | symbolic variable | symbolic expression | symbolic function | symbolic vector | symbolic matrix

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

B — Input value

symbolic number | symbolic variable | symbolic expression | symbolic function | symbolic vector | symbolic matrix

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

If A and B are nonscalar, they must have the same size. If either A or B is scalar, 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.

X — Polynomial variable

symbolic variable

Polynomial variable, specified as a symbolic variable. By default, gcd uses the variable determined by symvar.

Output Arguments

G — Greatest common divisor

symbolic number | symbolic variable | symbolic expression | symbolic function | symbolic vector | symbolic matrix

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

M — Coefficients for linear combination of elements in input A

symbolic vector | symbolic matrix | symbolic array

Coefficients for the linear combination of elements in input A that equals GCD of input, returned as a symbolic vector, matrix, or array.

U,V — Bézout coefficients

symbolic number | symbolic variable | symbolic expression | symbolic function | symbolic vector | symbolic matrix

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

Tips

• Calling gcd with 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.

Version History

Introduced in R2014b