不定方程式　導入

\(x,y\) に関する \(2\) 元 \(1\) 次方程式 \(ax+by=1\) の整数解を求めましょう。
ただし、\(a,b\) ともに整数であるとします。

具体例で考えましょう。
\(a=2,b=7\) のとき

\(2x+7y=1\)

未知数が \(x,y\) と \(2\) つあるのに、式が \(1\) つなので、この \(2\) 元 \(1\) 次方程式の解は、もちろん無限にあります。解が定まらないため、不定方程式とも呼ばれます。
この不定方程式の解の中で、\(x\) も \(y\) も整数となる解を求めます（これが整数解です）。

整数解ももちろん無限にあるのですが、とにかく \(1\) つ見つけましょうと言われれば、あてはめで探せばすぐに見つかりますね。

\(x=4,y=-1\) です。
\((x,y)=(4,-1)\) とも表記します。

不定方程式の解は、１つ見つかれば芋づる式

先の不定方程式

\(2x+7y=1\)

の整数解を、\((x,y)=(4,-1)\) をもとにすべて求めます。

仕組みは非常に簡単で、\(x\) は \(7\) ずつ、\(y\) は \(2\) ずつずらしていくのです。
\((x,y)=(4+7,-1-2)=(11,-3)\)
\((x,y)=(11+7,-3-2)=(18,-5)\)
と無限に続きます。

この \(7\) と \(2\) はどこからやってきたのかと言えば、不定方程式 \(2x+7y=1\) の \(x,y\) の係数からです。\(2x\) の項を増やした分と、\(7y\) の項の減らした分が等しくないといけません。
\(14\) ずつずらすことになりますから、\(x\) は \(7\) ずつ、\(y\) は \(2\) ずつずらします。

この \(x,y\) は、ともに等差数列であり、\(t\) を整数として、
\(x=7t+4\)
\(y=-2t-1\)
と表せます。

\(t=0\) のとき、\((x,y)=(4,-1)\)
\(t=1\) のとき、\((x,y)=(11,-3)\)
\(t=2\) のとき、\((x,y)=(18,-5)\)
とうまく表せていますね。
もちろん
\(t=-1\) のとき、\((x,y)=(-3,1)\)
のように \(t\) が負のときもＯＫです。

記述式答案としてまとめる

先ほど見た芋づる式に解を見つける方法ですが、記述式答案としてまとめるさいは、
以下のように書くのがスマートです。

\(2\cdot4+7(-1)=1\)

という解が見つかったら、もとの不定方程式と差をとります。

つまり、

\(2x+7y=1\)
\(2\cdot4+7(-1)=1\)

上式から下式を引くと

\(2(x-4)+7(y+1)=0\)
より
\(2(x-4)=-7(y+1)\)・・・（１）

\(2\) と \(7\) は互いに素なので、\((x-4)\) は \(7\) の倍数、\((y+1)\) は \(2\) の倍数であることがわかります。

\((x-4)\) は \(7\) の倍数であることは、整数 \(t\) を用いて

\(x-4=7t\)・・・（２）
と表せます。

（１）に代入すると、
\(2\cdot 7t=-7(y+1)\)
\(2t=-(y+1)\)

より、
\(y+1=-2t\)・・・（３）

したがって、（２）、（３）より
\(x=7t+4\)
\(y=-2t-1\)
これが一般解となります。

整数解がない場合もある

不定方程式には解が無限にある、と見てきましたが、そもそも解が \(1\) つもないケースもあります。

例えば
\(4x-2y=1\)

この式を満たす解は無限にありますが、整数解は \(1\) つもありません。
\(x,y\) ともに整数ならば、左辺は常に偶数であり、決して右辺の \(1\) と等しくなりません。

どのようなときに不定方程式は整数解を持つのか。次のことが成り立ちます。

\(ax+by=1\) が整数解をもつ　⇔　\(a,b\) は互いに素

なぜこれが成り立つのか、については直接は書きませんが、次の「ユークリッドの互除法による不定方程式の解法」からおよそ雰囲気はわかることでしょう。

とりあえず上の事実を丸暗記しておきましょう。

ユークリッドの互除法による不定方程式の解法

先ほどの例では、とりあえず解を \(1\) つ見つけることが容易でした。

