拡張ユークリッドの互除法について

競技プログラミングをやっていて拡張ユークリッドの互除法という単語を目にしましたが、よくわかりませんでした。

最近、数論の本を読んでいてユークリッドの互除法を勉強したので、いまなら拡張ユークリッドの互除法がわかるかなぁといろいろ調べてみました。

まず、ユークリッドの互除法とは整数 \(a,b\) の最大公約数( \(gcd(a,b)\) )を素早く求めることのできる操作です。

ユークリッドの互除法について気になる場合は、以下の記事で説明してみたので読んでみてください。

それでは拡張ユークリッドの互除法について書いていきます。

拡張ユークリッドの互除法とは

そして、拡張ユークリッドの互除法とは、ユークリッドの互除法を利用して、

\(a,b\)を整数とする方程式 \(ax+by=gcd(a,b)\) の整数解のひとつを求める操作のことを言います。

どんな操作なのか

ユークリッドの互除法では、2つの整数 \(a, b\) について、

\(\begin{aligned} a&=b\times{q_0}+r_0\\ b&=r_{0}\times{q_1}+r_1\\ r_0&=r_{1}\times{q_2}+r_2\\ \vdots\\r_{n-2}&=r_{n-1}\times{q_n}+r_n\\r_{n-1}&=r_{n}\times{q_{n+1}}\end{aligned}\)

このような操作で \(gcd(a,b)=r_n\) を求めていました。

ここで第一行の式に注目します。

\(\begin{aligned}a&=bq_{0}+r_0 \\ r_0 &= a-bq_0\end{aligned}\)

となり、 \(r_0\) を\(a,b\) の倍数の和で表すことができます。

この結果を第二行に代入してみます。

\(\begin{aligned}b&=r_0 \times q_1 + r_1 \\ b&= (a-bq_0)q_1+r_1 \\ b&=aq_1-bq_{0}q_{1}+r_1 \\ r_1 &= -aq_1+b(q_{0}q_{1}+1)\end{aligned}\)

となり、\(r_1\)も\(a,b\)の倍数の和で表すことができます。

この操作を繰り返していくと \(r_i(0\le i \le n)\) も \(a,b\) の倍数の和で表すことができます。

最終的に、

\(r_n = ka+lb\)

の形で表すことができます。

\(r_n=gcd(a,b)\) であることから、

\(ka+bl=gcd(a,b)\)

となり、整数解を求めたい方程式の形になります。

よって、 \((x,y)=(k,l)\) が整数解のひとつとなります。

\(a,b\) の係数を \(k,l\) と置いてますが実際の操作では整数となります。

ためしに求めてみる

文字を使った式ばかりだとイメージしづらいので、具体的な整数を与えて実際に計算してみましょう。

\(a=7,b=5\) として、ともに素数なので \(gcd(a,b)=1\) です。

拡張ユークリッドの互除法で整数解を求められる方程式は

\(7x+5y=1\)

となります。

それでは整数解を求めていきます。

まずはユークリッドの互除法で \(gcd(7,5)\) を求める操作を行います。

\(\begin{aligned}7 &= 5 \times 1 + 2 \\ 5 &= 2 \times 2 + 1 \\ 2 &= 1 \times 2 + 0\end{aligned}\)

となるので、 \(gcd(7,5)=1\) となります。

第一行の余りを \(r_0=2\) 、第二行の余りを \(r_1=1\) と表します。

第三行で割り切れているので \(gcd(7,5)=r_1=1\) となりますね。

\(a=7,b=5\) として第一行の式を \(a,b\) を用いた式に置き換えて、余り \(r_0=2\) を \(a,b\) を用いて表します。

\(\begin{aligned}7 &= 5 \times 1 + 2 \\ a &= b + 2 \\ 2 &= a – b \end{aligned}\)

つぎに第二行の式に注目します。

第二行では \(b=5, r_0=2=a-b\) を代入して、 \(r_1=1\) を \(a,b\) を用いて表します。

