MATLAB Function Reference

gcd

最大公約数

表示

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

詳細

G = gcd(A,B) は、整数配列 A と B の対応する要素同士の最大公約数を含んだ配列を出力します。便宜上、gcd(0,0) は値 0 を出力します。その他の入力に対しては、G には正の整数が出力されます。

[G,C,D] = gcd(A,B) は、最大公約数を含んだ配列 G と、方程式 A(i).*C(i) + B(i).*D(i) = G(i) を満足する配列 C 、および、Dを出力します。これらは、Diophantine方程式を解いたり、初等エルミート変換を計算するために便利です。

例題

最初の例は、初等エルミート変換に関するものです。

任意の2つの整数 a と b に対して、整数要素をもち、行列式が、つぎのような一つの2行2列の行列 E (ユニモジュラ行列)があります。

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

ここで、g は、コマンド [g,c,d] = gcd(a,b) によって出力されるようなa と b の最大公約数です。

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方程式 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

参考

lcm

参考文献

Knuth, Donald, The Art of Computer Programming, Vol. 2, Addison-Wesley: Reading MA, 1973. Section 4.5.2, アルゴリズム X.

gcbo

gcf