拡張ユークリッドの互除法の使い方・応用例を解説【Python/Go】
![](https://tech.aru-zakki.com/wp-content/uploads/2024/02/extGCD-app.001.jpeg)
最大公約数(GCD)を求めるユークリッドの互除法を拡張した拡張ユークリッドの互除法というものがあります。この記事では、「拡張ユークリッドの互除法って何に使えるの?」という応用方法について解説します。拡張ユークリッドの互除法は、一次不定方程式の解を求めるのに便利です。
はじめに
拡張ユークリッドの互除法は、以下の式を満たす$x, y$を求めるものです。
$$
ax + by = gcd(a,b)
$$
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
上記の式は、ベズーの等式(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$が逆元となります
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
AtCoderなどの場合、mが素数であることが多いので、多くの場合、拡張ユークリッドの互除法で逆元を求めることが可能です
例:a = 3, m = 11の場合の逆元を求める
ユークリッドの互除法により、$gcd(a, m)=1, x = 4, y = -1$となります
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
プログラムで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となります(5倍にスケーリング)。
従って、答えは、$x=-5, y = 5$となります。
実際に式に代入すると、$4*(-5) + 6*5 = 20 – 30 = 10$となります。
上記のように、
$ax + by = c$の形に変形することができる問題の場合、ユークリッドの互除法を用いて整数解を求めることができます。
二次元グラフ中の点(x,y)を求める問題などに使えるテクニックです。
これを使う問題としてAtCoder ABC340-F問題などがあります。
応用問題
重さを合わせる
問題
3gと7gの2種類の分銅があります。この2つの分銅を使って25gを作ることはできますか?できる場合は、組み合わせのパターンを1つ提示してください。
解法
$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が負になっているので少し考える必要があります。
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
分銅をマイナス50個というのはありえないので、正にする必要があります
x, yの一般解は、以下になります。
$$
\begin{eqnarray}
x &=& x_0 + k\frac{b}{gcd(a,b)}\\
y &=& y_0 – k\frac{a}{gcd(a,b)}
\end{eqnarray}
$$
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
いきなり一般解がでますが、両方から同じだけの数を足し引きしているだけです。元の式に代入してみれば理解できるかと思います。
$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以上になる解を1つ求めれば良いことになります。
$$
\begin{eqnarray}
x &=& -50 + 7k \geqq 0\\
y &=& 25 – 3k \geqq 0
\end{eqnarray}
$$
例えば、k=8とすれば、$x=6, y=1$となり、これが答えになります。
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
満たす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$となります。
このような方法でも一般解を導くことが可能です。
まとめ
拡張ユークリッドの互除法って何につかえるのかわからない人向けに、応用例について解説してみました。基本は一次不定方程式を解くというものだと思います。