\(\begin{aligned}5 &= 2 \times 2 + 1 \\ b &= 2r_0 + 1 \\ b &= 2(a-b) + 1 \\ b &= 2a – 2b + 1 \\ 1 &= -2a +3b \end{aligned}\)

\(r_1\) を \(a,b\) で表した式に注目してみましょう。

\(-2a+3b=1\)

\(a=7,b=5\) でしたので、これらを代入すると、

\(7 \times (-2) + 5 \times 3 = 1\)

となり等式は成立しています。

ここで、\(a\) の係数は \(-2\) 、 \(b\) の係数は \(3\) となっており、それぞれが \(x,y\) に対応しています。

よって、 \(7x+5y=1\) の整数解のひとつは、 \((x,y)=(-2,3)\) となります。

ちなみに整数解のひとつとずっと書いていますが、\((x,y)=(3,-4),(-7,10)\) のようにほかにも整数解があります。

ココでほかの整数解に注目してみると、

\((3,-4) = (-2 + 5, 3 + (-7))\) 、 \((-7,10)=(-2 + (-5),3 + 7)\) というように表せます。

求めた整数解にたいして、 \(x\) には \(b=5\) の倍数を、 \(y\) には \(a=7\) の倍数を加えたらなんだか新しい整数解を作れそうですね。

ちょっと調べてみます。

ほかの整数解を求めてみる

拡張ユークリッドの互除法で求めた整数解をもとにしてほかの整数解を作ることができるか調べてみましょう。

何回も \(gcd(a,b)\) と書くのはしんどいので \(gcd(a,b)=g\) とします。

それでは2組の整数解の間にある関係を調べていこうと思います。

\((x_1, y_1)\) と \((x_2,y_2)\) を \(ax+by=g\) の整数解とします。

よって、

$$\tag{1} ax_1 + by_1 = g$$
$$\tag{2} ax_2 + by_2 = g$$

となります。

式\((1)\)に \(y_2\) をかけ、式\((2)\)に \(y_1\) をかけて、

\(\begin{aligned}ax_1 y_2 + by_1 y_2 &= y_2 g \\ ax_2 y_1 + by_1 y_2 &= y_1 g\end{aligned}\)

として、2つの式の差をとります。

\(\begin{aligned}(ax_1 y_2 + by_1 y_2) – (ax_2 y_1 + by_1 y_2) &= g( y_2 – y_1 ) \\ ax_1 y_2 – ax_2 y_1 + by_1 y_2 – by_1 y_2 &= g( y_2 – y_1 ) \\ a(x_1 y_2 – x_2 y_1) &= g( y_2 – y_1 ) \end{aligned}\)

$$\tag{3} a(x_1 y_2 – x_2 y_1) = g( y_2 – y_1 )$$

が求まります。

次に、式\((1)\)に \(x_2\) をかけ、式\((2)\) に \(x_1\) をかけて、

\(\begin{aligned}ax_1 x_2 + bx_2 y_1 &= x_2 g \\ ax_1 x_2 + bx_1 y_2 &= x_1 g\end{aligned}\)

として、2つの式の差を取ります。

\(\begin{aligned}(ax_1 x_2 + bx_2 y_1)-(ax_1 x_2 + bx_1 y_2) &= g( x_2 – x_1 ) \\ ax_1 x_2 – ax_1 x_2 + bx_2 y_1 – bx_1 y_2 &= g( x_2 – x_1 ) \\ b(x_2 y_1 – x_1 y_2) &= g( x_2 – x_1 ) \end{aligned}\)

$$\tag{4} b(x_2 y_1 – x_1 y_2) = g( x_2 – x_1 )$$

が求まります。

ここで、 \(k = x_1 y_2 – x_2 y_1\) とおくと、式\((3)\) は、

\(\begin{aligned}ak &= g( y_2 – y_1 )\\ \dfrac{ak}{g} &= y_2 – y_1 \\ y_2 &= y_1 + \dfrac{ak}{g}\end{aligned}\)

式\((4)\) は、

