【整数問題】不定方程式を瞬時に解く技術

2019年5月7日

こんにちは、本日は整数問題の中でも不定方程式について書いていこうと思います。不定方程式って何っていう人でもわかるように書くので安心して読んでくださいね!センター試験や二次試験で他の人と圧倒的にスピードの差をつける技術なので、ぜひ身につけてください。

令和医学
人と差がつくとこなので最後まで読んでね

今から説明する不定方程式の解き方は意外と参考書に載ってません。というか今から説明するのは記述式で解答に書く部分以外の話であるため、参考書にはあまり書かれていないのです。

不定方程式とは

まず不定方程式とは何かということですが、例を挙げると

$$不定方程式31x+126y=1(x,yは整数とする)を解け$$

通常2文字の方程式を解くためには2式必要です。そのためこの不定方程式は式の数が足りてないので解は無数に存在するはずです。

しかし\(x\)と\(y\)が整数であるという条件によって解は絞られるのでそれを求める問題です。

参考書に載っている不定方程式の解き方

もちろん教科書にも参考書にも不定方程式の解き方は載っています。その解き方をまずは説明します。

$$31x +126y=1\tag{1}$$

の整数解を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+65\)が126の倍数で、\(y-16\)が31の倍数ということだ

よって\(x=126k-65,y=-31k+16(kは整数)\)が答えとなります。

解答には書かない部分の考え方

もちろん、記述式でのテストで上の解答を書ければ満点だ。実際私もこう書きます。しかし、今回説明したいのは上の解答で完全に省略してる部分についてなのです。すなわち実際に1つ整数解を求めてみるという部分についてです。

今回はこの部分を合同式を用いて求めてみようと思います。

合同式とは

合同式とは、ある数で割った場合のあまりを考えるときに使う考え方です。

例えば8かける13を3で割った余りを知りたいということを考えてほしい。もちろん8かける13を先計算して104だからそれを3で割ってみて2としてもいい。

しかし実はあまりを考える時にはあまりだけを考えてもいいというのが合同式の考え方なのだ。

つまり8を3で割ったあまりは213を3で割ったあまりは1であることから8かける13を3で割った余りは2かける1で求めることができるのです。

これを式で書くと

$$8\equiv2(mod3),13\equiv1(mod3)より8\times13\equiv2\times1=2(mod3)$$

合同式の式を書く時にはmodで何のあまりについて考えているのかを書いた上で合同マークであまりが等しい数に変えていくことができます

令和医学
あまりだけ知りたい時にはすごい便利だよ

このようにある整数の余りを考える場合、かけ算や足し算や引き算の場合は余りだけで計算できます。ただし、割り算はできない点は注意しましょう。

割り算の場合は基本的には合同式を使わないことを推奨しますが、modの数字と割る数字が互いに素の場合は実は使うことができます。(ただし割ったときに整数になる場合に限ります)例えば、2と3は互いに素なので

$$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\)が整数であることから両辺の31で割ったあまりを考えることにします。

令和医学
\(x\),\(y\)の係数のうち小さい方の数字のあまりを考えよう

\(31x\)はもちろん31の倍数ですのであまりは0です。さらにmod31の合同式を使って左辺のあまりを計算していきましょう。\(126\equiv2(mod31)\)より

$$31x +126y\equiv126y\equiv2y(mod31)$$となるのです。

\(31x +126y=1\)の両辺を31で割ったあまりはもちろん等しいので、

\(2y\equiv1(mod31)\)ということになります。

この合同式の両辺を2で割りたいのですが、1は2で割れないので出来ません。

そこで右辺の1に31ずつ足していって2で割り切れる数を見つけます。\(\equiv\)はあくまであまりが同じということを表しているだけなので、\(mod31\)の場合は\(1\equiv32\equiv63\)ということができるのです。

すなわち\(2y\equiv32(mod31)\)とも言えるわけです。

ここで32を2で割ることが出来るようになりました。かつ2と31は互いに素であるので、割り算の合同式を使うことができるので両辺を2で割って、

\(y\equiv16(mod31)\)となりました。この式の意味は\(y\)を31で割ったあまりは16だよっていうのを表しています。

その1つが\(y=16\)なので(1)の式に代入して\(x\)を求めると、\(x=-65\)となるのです。

後は上のやり方で不定方程式を解くことができます。

また、\(y\)を31で割ったあまりは16というのを式にすると

\(y=31k+16(kは整数\)なのでこれを(1)の式に代入することで\(x=-126k-65,y=31k+16(kは整数\)と不定方程式を最後まで解くこともできてしまうのです。

模範解答が合同式を使わない理由

ではなぜこのような楽な方法を参考書では使わないのかというと合同式の割り算については高校数学では使わないことになっているからです。そのため記述式のテストでは合同式で解答するのは避けたほうが無難です

なので最初に1つ解を求める段階でのみ使うのがいいでしょう。

合同式を使った方がいい不定方程式とは

この合同式を用いて不定方程式を解く方法はいつでも使おうと思えば使えるのですが、\(x\),\(y\)の係数が共に小さい場合は何も考えずに数字を当てはめていっても探すことができるのでわざわざ使う必要はありません。少し\(x\),\(y\)の係数が大きいような時に用いるのがオススメです。

まとめ

不定方程式を合同式で解く方法はいかがだったでしょうか。

このように数学には解答には書かれていない部分をテクニックで簡単に解くという方法が色々あります。

そのような模範解答には載っていないところのテクニックや考え方をこれからも公開していければなと思っています。気になる方は、ブログの記事をあげる時にツイッターでお知らせしますので是非ツイッターフォローお願いします。

ツイッタをフォローする

 

  • この記事を書いた人

令和 医学

京大医学部の医学生。自らの受験経験と大手塾での講師と家庭教師の経験から医学部含む受験についての正しい情報を知ってもらいたいと思っている。特に数学が得意で偏差値は90越え。趣味は旅行。特にディズニーが大好き。

Copyright© 初心者医学生の雑記ブログ , 2020 All Rights Reserved Powered by AFFINGER5.