このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

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、符号付き整数の入力をサポートします。

例

double 値の最大公約数

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 = 1×3 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 は任意の数値型にでき、特定の制限内で異なる型にすることもできます。

• 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 — 最大公約数

実数、非負の整数値

最大公約数。実数かつ非負の整数値の配列として返されます。G は A および B と同じサイズであり、G 内の値は常に実数かつ非負です。G は A および B と同じ型として返されます。A と B の型が異なる場合、G は非 double 型として返されます。

U,V — ベズー係数

実数の整数値

ベズー係数。方程式 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++ コードを生成します。

スレッドベースの環境

MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

この関数はスレッドベースの環境を完全にサポートしています。詳細については、スレッドベースの環境での MATLAB 関数の実行を参照してください。

バージョン履歴

R2006a より前に導入

参考

lcm