This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English version of the page.

Note: This page has been translated by MathWorks. Click here to see
To view all translated materials including this page, select Country from the country navigator on the bottom of this page.


Greatest common divisor


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



G = gcd(A,B) returns the greatest common divisors of the elements of A and B. The elements in G are always nonnegative, and gcd(0,0) returns 0. This syntax supports inputs of any numeric type.


[G,U,V] = gcd(A,B) also returns the Bézout coefficients, U and V, which satisfy: A.*U + B.*V = G. The Bézout coefficients are useful for solving Diophantine equations. This syntax supports double, single, and signed integer inputs.


collapse all

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, 30x+56y=8 for x and y.

Find the greatest common divisor and a pair of Bézout coefficients for 30 and 56.

[g,u,v] = gcd(30,56)
g = 2
u = -13
v = 7

u and 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 4. Use == to verify that both sides of the equation are equal.

(30*u*4) + (56*v*4) == g*4
ans = logical

Calculate the values of x and y that solve the problem.

x = u*4
x = -52
y = v*4
y = 28

Input Arguments

collapse all

Input values, specified as scalars, vectors, or arrays of real integer values. A and B can be any numeric type, and they can be of different types within certain limitations:

  • If A or B is of type single, then the other can be of type single or double.

  • If A or B belongs to an integer class, then the other must belong to the same class or it must be a double scalar value.

A and B must be the same size or one must be a scalar.

Example: [20 -3 13],[10 6 7]

Example: int16([100 -30 200]),int16([20 15 9])

Example: int16([100 -30 200]),20

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Output Arguments

collapse all

Greatest common divisor, returned as an array of real nonnegative integer values. G is the same size as A and B, and the values in G are always real and nonnegative. G is returned as the same type as A and B. If A and B are of different types, then G is returned as the nondouble type.

Bézout coefficients, returned as arrays of real integer values that satisfy the equation, A.*U + B.*V = G. The data type of U and V is the same type as that of A and B. If A and B are of different types, then U and V are returned as the nondouble type.


g = gcd(A,B) is calculated using the Euclidian algorithm.[1]

[g,u,v] = gcd(A,B) is calculated using the extended Euclidian algorithm.[1]


[1] Knuth, D. “Algorithms A and X.” The Art of Computer Programming, Vol. 2, Section 4.5.2. Reading, MA: Addison-Wesley, 1973.

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

See Also

Introduced before R2006a