\(\begin{aligned}b(-k) &=g( x_2 -x_1 ) \\ \dfrac{-bk}{g} &= x_2 – x_1 \\ x_2 &= x_1 – \dfrac{bk}{g} \end{aligned}\)

となります。

\(gcd(a,b)=g\) ですので、 \(\dfrac{a}{g}\) も \(\dfrac{b}{g}\) も整数になりますね。

つまり、 \((x_2 , y_2)=(x_1 – \dfrac{bk}{g} , y_1 + \dfrac{ak}{g})\) となります。

これより、 \(ax+by=gcd(a,b)\) の2組の整数解の間にある関係がわかりました。

ある整数解 \((x_1, y_1)\) がわかれば、それ以外の整数解は \((x_1 -\dfrac{bk}{g}, y_1 +\dfrac{ak}{g})\) の形で表すことができます。

1次方程式ax+by=cの整数解を求める

拡張ユークリッドの互除法を用いることで、 \(ax+by=gcd(a,b)\) の整数解のひとつを求められることはわかりました。

また、求めた整数解をもとにしてそれ以外の整数解を求められることもわかりました。

しかし、 \(ax+by=c\) のような一般的な方程式については適用できないのかなと疑問があります。

どんな場合が適用できて、どんな場合がダメなのかということを調べていきます。

方程式が整数解を持つ条件

$$\tag{5}ax+by=c$$

が整数解を持つ条件について考えていきます。

先程の拡張ユークリッドの互除法では、 \(ax+by=gcd(a,b)\) について整数解を求めました。

というわけで、最大公約数に注目して考えていきます。

\(gcd(a,b)=g\) とおくと、 \(a,b\) はある整数\(m,n\) を用いて、\(a = gm,b=gn\) と表すことができます。

式\((5)\) に代入すると、

\(\begin{aligned} ax+by &= c \\ gmx + gny &= c \\ g(mx+ny) &= c \end{aligned}\)

となるので、 \(c\) は \(g\) の倍数になります。

よって、 \(ax+by=c\) が整数解を持つためには、 \(c\) が \(g\) の倍数である必要があります。

それでは逆に、 \(c\) が \(g\) の倍数であれば、必ず整数解を持つのか確認してみます。

\(c\) は \(g\) の倍数であるから、適当な整数 \(m\) を用いて、 \(c=mg\) と表せます。

\(ax+by=g\) は整数解を持つことがわかっているので、整数解を \((x_1,y_1)\) とすると、

\(ax_1+by_1=g\)

両辺を \(m\) 倍すると、

\(\begin{aligned}amx_1 + bmy_1 &= mg \\ a(mx_1) + b(my_1) &= c\end{aligned}\)

となるので、\(ax+by=c\) の整数解は \((mx_1, my_1)\) となります。

ためしに求めてみる

さきほどは、 \(7x+5y=1\) について整数解を求めましたが、 \(3x+5y=4\) について整数解を求めてみましょう。

まず、ユークリッドの互除法で \(gcd(3,5)\) を求めましょう。

\(\begin{aligned}5 &= 3 \times 1 + 2 \\ 3 &= 2 \times 1 + 1 \\ 2 &= 1 \times 2 + 0\end{aligned}\)

となるので、 \(gcd(3,5)=1\) ですね。

まず、 \(a = 3, b = 5\) とおいて拡張ユークリッドの互除法を適用し、 \(ax+by=gcd(a,b)\) の整数解を求めます。

\(\begin{aligned}b &= a + 2 \\ 2 &= -a + b\end{aligned}\)

\(\begin{aligned}a &= 2 + 1 \\ a &= -a + b + 1 \\ 2a -b &= 1\end{aligned}\)

よって、 \((x,y)=(2,-1)\) が \(3x+5y=1\) の整数解となります。

これをもとにして \(3x+5y=4\) の整数解を求めるには、両辺を \(4\) 倍すればよいです。

つまり、

\(\begin{aligned}3 \times 2 + 5 \times (-1) &= 1 \\ 3 \times 8 + 5 \times (-4) &= 4\end{aligned}\)

ですので、 \((x,y)=(8,-4)\) が整数解となります。