不定方程式 ax + by = (a, b) には整数解が存在します

n 元 1 次不定方程式の定義

 乗算表を用いれば 1 次合同方程式は簡単に解けますが、現実的には法が小さい場合にのみ有効な方法です。たとえば $\mathrm{mod}\;123$ の乗算表を作ろうと考える人はさすがにいないでしょう。そこで、これからしばらくは 1 次合同方程式
 
\[ax\equiv b\:(\mathrm{mod}\;m)\]
の一般的な解法を調べていくことにします。上式は
 
\[ax-b\:|\:m\]
を意味するので、整数 $y$ を導入すると
 
\[ax-b=my\quad\Longleftrightarrow\quad ax-my=b\]
と表せるので、1 次合同方程式とは 2 元 1 次不定方程式に他ならないということになります。まずは不定方程式の定義を載せておきます。

[定義 C5] $a_1,\:a_2,\:\cdots,\:k\:\in\mathbb{Z}$ を係数とする方程式
\[a_1\,x_1+a_2\,x_2+\:\cdots+a_n\,x_n=k\]を n 元 1 次不定方程式 といいます。

 ちなみに n 元 1 次不定方程式を英語で書くと linear indeterminate equation with n-unknowns です。または古代アレクサンドリアの数学者ディオファントスにちなんで ディオファントスの不定方程式 とよばれることもあります。
 

不定方程式 ax + by = (a, b)

 まず最初に次のような 2 元 1 次不定方程式
 
\[ax+by=g=(a,\:b)\]
を考えます。すなわち定数項が係数 $a,\:b$ の最大公約数となっているという極めて特殊な形の不定方程式ですが、この方程式には必ず整数解が存在するという定理が合同方程式を解くための重要な鍵となります。

[定理 C6] $g=(a,\:b)$ とすると、2 元 1 次不定方程式
\[ax+by=g\]を満たす整数 $x,\:y$ が必ず存在します。

[定理 C6 の証明]
 本講座の序盤で学んだ ユークリッドの互除法 を用いて証明します。
 $a=a_1,\:\:b=a_2$ とおくと、
 
\[\begin{align*}&a_1=a_2\,q_1+a_3\quad (0\leq a_3\lt a_2)\quad\quad (1)\\[6pt]
&a_2=a_3\,q_2+a_4\quad (0\leq a_4\lt a_3)\quad\quad (2)\\[6pt]
&a_3=a_4\,q_3+a_5\quad (0\leq a_5\lt a_4)\quad\quad (3)\\[6pt]
&\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\\[6pt]
&a_{n-1}=a_n\,q_{n-1}+a_{n+1}\quad (0\leq a_{n+1}\lt a_n)\\[6pt]
&a_n=a_{n+1}q_n\end{align*}\]
のように表せて、$a_{n+1}$ が $a_1$ と $a_2$ の最大公約数になります:
 
\[(a_1,\:a_2)=(a_2,\:a_3)=(a_3,\:a_4)=\:\cdots\:=(a_n,\:a_{n+1})=a_{n+1}\]
 すなわち $g=a_{n+1}$ となります。(1) より
 
\[a_3=a_1-a_2\,q_1\tag{4}\]
を (2) に代入すると
 
\[a_4=-a_1\,q_2+a_2\,(1+q_1\,q_2)\tag{5}\]
 (4) と (5) を (3) に代入すると
 
\[a_5=a_1\,(1+q_2\,q_3)-a_2\,(q_1+q_3+q_1\,q_2\,q_3)\]
となります。これを繰り返していけば、$a_{n+1}$ も $a_1$ と $a_2$ で表すことができます。すなわち
 
\[a_{n+1}=a_1\,x+a_2\,y\:\:(x\in\mathbb{Z},\:y\in\mathbb{Z})\]
 したがって $ax+by=c$ を満たす解が必ず存在します。(証明終)

 定理 C6 はいわゆる存在定理なのですが、その証明自体が具体的に解を求める手順になっています。この方法によって 1 組の解は求められますが、それを用いて不定方程式の一般的な解を得るためには以下の定理を用います。

[定理 C7] $g=(a,\:b),\:a=ga',\:b=gb'$ とすると
\[ax+by=g\] の一般解は 1 組の整数解 $x_0,\:y_0$ を用いて
\[x=x_0+b'k,\quad y=y_0-a'k,\:(k\in\mathbb{Z})\]で与えられます。

[定理 C7 の証明] $x_0,\:y_0$ は方程式の解なので、
 
\[\begin{align*}ax+by=g\\[6pt]
ax_0+by_0=g\end{align*}\]
が成り立ちます。両辺を差し引いて
 
\[a(x-x_0)+b(y-y_0)=0\]
 $a=ga',\:b=gb'$ を代入すると
 
\[a'(x-x_0)+b'(y-y_0)=0\]
 $(a',\:b')=1$ より、$b\:|\:x-x_0$ なので
 
\[\begin{align*}&x-x_0=b'k,\quad y-y_0=-a'k\\[6pt]
&\therefore x=x_0+b'k,\quad y=y_0-a'k\end{align*}\]
 ごく簡単な例をひとつだけ載せておきます。
 
\[35x+19y=1\]
 ユークリッドの互除法より
 
\[\begin{align*}35&=19\times 1+16\\[6pt]
19&=16\times 1+3\\[6pt]
16&=3\times 5+1\end{align*}\]
 つまり $35$ と $19$ は互いに素(最大公約数が $1$)となっています。
 $a=35,\:b=19$ とおいて上の式を書き直すと
 
\[\begin{align*}a&=b+16\quad\quad (1)\\[6pt]
b&=16+3\quad\quad (2)\\[6pt]16&=3\times 5+1\quad\quad (3)\end{align*}\]
 (1) より $16=a-b$ を (2) に代入すると
 
\[3=2b-a\quad\quad (4)\]
 16=a-b と (4) を (3) に代入して
 
\[6a-11b=1\]
 したがって
 
\[x_0=6,\quad y_0=-11\]
という 1 組の解が得られます。定理 C7 より一般解は
 
\[x=6+19k,\quad y=-11-35k\]
となります。
 

不定方程式 ax + by = c が解をもつ条件

 定理 C6 では右辺が $a,\:b$ の最大公約数のときに解をもつというものでしたが、この条件はもう少しだけ緩めることができます。

[定理 C8] 2 元 1 次不定方程式
\[ax+by=c\:(a,b,c\:\in\mathbb{Z})\]が整数解 $x,\:y$ をもつための必要十分条件は $(a,\;b)\:|\:c$ です。

[定理 C8 の証明]
 まずは必要条件を示します。
 $ax+by=c$ が整数解 $x,\:y$ をもつとき、$ax+by$ は整数となります。
 
\[(a,\;b)\:|\:a,\quad (a,\;b)\:|\:b\]
なので、定理 A3 より
 
\[(a,\;b)\:|\:ax+by\]
 すなわち $(a,\:b)\:|\:c$ となります。

 次は十分条件を示します。
 $(a,\:b)\:|\:c$ が成り立っているとき、$(a,\:b)=g$ とおくと定理 C6 より
 
\[ax'+by'=g\]
を満たす $x',\:y'$ が存在しています。また、$(a,\:b)\:|\:c$ なので $c=gc'$ となるような $c'$ も存在します。そこで上の式に $c'$ を掛けると
 
\[\begin{align*}ax'c'+by'c'=gc'\\[6pt]
a(c'x')+b(c'y')=c\end{align*}\]
となって、$x=c'x',\;y=c'y'$ という解が存在します。(証明終)

 ≫ 1 元 1 次合同方程式の解の個数 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください