不定方程式の特殊解を見つける!
松谷です。
土曜に質問を受けていて、整数問題のある解法について質問されたのですが、いつも別の方法で自分自身が解いていたこともあり、ちゃんとその場で説明できないものがありました。。。懺悔。。
ということで、まぁ、別に基本問題なんですが、説明しておきたいと思います。
上の例のような、ax+by=1の形の不定方程式は整数問題で、もっともよく出る問題の一つです。
特に、a,bが互いに素(最大公約数が1)の場合、必ず整数解が存在します。
その存在証明のひとつは、フェルマーの小定理を証明するときにも使った道具を使います。
すなわち、bに0からa-1までをそれぞれかけたもの(b×0,b×1,b×2,・・・,b×(a-1)のa個の数)はaで余った余りがすべて異なることを利用して(背理法によって示されます)、aの余りはa種類(0からa-1まで)あることから、必ず余りが1であるものも存在することが言え(鳩ノ巣原理といいます)、そこから、b×🔲=a×◯+1とおけるわけなので、a×(-◯)+b×🔲=1とすることで、一つ解が見つかります。
まぁでもそれが本題ではありません。
整数解は必ずあるなぁと思っても、かなり見つけにくい場合があるときにどうするかということです。
5x+7y=1なら皆さん余裕でしょう。
(上の議論から、どんなに思いつかなかったとしても、yに0、1、2、3、4までを順番に代入すれば機械的に求まります。x=3、y=-2の方が早く見つかるならばそれでいいです。)
しかし、19x+53y=1は?って言われたら、うってなりますし、
いやいや、なんとかなるでしょう、っていう人も、157x+63y=1は?とか、206x+85y=1は?と言われたら流石に厳しいと感じることでしょう。
ということで、これの見つけ方を二通り載せておきたいと思います。
別に、特殊な方法を載せているわけではないのですが、忘れてたなとか、知らなかったとかいうひとがいたら、覚えておいてください。
19x+53y=1を題材にやり方を載せておきました。
ただ、見ただけでは、きちんと再現することはできないと思いますので、きちんと慣れたいという人は、157x+63y=1と206x+85y=1もやっておいてくださいませ。
あと、一つ解が見つかってから、それを一般の話にもっていくやり方も学校の教科書などなんでも載ってますので怪しい人は確認しておいてくださいませ。
ではでは、ちょっと真面目な数学ネタでした。
そして、自分自身、謙虚に数学について精進したいなと思いました。上がりたい人がどこまでも上がれるようにするためにも。