不定方程式 導入
\(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\)
これが求める一般解です。