では次の例ではどうでしょう。

\(145x+67y=1\)

この不定方程式の整数解を求めましょう。
まず \(1\) つ解が見つかれば良いのですが、なかなか苦しいですね。

このようなときは、ユークリッドの互除法による手順が確立されています。

何はともあれその手順を見せると

\(145÷67=2\) あまり \(11\)
\(67÷11=6\) あまり \(1\)
次に \(11÷1=11\) あまり \(0\) で、 \(145\) と \(67\) の最大公約数が \(1\) であると求まるのがユークリッドの互除法ですが、今回は不定方程式を解くのが目的でしたね。

あまりが \(1\) になったところで、この操作を逆にたどります。
まず、ユークリッドの互除法の際に行ったわり算を、書き直します。

\(145÷67=2\) あまり \(11\) \(\Rightarrow\) \(11=145-67×2\)・・・（１）
\(67÷11=6\) あまり \(1\) \(\Rightarrow\) \(1=67-11×6\)・・・（２）

このように、
「あまり\(=\)」 の式になおします。

さて、（２）の式です。
\(1=67-11×6\)・・・（２）

左辺の \(1\) を \(145\) と \(67\) を組みあわせて作りたいのですが・・・
(１)式を使えば可能ですね。

\(67-\)\(11\)\(×6=1\)
この \(11\) は、\(145\) と \(67\) を用いて表せます。

\(67-\)\((145－67×2)\)\(×6=1\)

つまり、

\(67-(145×6-67×12)=1\)
\(67×13-145×6=1\)
これこそが、\(145x+67y=1\) の整数解の一つです。
\(x=-6\)
\(y=13\)
が見つかりました。
あとは芋づる式にわかりますね。

\(t\) を整数として
\(x=67t-6\)
\(y=-145t+13\)
これが一般解です。

例題１

不定方程式 \(43x+19y=1\) の整数解を求めなさい。

解説

直感的に解が \(1\) つ見つかればそれで良いのですが・・・
あてはめで探してすぐに見つかればそれで良いのですが・・・

すぐに見つからなそうなら、ユークリッドの互除法ですね。

\(43÷19=2\) あまり \(5\)
\(19÷5=3\) あまり \(4\)
\(5÷4=1\) あまり \(1\)

あまりが \(1\) になりました。
上の \(3\) つの式を、「あまり\(=\)」 の式になおします。
\(43÷19=2\) あまり \(5\) \(\Rightarrow\) \(5=43-19×2\)
\(19÷5=3\) あまり \(4\) \(\Rightarrow\) \(4=19-5×3\)
\(5÷4=1\) あまり \(1\) \(\Rightarrow\) \(1=5-4×1\)

さて、主役は \(43\) と \(19\) です。
あまりとして出た \(4\) や \(5\) を代入していけばＯＫです。

\(1=5-4×1\) の \(4\) に \(4=19-5×3\) を代入します。

\(1=5-(19-5×3)×1\)
整理すると
\(1=5×4-19×1\)

次にこの \(5\) に \(5=43-19×2\) を代入します。

\(1=(43-19×2)×4-19×1\)
整理すると
\(1=43×4-19×9\)

より、
\(x=4\)
\(y=-9\)
が求まりました！

解が \(1\) つ見つかればあとはわかりますね。
\(x\) は \(y\) の係数 \(19\) ずつ、\(y\) は \(x\) の係数 \(43\) ずつずらします。
\(x\) は \(19\) 足せば、\(y\) は \(43\) 減らします。

よって、\(t\) を整数として、
\(x=19t+4\)
\(y=-43t-9\)
これが求める一般解です。

参考・記述答案用の式処理

\(43x+19y=1\)
\(43×4+19×(-9)=1\)

上から下を引くと
\(43(x-4)+19(y+9)=0\)
\(43(x-4)=-19(y+9)\)・・・（１）

\(43\) と \(19\) は互いに素なので、\(x-4\)は \(19\) の倍数。
これは \(t\) を整数として
\(x-4=19t\) と表せる。

これを（１）に代入すると、
\(43\cdot19t=-19(y+9)\)
\(43t=-(y+9)\)
\(y=-43t-9\)

よって、\(t\) を整数として、
\(x=19t+4\)
\(y=-43t-9\)
これが求める一般解です。