1次不定方程式の整数解と、互除法による解き方、解ける条件

どうも、木村（@kimu3_slime）です。

今回は、1次不定方程式の整数解とは何か、その互除法による解き方、解ける条件を紹介します。

1次不定方程式の整数解とは
互除法による解き方
1次不定方程式が解ける条件
こちらもおすすめ

1次不定方程式の整数解とは

20個のおはじきを、1袋に2個入る袋と、1袋に3個入る袋に分けたい、という問題を考えましょう。袋の数をそれぞれ\(x,y\)とすると、

\[ \begin{aligned}2x +3y =20\end{aligned} \]

という方程式を解くことになります。

一般に、\(a,b,c\)を定まった整数として、

\[ \begin{aligned}ax+by=c\end{aligned} \]

を満たす整数\(x,y\)を求める問題を1次不定方程式、またはディオファントス方程式（Diophantine equation）と呼びます。ディオファントスは古代の数学者で、紀元前から考えられてきた由緒ある問題です。

\(2x +3y =20\)程度の簡単な問題なら、答えを手探りで見つけることができます。適当に数を代入して試してみれば良いのです。

例えば、\(x=7,y=2\)は解ですね。方程式のひとつの解を、特殊解と呼びます。1次不定方程式の解は、ただひとつではありません。未知数を2つ\(x,y\)持つ場合、少なくとも2つの方程式がなければ、答えは唯ひとつに定まりません（2元連立1次方程式）。このような答えの定まらなさがあるから、不定方程式と呼ばれるわけですね。

特殊解\(x=7,y=2\)を手がかりに、一般の解を探してみましょう。\(x,y\)を一般の解とします。すると、\(2x+3y =20\)、\(2\cdot 7+ 3\cdot 2 =20\)が成り立ちます。一方の式からもう一方を引くと、\(2(x-7)=-3(y-2)\)です。右辺は\(3\)の倍数で、\(2\)は\(3\)の約数ではないので（\(2,3\)は互いに素）、\(x-7\)は\(3\)の倍数でなければなりません。つまり、\(x-7 =3k \)となる整数\(k\)が存在します。

\(x,y\)について整理すると、\(x= 3k+7\)で、\(y=-2k+2\)となりました。方程式のすべての解はこの形に表されるので、それを一般解と呼びます。最初に求めたのは\(k=0\)の特殊なケースだったというわけです。

一般解は、整数\(k\)が無限に存在するので、無限に存在します。しかし、例えば\(x,y\)それぞれが\(0\)以上\(x,y \geq 0\)であるという条件を課せば、\(k\)の範囲が絞り込めて、解の候補が有限個となります。今回の例ならば、\(x\geq 0\)から\(k \geq -2\)、\(y\geq 0\)から\(k \leq 1\)です。したがって、\((x,y)=(1,6),(4,4),(7,2),(10,0)\)が解となります。

互除法による解き方

1次不定方程式は、（解ける時は）ユークリッドの互除法によって解くことができます。

\(2016x +216 y =14400\)を解いてみましょう。さきほどのように、適当にあたりをつけるのは難しいのではないでしょうか。

そこで、係数\(a=2016,b=216\)にユークリッドの互除法を適用します。

\[ \begin{aligned}2016 =9\cdot 216+72\end{aligned} \]

\[ \begin{aligned}216 = 3\cdot72+0\end{aligned} \]

最大公約数は\(\mathrm{gcd}(2016,216)=72\)です。これを使って\(c=14400=200\cdot 72\)と分解できるので、この形を利用しましょう。上で得た式の両辺に\(200\)をかければ、

\[ \begin{aligned}2016\cdot 200 =9\cdot 216 \cdot 200+72\cdot 200\end{aligned} \]

\[ \begin{aligned}2016\cdot 200 -216\cdot 1800=14400\end{aligned} \]

なので、\(x=200,y=-1800\)は方程式\(2016x +216 y =14400\)の解です。特殊解が得られました。一般解の求め方は、さきほどと同様なので省略します。

別の例として、\(201x+80y=1\)を解いてみましょう。係数\(a=201,b=80\)に対して、ユークリッドの互除法を用います。

\[ \begin{aligned}201 =2\cdot80 +41\end{aligned} \]

\[ \begin{aligned}80 = 1\cdot 41 +39\end{aligned} \]

\[ \begin{aligned}41 = 1\cdot39+2\end{aligned} \]

\[ \begin{aligned}39= 19\cdot 2 +1\end{aligned} \]

\[ \begin{aligned}2= 1\cdot2 +0\end{aligned} \]

これらの式をたどっていくことで、\(201x+80y=1\)の形を生み出すことができます。

\[ \begin{aligned} 1 &=39-19\cdot2\\ &=39-19\cdot(41-39) \\&=20\cdot(80-41)-19\cdot 41 \\ &=20\cdot 80 -39\cdot 41 \\ &=20\cdot 80 -39\cdot (201-2\cdot 80) \\&=-39\cdot 201+98\cdot 80\end{aligned} \]

よって、\(x=-39,y=98\)が特殊解として得られました。

