いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

2元1次不定方程式の特殊解を求める、分かりやすい方法

 互除法を用いて2元1次不定方程式の特殊解を求める方法、わかりにくい気がします。簡単な工夫で理解しやすくなるので、紹介しましょう。その前にまず互除法についてざっと復習しておきます。

 互除法とは……例えば240と66の最大公約数(以下、最大公約数を(240,66)と表すことにします)を求めるとき

24066・3+42

と割り算をして、(24066)=(6642)(240と66の最大公約数は66と42の最大公約数に等しい)と計算すればよい、という方法でした。これは繰り返せます。

66=42・1+24

 なので、(66,24)=(42,24)です。つまり(240,66)=(66,24)=(42,24)です。相手にする数はあっという間に小さくなり、何回かこの計算を繰り返せば最大公約数はすぐに求まります。素晴らしい方法です。

 さて、本題。今 36x+25y=1 の特殊解(方程式を満たす具体的な例)を見つけたいとしましょう。係数の36と25に対して、最大公約数を求めるつもりで互除法を実行します。

36=25・1+11

25=11・2+3

11=3  ・3+2

3 =2   ・1+1

もとの方程式で36=a、25=bとおいてみると、上の計算は次のようになります。

a=b・1+11

b=11・2+3

11=3  ・3+2

3  =2  ・1+1

第1式から「余り=」という式を導きます。11=a-b なので、これを第2式以降の太字の11に一斉に代入します。

a       =b          ・1+11

b       =(a-b)・2+3

a-b=3           ・3+2

3         =2           ・1+1

 第2式から「余り=」という式を導きます。3=3b-2a なので、これを第3式以降の太字の3に一斉に代入します。

a             =b              ・1+11

b             =(a-b)     ・2+3

a-b      =(3b-2a)・3+2

3b-2a  =2                ・1+1

第3式から「余り=」という式を導きます。2=7a-9bなので、第4式の太字の2にこれを代入して次を得ます。

-9a+13b=1

a,bを元に戻しましょう。

-9・36+13・25=1

これは最初の不定方程式の特殊解(のうちのひとつ)がx=-9,y=13であることを示しています。

  最初にa,bを使わないと、あちこちから出てくるいろんな数値が混ざってしまって何をどこへ代入したらよいか分からなくなってしまうんですね。注意してやればよいのでしょうが、そんなことに気をつかうのはバカバカしいことです。今回紹介したのは大学で学ぶ代数学でも使える方法です。整式を相手に同じことをするのです。