Documentation

This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.

gcd

Greatest common divisor

Syntax

Description

example

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.

example

[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

collapse all

A = [-5 17; 10 0];
B = [-15 3; 100 0];
G = gcd(A,B)
G =

     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 =

  1×3 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

   1

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

x = u*4
y = v*4
x =

   -52


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.

More About

collapse all

Algorithms

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]

References

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

See Also

Introduced before R2006a

Was this topic helpful?