こんにちは、本日は整数問題の中でも不定方程式について書いていこうと思います。不定方程式って何っていう人でもわかるように書くので安心して読んでくださいね！センター試験や二次試験で他の人と圧倒的にスピードの差をつける技術なので、ぜひ身につけてください。
今から説明する不定方程式の解き方は意外と参考書に載ってません。というか今から説明するのは記述式で解答に書く部分以外の話であるため、参考書にはあまり書かれていないのです。
不定方程式とは
まず不定方程式とは何かということですが、例を挙げると
$$不定方程式31x+126y=1(x,yは整数とする)を解け$$
通常2文字の方程式を解くためには２式必要です。そのためこの不定方程式は式の数が足りてないので解は無数に存在するはずです。
しかし\(x\)と\(y\)が整数であるという条件によって解は絞られるのでそれを求める問題です。
参考書に載っている不定方程式の解き方
もちろん教科書にも参考書にも不定方程式の解き方は載っています。その解き方をまずは説明します。
$$31x +126y=1\tag{1}$$
の整数解を１つ求めます。求めると\(x=-65,y=16\)となるので代入して
$$31×(-65)+126×16=1\tag{2}$$
ということになります。
両辺(1)の式から(2)の式を引くと
$$31(x+65)+126(y-16)=0$$
移項すると
$$31(x+65)=-126(y-16)$$
31と126は互いに素(最大公約数が1)なので
\(x+65=126k,y-16=-31k(kは整数)\)とおける。
よって\(x=126k-65,y=-31k+16(kは整数)\)が答えとなります。
解答には書かない部分の考え方
もちろん、記述式でのテストで上の解答を書ければ満点だ。実際私もこう書きます。しかし、今回説明したいのは上の解答で完全に省略してる部分についてなのです。すなわち実際に１つ整数解を求めてみるという部分についてです。
今回はこの部分を合同式を用いて求めてみようと思います。
合同式とは
合同式とは、ある数で割った場合のあまりを考えるときに使う考え方です。
例えば8かける13を3で割った余りを知りたいということを考えてほしい。もちろん8かける13を先計算して104だからそれを3で割ってみて2としてもいい。
しかし実はあまりを考える時にはあまりだけを考えてもいいというのが合同式の考え方なのだ。
つまり8を3で割ったあまりは2、13を3で割ったあまりは1であることから8かける13を3で割った余りは2かける1で求めることができるのです。
これを式で書くと
$$8\equiv2(mod3),13\equiv1(mod3)より8\times13\equiv2\times1=2(mod3)$$
合同式の式を書く時にはmodで何のあまりについて考えているのかを書いた上で、合同マークであまりが等しい数に変えていくことができます。
このようにある整数の余りを考える場合、かけ算や足し算や引き算の場合は余りだけで計算できます。ただし、割り算はできない点は注意しましょう。
割り算の場合は基本的には合同式を使わないことを推奨しますが、modの数字と割る数字が互いに素の場合は実は使うことができます。（ただし割ったときに整数になる場合に限ります）例えば、２と３は互いに素なので
$$8\equiv2(mod3)より8\div2\equiv2\div2=1(mod3)となります。$$
しかし、\(5\div2\)は整数にはならないので
$$5\equiv2(mod3)より5\div2\equiv2\div2=1(mod3)というのはおかしいです。$$
不定方程式に合同式を用いる方法
実は今説明した合同式を用いることで不定方程式の解を求めるスピードが格段に上がるのです。
$$31x +126y=1\tag{1}$$
もう一度この式に戻ります。この式の両辺は\(x,y\)が整数であることから両辺の３１で割ったあまりを考えることにします。
\(31x\)はもちろん３１の倍数ですのであまりは０です。さらにmod31の合同式を使って左辺のあまりを計算していきましょう。\(126\equiv2(mod31)\)より
$$31x +126y\equiv126y\equiv2y(mod31)$$となるのです。
\(31x +126y=1\)の両辺を３１で割ったあまりはもちろん等しいので、
\(2y\equiv1(mod31)\)ということになります。
この合同式の両辺を２で割りたいのですが、１は２で割れないので出来ません。
そこで右辺の１に３１ずつ足していって２で割り切れる数を見つけます。\(\equiv\)はあくまであまりが同じということを表しているだけなので、\(mod31\)の場合は\(1\equiv32\equiv63\)ということができるのです。
すなわち\(2y\equiv32(mod31)\)とも言えるわけです。
ここで３２を２で割ることが出来るようになりました。かつ２と３１は互いに素であるので、割り算の合同式を使うことができるので両辺を２で割って、
\(y\equiv16(mod31)\)となりました。この式の意味は\(y\)を３１で割ったあまりは１６だよっていうのを表しています。
その１つが\(y=16\)なので(1)の式に代入して\(x\)を求めると、\(x=-65\)となるのです。
後は上のやり方で不定方程式を解くことができます。
また、\(y\)を３１で割ったあまりは１６というのを式にすると
\(y=31k+16(kは整数\)なのでこれを(1)の式に代入することで\(x=-126k-65,y=31k+16(kは整数\)と不定方程式を最後まで解くこともできてしまうのです。
模範解答が合同式を使わない理由
ではなぜこのような楽な方法を参考書では使わないのかというと合同式の割り算については高校数学では使わないことになっているからです。そのため記述式のテストでは合同式で解答するのは避けたほうが無難です。
なので最初に１つ解を求める段階でのみ使うのがいいでしょう。
合同式を使った方がいい不定方程式とは
この合同式を用いて不定方程式を解く方法はいつでも使おうと思えば使えるのですが、\(x\),\(y\)の係数が共に小さい場合は何も考えずに数字を当てはめていっても探すことができるのでわざわざ使う必要はありません。少し\(x\),\(y\)の係数が大きいような時に用いるのがオススメです。
まとめ
不定方程式を合同式で解く方法はいかがだったでしょうか。
このように数学には解答には書かれていない部分をテクニックで簡単に解くという方法が色々あります。
そのような模範解答には載っていないところのテクニックや考え方をこれからも公開していければなと思っています。気になる方は、ブログの記事をあげる時にツイッターでお知らせしますので是非ツイッターフォローお願いします。
