gcd

Greatest common divisor

Syntax

G = gcd(A,B)

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

Description

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.

Examples

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, $$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
   1

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

x = u*4

x = 
-52

y = v*4

y = 
28

Input Arguments

A,B — Input values

scalars, vectors, or arrays of real integer values

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

G — Greatest common divisor

real, nonnegative integer values

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.

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

Algorithms

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

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

References

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

Thread-Based Environment

Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

Version History

Introduced before R2006a