Main Content

gcd

最大公约数

说明

示例

G = gcd(A,B) 返回 AB 的元素的最大公约数。G 中的元素始终是非负值,gcd(0,0) 返回 0。此语法支持任何数值类型的输入。

示例

[G,U,V] = gcd(A,B) 还返回 Bézout 系数 UV,它们满足:A.*U + B.*V = G。Bézout 系数用于对 Diophantine 方程求解。此语法支持双精度、单精度和有符号整数输入。

示例

全部折叠

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

     5     1
    10     0

gcd 返回正值,即使输入为负数也是如此。

A = uint16([255 511 15]);
B = uint16([15 127 1023]);
G = gcd(A,B)
G = 1x3 uint16 row vector

   15    1    3

xy 的 Diophantine 方程 30x+56y=8 求解。

3056 的最大公约数和一对 Bézout 系数。

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

uv 满足 Bézout 恒等式 (30*u) + (56*v) = g

重新编写 Bézout 恒等式,使其看起来更像原始方程。通过乘以 4 来实现这一点。使用 == 验证方程的两端是否相等。

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

计算对该问题求解的 xy 的值。

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

输入参数

全部折叠

输入值,指定为标量、向量或实整数值数组。AB 可以是任意数值类型,在一定的限制范围内它们的类型可以不同:

  • 如果 AB 属于 single 类型,则另一个可以是 singledouble 类型。

  • 如果 AB 属于整数类,则另一个必须属于相同类或必须是 double 标量值。

AB 必须大小相同或一个必须为标量。

示例: [20 -3 13],[10 6 7]

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

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

数据类型: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

输出参数

全部折叠

最大公约数,以非负实整数值数组形式返回。G 的大小与 AB 相同,G 中的值始终为非负实数。G 的返回值的类型与 AB 的类型相同。如果 AB 的类型不同,则 G 以非双精度类型形式返回。

Bézout 系数,以满足方程 A.*U + B.*V = G 的实整数值数组形式返回。UV 的数据类型与 AB 的数据类型相同。如果 AB 的类型不同,则 UV 以非双精度类型形式返回。

算法

g = gcd(A,B) 是使用欧几里德算法来计算的。[1]

[g,u,v] = gcd(A,B) 是使用扩展欧几里德算法来计算的。[1]

参考

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

扩展功能

C/C++ 代码生成
使用 MATLAB® Coder™ 生成 C 代码和 C++ 代码。

版本历史记录

在 R2006a 之前推出

另请参阅