2024.02.25

記事内に商品プロモーションを含む場合があります

拡張ユークリッドの互除法の使い方・応用例を解説【Python/Go】

tadanori

最大公約数（GCD）を求めるユークリッドの互除法を拡張した拡張ユークリッドの互除法というものがあります。この記事では、拡張ユークリッドの互除法の応用例について解説します。

Contents

はじめに
拡張ユークリッドの互除法のプログラム
- Pythonのプログラム
- Go言語のプログラム
拡張ユークリッドの互除法の応用例
- 逆元を求める
- 一次不定方程式の解を求める
応用問題
- 重さを合わせる
まとめ

はじめに

拡張ユークリッドの互除法は、以下の式を満たす$x, y$を求めるものです。

$$
ax + by = gcd(a,b)
$$

上記の式は、ベズーの等式(Bézout’s identity)と呼ばれます。また、式を満たす整数x, yをベズー係数と呼びます。

アルゴリズムについては、色々な記事やブログにあるので、この記事では、アルゴリズム詳細については省略します。

この記事では、「これを求めることができると何が嬉しいの？」「何に使えるの？」という部分を少し掘り下げて解説したいと思います。

拡張ユークリッドの互除法のプログラム

拡張ユークリッドの互除法のプログラムはそれほど難しくありません。

Pythonのプログラム

extGCD(a,b)を呼び出すことで、gcd(a,b), x, yを返します。基本部分は、gcdを計算するプログラムと同じで、gcdを求めた後に、x,yを計算する処理が追加されたものになります。

def extGCD(a, b) :
    if b ==  0 :
        return a, 1, 0
    d, y, x = extGCD(b, a%b)
    y -= a//b * x
    return d, x, y

Go言語のプログラム

同じプログラムをGo言語で記述した場合です。

func extGCD(a, b int) (int, int, int) {
	if b == 0 {
		return a, 1, 0
	}
	d, y, x := extGCD(b, a%b)
	y -= a / b * x
	return d, x, y
}

拡張ユークリッドの互除法の応用例

逆元を求める

拡張ユークリッドの互除法を用いることでmod mにおける逆元を求めることができます。

逆元とは、以下の式を満たす$a^{-1}$です。

$$
a\cdot a^{-1} \equiv 1 \mod m
$$

注意点としては、拡張ユークリッドの互除法を用いる場合は、$gcd(a, m)=1$（aとmが違いに素）である必要があります。

$gcd(a, m)=1$とすると、拡張ユークリッドの互除法の式より、

$$
ax + my = gcd(a, m) = 1
$$

となります。$\mod m$で考えると両辺は、

$$
ax = 1 \mod m
$$

となり、$x = a^{-1}$、つまり$x$が逆元となります

AtCoderなどの場合、mが素数であることが多いので、多くの場合、拡張ユークリッドの互除法で逆元を求めることが可能です

例：a = 3, m = 11の場合の逆元を求める

ユークリッドの互除法により、$gcd(a, m)=1, x = 4, y = -1$となります

プログラムでextGCD(3,11)を計算してみてください

xが逆元なので、$\mod 11$における3の逆元は4となります

実際に計算すれば、$3*4 \equiv 1 (mod\ 11)$となることがわかります

一次不定方程式の解を求める

拡張ユークリッド互除法を用いて一次不定方程式$ax + by = c$を満たす整数$(x, y)$を求めることができます。

式が$ax + by = gcd(a,b)$と似ていることから、なんとなく使えそうなことがわかるかと思います。

cがgcd(a,b)で割り切れ無い場合は、整数解はありません。

cがgcd(a,b)で割り切れる場合は、$d = c/gcd(a,b)$とすると、

$$
a(dx) + b(dy) = d \cdot gcd(a,b)
$$

となり、ユークリッドの互除法で求めたx,yをd倍したものが解となります。

例：$6x+9y=3$の整数解を求めたい場合

拡張ユークリッド互除法（ext(6,9)）より、gcd(6,9)=3, x=-1, y = 1となります。

$3/gcd(6,9)=1$なので、d=1となるので、dx, dy = -1, 1となります（スケーリングは必要ない）。

従って、答えは、$x=-1, y = 1$となります。

例：$4x+6y=10$の整数解を求めたい場合

拡張ユークリッド互除法（ext(4,6)）より、gcd(4,6)=2, x=-1, y = 1となります。

$10/gcd(4,6)=5$なので、d=5となり、dx, dy = -5, 5となります（スケーリングは必要ない）。

従って、答えは、$x=-5, y = 5$となります。

実際に式に代入すると、$4*(-5) + 6*5 = 20 – 30 = 10$となります。

上記のように、

$ax + by = c$の形に変形することができる問題の場合、ユークリッドの互除法を用いて整数解を求めることができます。

二次元グラフ中の点(x,y）を求める問題などに使えるテクニックです。

これを使う問題としてAtCoder ABC340-F問題などがあります。

応用問題

重さを合わせる

問題

3gと7gの２種類の分銅があります。この２つの分銅を使って25gを作ることはできますか？できる場合は、組み合わせのパターンを１つ提示してください。

解法

$3x + 7y = 25$を求める問題です

ユークリッドの互除法を使うと、gcd(3,7)=1, x = -2, y = 1となります。

25/gcd(3,7)は割り切れるので、整数解が存在します。つまり、組み合わせが存在します。

$25/gcd(3,7) = 25$なので、解はx=-50, y = 25ですが、ただ、ｘが負になっているので少し考える必要があります。

分銅をマイナス５０個というのはありえないので、正にする必要があります

x, yの一般解は、以下になります。

$$
\begin{eqnarray}
x &=& x_0 + k\frac{b}{gcd(a,b)}\\
y &=& y_0 – k\frac{a}{gcd(a,b)}
\end{eqnarray}
$$

いきなり一般解がでますが、両方から同じだけの数を足し引きしているだけです。元の式に代入してみれば理解できるかと思います。

$gcd(a, b) = 1, a = 3, b = 7$として元の式に代入すると、

$$
3(x_0 + 7k) + 7(y_0 – 3k) = 3x_0 + 7y_0 = 25
$$

となり、x_0 = -50, y_0 = 25とすると、式を満たすことが分かります。

なので、一般解がx,yが0以上になる解を１つ求めれば良いことになります。

$$
\begin{eqnarray}
x &=& -50 + 7k \geqq 0\\
y &=& 25 – 3k \geqq 0
\end{eqnarray}
$$

例えば、k=8とすれば、$x=6, y=1$となり、これが答えになります。

満たすkがなければ、解なしです

実際に代入すると、$3\cdot 6 + 7\cdot 1 = 25$となり条件を満たします。

（参考）一般解の求め方

解を元の式に代入すると、

$$\begin{eqnarray}
3x + 7y = 25\\
3\times (-50) + 7 \times 25 = 25
\end{eqnarray}
$$

両辺を引くと、

$$\begin{eqnarray}
3(x+50) + 7(y-25) = 0\\
3(x+50) = -7(y-25)
\end{eqnarray}
$$

3と7は互いに素なので、x+50は7の倍数である必要があります。tを任意の整数とすると$x+50 = -7t$と表すと$x = -7t – 50$となります。

このような方法でも一般解を導くことが可能です。