MATLAB Function Reference

gcd

最大公因數(Greatest common divisor)

Syntax

G = gcd(A,B)
[G,C,D] = gcd(A,B)

Description

G = gcd(A,B) 回傳整數陣列 A 及 B 相對應元素的最大公因數(Greatest common divisor)。依照規定， gcd(0,0) 回傳 0；其他輸入的回傳值則須為正整數。

[G,C,D] = gcd(A,B) 回傳最大公因數(greatest common divisor)陣列 G，及額外兩陣列 C 及 D 使得 A(i).*C(i) + B(i).*D(i) = G(i)。這些對於解 Diophantine equations 及計算 elementary Hermite transformations 是很有幫助的。

Examples

第一個例子包含了 elementary Hermite transformations。

對於任意兩個整數 a 及 b ，存在一個行列式值為 1 的 2 x 2 整數矩陣 E [即 E 為單位模矩陣(a unimodular matrix)] 使得：

E * [a;b] = [g,0],

上式的 g 為 [g,c,d] = gcd(a,b) 所回傳的，即 a 及 b 的最大公因數(greatest common divisor)。

矩陣 E 等於：

c       d 
-b/g    a/g 

以 a = 2 及 b = 4 為例：

[g,c,d] = gcd(2,4)
g =
     2
c =
     1
d =
     0

則可計算出：

E =
    1     0
    -2     1

第二個例子則是解 Diophantine equation ： 30x + 56y = 8 的 x 及 y 。

[g,c,d] = gcd(30,56)
g =
     2
c =
    -13
d =
     7

根據定義，對於純數 c 及 d ，我們可知：

30(-13) + 56(7) = 2, 

左右同乘 8/2：

30(-13*4) + 56(7*4) = 8

和原式比較，我們即可得到解答：

x = (-13*4) = -52; y = (7*4) = 28

See Also

lcm

References

[1]  Knuth, Donald, The Art of Computer Programming, Vol. 2, Addison-Wesley: Reading MA, 1973. Section 4.5.2, Algorithm X.

gcbo

gcf