Greatest common divisor
Greatest Common Divisors of Double Values
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.
Greatest Common Divisors of Unsigned Integers
A = uint16([255 511 15]); B = uint16([15 127 1023]); G = gcd(A,B)
G = 1x3 uint16 row vector 15 1 3
Solution to Diophantine Equation
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
scalars, vectors, or arrays of real integer values
Input values, specified as scalars, vectors, or arrays of real
be any numeric type, and they can be of different types within certain
Bis of type
single, then the other can be of type
Bbelongs to an integer class, then the other must belong to the same class or it must be a
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
real, nonnegative integer values
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
real integer values
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 Euclidean algorithm.
[g,u,v] = gcd(A,B) is calculated using the extended Euclidean
 Knuth, D. “Algorithms A and X.” The Art of Computer Programming, Vol. 2, Section 4.5.2. Reading, MA: Addison-Wesley, 1973.
C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.
Run code in the background using MATLAB®
backgroundPool or accelerate code with Parallel Computing Toolbox™
This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.
Introduced before R2006a