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
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
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.