Main Content

gcd

最大公约数

全页折叠

语法

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

说明

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

示例

[G,U,V] = gcd(A,B) 还返回 Bézout 系数 U 和 V，它们满足：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
打开实时脚本

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

求 30 和 56 的最大公约数和一对 Bézout 系数。

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

u = 
-13

v = 
7

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

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

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

计算对该问题求解的 x 和 y 的值。 

x = u*4
x = 
-52

y = v*4
y = 
28

输入参数

全部折叠

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

  • 如果 A 或 B 属于 single 类型，则另一个可以是 single 或 double 类型。

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

A 和 B 必须大小相同或一个必须为标量。

示例: [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 的大小与 A 和 B 相同，G 中的值始终为非负实数。G 的返回值的类型与 A 和 B 的类型相同。如果 A 和 B 的类型不同，则 G 以非双精度类型形式返回。

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

算法

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 之前推出

另请参阅