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) はベズー係数 U と V も返します。これらは、A.*U + B.*V = G を満たします。ベズー係数はディオファントス方程式を解くのに便利です。この構文は、double、single、符号付き整数の入力をサポートします。

例

すべて折りたたむ

ライブ スクリプトを開く
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
ライブ スクリプトを開く

ディオファントス方程式 30x+56y=8 を解き、x および y を求めます。

30 と 56 の最大公約数と、ベズー係数の組を求めます。

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

u = -13

v = 7

u と v はベズーの恒等式 (30*u) + (56*v) = g を満たします。

ベズーの恒等式を、元の方程式に近くなるように書き換えます。これは、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 は非 double 型として返されます。

ベズー係数。方程式 A.*U + B.*V = G を満たす実数の整数値の配列として返されます。U および V のデータ型は、A および B と同じ型です。A と B の型が異なる場合、U および V は非 double 型として返されます。

アルゴリズム

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 より前に導入

参考