1次不定方程式が解ける条件

さて、互除法による解き方はなぜうまくいくのでしょうか。

そもそも、1次不定方程式\(ax+by=c\)はいつでも解ける（解を持つ）わけではありません。例えば、\(2x+2y=1\)には解が存在しません。左辺は偶数であり、右辺は奇数なので。

1次不定方程式が解ける条件として、次の定理が知られています。

\(d=\mathrm{gcd}(a,b)\)とする。\(ax+by=c\)が解を持つことと、\(d \mid c\)は同値。

まず、\(d \mid c\)を仮定して、\(ax+by=c\)が解を持つことを確かめましょう。

\(d =\mathrm{gcd}(a,b) \)と置きます。仮定より、\(c =kd \)となる整数\(k\)が存在します。ユークリッドの互除法より、\(a=q_1b+r_1\)、\(b=q_2r_1 +r_2\)、…、\(r_{n}=q_{n}r_{n+1}+0\)、\(r_{n}=d\)が成り立ちます。

ここで、すべての\(n\)に対し、\(ax_n+by_n=r_n\)を満たす整数\(x_n,y_n\)が存在することを示しましょう。数学的帰納法を用います。

\(n=1\)のとき、\(a=q_1b+d\)なので、\(a-q_1 b=d\)で\(x_0=1,y_0=-q_1\)とすれば良いです。
\(1 \leq n\leq k\)のとき、\(ax_k+by_k=r_k\)となる\(x_k,y_k\)が存在すると仮定します。\(n=k+1\)のとき、\(ax_{k+1}+by_{k+1}=r_{k+1}\)となる\(x_{k+1},y_{k+1}\)が存在することを示せば良いです。互除法の等式より、\(r_{k-1}=q_{k-1}r_{k}+r_{k+1}\)が成り立っています。仮定の式の両辺に\(q_{k-1}\)をかけると、\(ax_k q_{k-1} +by_k q_{k-1} = r_k q_{k-1}=r_{k-1}-r_{k+1}\)が成り立ちます。仮定より\(r_{k-1}=ax_{k-1}+by_{k-1}\)を用いて整理すると、
\[ \begin{aligned} r_{k+1}&= -ax_k q_{k-1} -by_k q_{k-1}+r_{k-1}\\ &=a(x_{k-1}-x_k q_{k-1})+b(y_{k-1}-y_k q_{k-1})\end{aligned} \]となり、\(x_{k+1}=x_{k-1}-x_k q_{k-1}\)、\(y_{k+1}=y_{k-1}-y_k q_{k-1}\)とすれば良いです。

示したことを元の議論に適用すると、\(ax_n+by_n=r_n\)を満たす整数\(x_n,y_n\)が存在します。互除法によって\(r_n =d\)であること、仮定より\(c =kd \)であることを思い出しましょう。\(ax_n+by_n=r_n\)に\(k\)をかければ、\(akx_n+bky_n =kr_n= kd =c\)が成り立ちます。よって、\(x=kx_n,y=ky_n\)とおけば、\(ax+by=c\)を満たすことがわかりました。

逆に、\(ax+by=c\)が解を持つならば、\(d \mid c\)でなければならないことを示しましょう。

\(x,y\)を\(ax+by=c\)を満たす整数と仮定します。\(d\)は最大公約数なので、\(a=d\ell\)、\(b=dm\)を満たす整数\(\ell ,m\)が存在します。すると、\(c=ax+by=d(x\ell+ym)\)で、\(x\ell+ym\)は整数です。よって、\(d \mid c\)が示せました。

少し長くなりましたが、簡単にまとめます。

そもそも1次不定方程式が解けるときは、右辺\(c\)が\(a,b\)の最大公約数の倍数となっていなければなりません。そうでないケースでは解が存在しません。このときは、互除法によっても当然解けません。

逆に、\(d \mid c\)のときは、互除法によって\(ax+by=c\)を満たす\(x,y\)を構成できることを確かめました。ポイントは、\(d=r_n =ax_n+by_n\)と表せることでした。最も簡単なケース\(n=1\)では、そもそも除法の原理は\(a=q_1b+d\)という形をしていて、これが1次不定方程式と見れます。そして等式の数が増える一般のケースでも、\(r_{k-1}=q_{k-1}r_{k}+r_{k+1}\)を使って、\(r_{k+1}\)を前の式と関連付けていくことで、\(a=q_1b+r_1\)まで戻ることができる。さらに余りには、\[ \begin{aligned}\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r_1)=\cdots \\= \mathrm{gcd}(r_{n-1},r_n)=\mathrm{gcd}(r_n,0)=r_n\end{aligned} \]という関係が成り立っているので（互除法の原理）、結局は常に\(a,b\)でまとめられる、というわけでした。

以上、1次不定方程式の整数解と、互除法による解き方、解ける条件を紹介してきました。

後半は少し難しかったかもしれませんが、1次不定方程式と互除法が密接な関係にある、ということを感じてもらえたら嬉しいです。

木村すらいむ（@kimu3_slime）でした。ではでは。