gcd

シンボリック数および多項式の最大公約数

構文

G = gcd(A)

G = gcd(A,B)

[G,M] = gcd(A)

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

説明

G = gcd(A) は、A のすべてのシンボリック要素の最大公約数 (GCD) を求めます。

G = gcd(A,B) は A および B の最大公約数を求めます。

[G,M] = gcd(A) は、G になる A の要素の線形結合係数 M も返します。

[G,U,V] = gcd(A,B,X) は、G = A*U + B*V となるようなベズー係数 U および V も返します。多変数多項式では、U および V の分母に現れないような多項式変数 X を指定します。X を指定しない場合、gcd は symvar によって決定される既定の変数を使用します。

例

シンボリック整数の最大公約数

シンボリック ベクトルの要素として指定された 4 つの整数の最大公約数を求めます。

A = sym([4420 -128 8984 -488]);
G = gcd(A)

G = $$4$$

または、これらの値をシンボリック行列の要素として指定します。

A = sym([4420 -128; 8984 -488]);
G = gcd(A)

G = $$4$$

有理数の最大公約数

有理数 $a_1,a_2,\dots ,a_n$ の最大公約数は、$a_1/g,a_2/g,\dots ,a_n/g$ が整数、かつ $\gcd \left(a_1/g,a_2/g,\dots ,a_n/g\right)=1$ である数 $g$ です。

5 つの有理数の最大公約数を求めます。

A = sym([1/4 1/3 1/2 2/3 3/4])

A = 
$$\left(\begin{array}{ccccc}\frac{1}{4}& \frac{1}{3}& \frac{1}{2}& \frac{2}{3}& \frac{3}{4}\end{array}\right)$$

G = gcd(A)

G = 
$$\frac{1}{12}$$

複素数の最大公約数

gcd は、ガウス整数 (実数部と虚数部が整数である複素数) について複素数の最大公約数を計算します。正の実数部と非負の虚数部をもつ複素数を返します。

3 つの複素数の最大公約数を求めます。

A = sym([3 + 1i, 4 - 2i, -5 - 5i]);
G = gcd(A)

G = $$3+\mathrm{i}$$

行列要素の最大公約数

入力引数を 2 つ指定し、その少なくとも一方が非スカラーの場合、gcd は要素単位で最大公約数を求めます。

2 つの行列の要素の最大公約数を求めます。非スカラーの入力引数を 2 つ指定する場合、それらは同じサイズでなければなりません。

A = sym([309 186; 486 224]);
B = sym([558 444; 1024 1984]);
G = gcd(A,B)

G = 
$$\left(\begin{array}{cc}3& 6\\ 2& 32\end{array}\right)$$

行列 A の要素および値 200 の最大公約数を求めます。ここで、gcd は 200 をすべての要素が 200 に等しい 2 行 2 列の行列に拡張します。

G = gcd(A,200)

G = 
$$\left(\begin{array}{cc}1& 2\\ 2& 8\end{array}\right)$$

多項式の最大公約数

2 つの一変数多項式の最大公約数を求めます。

syms x
A = x^3 - 3*x^2 + 3*x - 1;
B = x^2 - 5*x + 4;
G = gcd(A,B)

G = $$x-1$$

3 つの多変数多項式の最大公約数を求めます。多項式が 3 つ以上あるので、これらをシンボリック ベクトルの要素として指定します。

syms x y
A = [x^2*y + x^3, (x + y)^2, x^2 + x*y^2 + x*y + x + y^3 + y];
G = gcd(A)

G = $$x+y$$

入力の線形結合

整数論の定理は、2 つの数値の GCD がそれらの数値の最小の正の線形結合であることを記述します。64 と 44 の GCD がそれらの数値の正の線形結合であることを示します。

A = sym([64 44]);
[G,M] = gcd(A)

G = $$4$$

M = $$\left(\begin{array}{cc}-2& 3\end{array}\right)$$

tf = isequal(G,sum(M.*A))

tf = logical
   1

ベズー係数

2 つの多項式の変数 x について最大公約数とベズー係数を求めます。ベズー係数を計算する際、gcd は多項式変数がそれらの係数の分母に絶対に現れないようにします。

syms x y
[G,U,V] = gcd(x^2*y + x^3, (x + y)^2, x)

G = $$x+y$$

U = 
$$\frac{1}{y^2}$$

V = 
$$\frac{1}{y}-\frac{x}{y^2}$$

同じ多項式の変数 y について最大公約数とベズー係数を求めます。

[G,U,V] = gcd(x^2*y + x^3, (x + y)^2, y)

