Greatest common divisor
G = gcd(A,B)
[G,U,V] = gcd(A,B)
A = [-5 17; 10 0]; B = [-15 3; 100 0]; G = gcd(A,B)
G = 2×2 5 1 10 0
gcd returns positive values, even when the inputs are negative.
A = uint16([255 511 15]); B = uint16([15 127 1023]); G = gcd(A,B)
G = 1x3 uint16 row vector 15 1 3
Solve the Diophantine equation, for and .
Find the greatest common divisor and a pair of Bézout coefficients for
[g,u,v] = gcd(30,56)
g = 2
u = -13
v = 7
v satisfy the Bézout's identity,
(30*u) + (56*v) = g.
Rewrite Bézout's identity so that it looks more like the original equation. Do this by multiplying by
== to verify that both sides of the equation are equal.
(30*u*4) + (56*v*4) == g*4
ans = logical 1
Calculate the values of and that solve the problem.
x = u*4
x = -52
y = v*4
y = 28
A,B— Input values
Input values, specified as scalars, vectors, or arrays of real
be any numeric type, and they can be of different types within certain
single, then the other can be of type
to an integer class, then the other must belong to the same class
or it must be a
double scalar value.
B must be the same
size or one must be a scalar.
[20 -3 13],[10 6 7]
int16([100 -30 200]),int16([20 15 9])
int16([100 -30 200]),20
G— Greatest common divisor
Greatest common divisor, returned as an array of real nonnegative
G is the same size as
and the values in
G are always real and nonnegative.
returned as the same type as
B are of different
G is returned as the nondouble type.
U,V— Bézout coefficients
Bézout coefficients, returned as arrays of real integer
values that satisfy the equation,
A.*U + B.*V = G.
The data type of
the same type as that of
B are of different
V are returned
as the nondouble type.
g = gcd(A,B) is calculated using the Euclidian
[g,u,v] = gcd(A,B) is calculated using the
extended Euclidian algorithm.
 Knuth, D. “Algorithms A and X.” The Art of Computer Programming, Vol. 2, Section 4.5.2. Reading, MA: Addison-Wesley, 1973.