gcd

4 つの整数の最大公約数

3 つ以上の値の最大公約数を求めるには、それらの数値をシンボリックなベクトルまたは行列として指定します。

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

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

A =
[ 4420, -128, 8984, -488]
 
ans =
4

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

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

A =
[ 4420, -128]
[ 8984, -488]
 
ans =
4

多項式の最大公約数

一変数および多変数の多項式の最大公約数を求めます。

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

syms x
gcd(x^3 - 3*x^2 + 3*x - 1, x^2 - 5*x + 4)

ans =
x - 1

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

syms x y
gcd([x^2*y + x^3, (x + y)^2, x^2 + x*y^2 + x*y + x + y^3 + y])

ans =
x + y

有理数の最大公約数

有理数 a1,a2,... の最大公約数は、g/a1,g/a2,... が整数、かつ gcd(g/a1,g/a2,...) = 1 である数 g です。

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

gcd(sym([1/4, 1/3, 1/2, 2/3, 3/4]))

ans =
1/12

複素数の最大公約数

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

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

gcd(sym([10 - 5*i, 20 - 10*i, 30 - 15*i]))

ans =
5 + 10i

行列要素の最大公約数

ベクトルと行列に対して gcd は要素単位の最大公約数を求めます。非スカラー引数のサイズは同じでなければなりません。

次の 2 つの行列要素の最大公約数を求めます。

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

ans =
[ 3,  6]
[ 2, 32]

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

gcd(A,200)

ans =
[ 1, 2]
[ 2, 8]

GCD が入力の正の線形結合

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

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

G =
4
M =
[ -2, 3]

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

ans =
  logical
   1

ベズー係数

以下の多項式の最大公約数とベズー係数を求めます。多変数式の場合は、第 3 の入力引数を使用して多項式変数を指定します。ベズー係数を計算する際、gcd は多項式変数がその分母に絶対に現れないようにします。

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

[G,C,D] = gcd(x^2*y + x^3, (x + y)^2, x)

G =
x + y
 
C =
1/y^2
 
D =
1/y - x/y^2

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

[G,C,D] = gcd(x^2*y + x^3, (x + y)^2, y)

G =
x + y
 
C =
1/x^2
 
D =
0

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

[G,C,D] = gcd(x^2*y + x^3, (x + y)^2)

G =
x + y
 
C =
1/y^2
 
D =
1/y - x/y^2

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

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

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

[G,C,D] = gcd(sym(30),56)

G =
2
 
C =
-13
 
D =
7

C = -13 と D = 7 はベズーの恒等式 (30*(-13)) + (56*7) = 2 を満たします。

ベズーの恒等式を、元の方程式に近くなるように書き換えます。これは、4 で乗算することで行います。== を使用して、方程式の両側が等しいことを確認します。

isAlways((30*C*4) + (56*D*4) == G*4)

ans =
  logical
   1

ディオファントス方程式を解く x と y の値を計算します。

x = C*4
y = D*4

x =
-52
 
y =
28