G = $$x+y$$

U = 
$$\frac{1}{x^2}$$

V = $$0$$

多項式の変数を指定しない場合、このツールボックスでは symvar により変数が決定されます。

[G,U,V] = gcd(x^2*y + x^3, (x + y)^2)

G = $$x+y$$

U = 
$$\frac{1}{y^2}$$

V = 
$$\frac{1}{y}-\frac{x}{y^2}$$

ディオファントス方程式の求解

ディオファントス方程式 $\left(1-z\right)x+z\left(1-2z\right)y=3$ を $x$ および $y$ について解きます。

最初に、このディオファントス方程式の $x$ と $y$ の係数、および右辺を定義します。

syms z
A = 1 - z;
B = z*(1 - 2*z);
R = 3;

構文 [G,U,V] = gcd(A,B) を使用して、多項式 A と B の最大公約数 G、および G = A*U + B*V となるようなベズー係数 U と V を求めます。

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

G = $$1$$

U = $$2\hspace{0.17em}z+1$$

V = $$-1$$

GCD で方程式の右辺が割り切れる場合、つまり R/G が整数であれば、ディオファントス方程式は解をもちます。ベズー係数 U と V を使用して、ディオファントス方程式の 1 つの特解と一般解を計算します。

if mod(R,G) == 0
  S = R/G;
  disp("Particular solution:")
  x1 = U*S
  y1 = V*S
  disp("General solution:")
  syms k integer
  x = x1 + B/G*k
  y = y1 - A/G*k
  params = assumptions(k)
else
  disp("This Diophantine equation does not have a solution.")
end

Particular solution:

x1 = $$6\hspace{0.17em}z+3$$

y1 = $$-3$$

General solution:

x = $$6\hspace{0.17em}z-k\hspace{0.17em}z\hspace{0.17em}\left(2\hspace{0.17em}z-1\right)+3$$

y = $$k\hspace{0.17em}\left(z-1\right)-3$$

params = $$k\in \mathbb{Z}$$

最後に、一般解がディオファントス方程式を満たすことを確認します。

eqCheck = simplify(A*x + B*y) == R

eqCheck = $$3=3$$

入力引数

A — 入力値

シンボリック数 | シンボリック変数 | シンボリック式 | シンボリック関数 | シンボリック ベクトル | シンボリック行列

入力値。シンボリック数、シンボリック変数、シンボリック式、シンボリック関数、あるいはシンボリック数、シンボリック変数、シンボリック式、シンボリック関数のベクトルまたは行列として指定します。

B — 入力値

シンボリック数 | シンボリック変数 | シンボリック式 | シンボリック関数 | シンボリック ベクトル | シンボリック行列

入力値。シンボリック数、シンボリック変数、シンボリック式、シンボリック関数、あるいはシンボリック数、シンボリック変数、シンボリック式、シンボリック関数のベクトルまたは行列として指定します。

A と B が非スカラーの場合、それらは同じサイズでなければなりません。A または B の一方がスカラーの場合、gcd は、すべての要素が対応するスカラーと等しい、非スカラー引数と同じサイズのベクトルまたは行列にスカラーを拡張します。

X — 多項式の変数

シンボリック変数

多項式の変数。シンボリック変数として指定します。既定では、gcd は symvar によって決定される変数を使用します。

出力引数

G — 最大公約数

シンボリック数 | シンボリック変数 | シンボリック式 | シンボリック関数 | シンボリック ベクトル | シンボリック行列

最大公約数。シンボリック数、変数、式、関数、あるいはシンボリック数、変数、式、関数のベクトルまたは行列として返されます。

M — 入力 A の要素の線形結合係数

シンボリック ベクトル | シンボリック行列 | シンボリック配列

入力 A の GCD に等しい入力要素の線形結合係数。シンボリック ベクトル、シンボリック行列、またはシンボリック配列として返されます。

U,V — ベズー係数

シンボリック数 | シンボリック変数 | シンボリック式 | シンボリック関数 | シンボリック ベクトル | シンボリック行列

ベズー係数。シンボリック数、変数、式、関数、あるいはシンボリック数、変数、式、関数のベクトルまたは行列として返されます。

ヒント

• シンボリック オブジェクトではない数値で gcd を呼び出すと、MATLAB^® の gcd 関数が呼び出されます。

• MATLAB 関数 gcd は有理数または複素数の引数を受け入れません。有理数または複素数の最大公約数を求めるには、sym を使用してこれらの数値をシンボリック オブジェクトに変換した後で gcd を使用します。

バージョン履歴

R2014b で導入

参考

lcm