31x+22y=1に当てはまる整数x,yをどう求めるか | 一次不定方程式の特殊解

数学Aの教科書にある一次不定方程式の特殊解を求める方法について記事にしてみます。

数学A 改訂版 [104/数研/数A/327] 文部科学省検定済教科書

数学A 改訂版 [104/数研/数A/327] 文部科学省検定済教科書

 

該当するのは、上教科書内にある次のような問題。

 

等式\displaystyle 31x+22y=1 を満たす整数\displaystyle x,y の組を一つ求めよ。

(解(方法①))

31と22に互除法の計算を行うと、次のようになる。

 \displaystyle 31=22\cdot 1 +9 移項すると\displaystyle 9=31-22\cdot 1 …①

 \displaystyle 22=9\cdot 2 +4 移項すると\displaystyle 4=22-9\cdot 2 …②

 \displaystyle 9=4\cdot 2 +1 移項すると\displaystyle 1=9-4\cdot 2 …③

③、②、①を順に使って1を31の何倍かと22の何倍かで表すことを試みる。

\displaystyle 1=9-4\cdot 2 ←③より

 \displaystyle =9-(22-9\cdot 2)\cdot 2 ←②より

 \displaystyle =9+22\cdot (-2)+9\cdot 4

 \displaystyle =9\cdot 5 +22\cdot (-2)

 \displaystyle =(31-22\cdot 1)\cdot 5 +22\cdot (-2) ←①より

 \displaystyle =31\cdot 5 +22\cdot (-5)+22\cdot (-2)

 \displaystyle =31\cdot 5+22\cdot (-7)

すなわち

 \displaystyle 31\cdot 5+22\cdot (-7)=1

したがって、求める整数\displaystyle x,y の組の一つは

 \displaystyle x=5, y=-7

となる。(終)

 

数字に数字を入れる計算がやや難しいという方もいるかもしれません。

そのような場合には次のように\displaystyle  a=31, b=22 とし、割り算の各段階で余りを\displaystyle a,b で表す方法もあります。

(方法②)

 \displaystyle 31=22\cdot 1 +9

  移項すると\displaystyle 9=31-22\cdot 1 =a-b 

 \displaystyle 22=9\cdot 2 +4

  移項すると\displaystyle 4=22-9\cdot 2 =b-(a-b)\cdot 2=-2a+3b 

 \displaystyle 9=4\cdot 2 +1

  移項すると\displaystyle 1=9-4\cdot 2=(a-b)-(-2a+3b)\cdot 2=5a-7b

よって

 \displaystyle 31\cdot 5+22\cdot(-7)=1

となる。

 

1を\displaystyle a,b で表したいのだなという目的がはっきり見えやすいので最初の方法よりやりやすい…かも。

 

最後に、私が気に入っている方法を紹介します。この方法は数研出版の何かの問題集の解答に「こんな方法もある…」と遠慮気味に書いてあったものですが、もう少し胸を張っても良いスバラシイ方法だと思います。

 

(方法③)元の問題はそもそも、係数が大きいので当てはまる整数\displaystyle x,yが探しにくいのでした。係数が小さければ当てはまる数は割と簡単に見つかります。ということで係数が小さくなるように、大きい係数の中から小さい係数が何個とれるか、という工夫をします(要するに割り算をする)。

 \displaystyle 31x+22y=1

31は22が一つ分と残り9に分けられるので

 \displaystyle 22x+9x+22y=1

22でくくる。

 \displaystyle 22(x+y)+9x=1

ここで置き換え

 \displaystyle x+y=z …(A)

をすると

 \displaystyle 22z+9x=1

を得る。これでもパッとは当てはまる数は見つけにくいので、もう一度上と同様に割り算をしてみる。22の中に9は2個取れるので

 \displaystyle 9\cdot 2 z+4z+9x=1

9でくくって

 \displaystyle 9(2z+x)+4z=1

ここでまた置き換え

 \displaystyle 2z+x=w …(B)

を行うと

 \displaystyle 9w+4z=1

を得る。2係数がともに一桁ぐらいになればさすがに当てはまる数はわかる。\displaystyle w=1, z=-2 とすればよい。このあとは文字の置き換えを行なった(B), (A)の式から芋づる式に\displaystyle x,y がでてくる。

(B)より\displaystyle  2\cdot (-2)+x=1\displaystyle x=5 。また(Aより\displaystyle 5+y=-2 \displaystyle y=-7 である。

 

なお、教科書にある通り、特殊解が一つ求まれば一般解はほぼ形式的に求められます。元の方程式と解の入った式を並べ

 \displaystyle 31x+22y=1

 \displaystyle 31\cdot 5+22\cdot (-7)=1

上から下の式をひくと

 \displaystyle 31(x-5)=-22(y+7)…④

を得ます。31と22は互いに素なので\displaystyle x-5 は22の倍数、よって\displaystyle x-5=22k (\displaystyle k は整数)と表され、④とから\displaystyle y+7=-31k となります。したがって一般解は

 \displaystyle x=5+22k, y=-7-31k (\displaystyle k は整数)

となります。

 

(方法③)の使用上の注意点としては、当てはまる数を自力で求める際に、いろいろなパターンが発生しうるということです。上で

 \displaystyle 9w+4z=1

とした際に、\displaystyle w=-3, z=7としても間違いではないわけです。その場合には\displaystyle x=-17,y=24 となってこれは直前に求めた一般解で\displaystyle k=-1 とした場合に相当します。

 

(方法③)は割り算を少々援用しつつも最終的には人間の直感によって当てはまる数を探す方法をとっています。それに対して(方法①)、あるいは(方法②)のような純粋な互除法で求める場合には、当てはめるものを直感的に自力で見つける作業は不要で、定められた計算を手順通りこなすと必ず\displaystyle x,yが求められます(いわゆるアルゴリズム!)。手順通り計算すれば必ず答えが求められるというのはコンピュータでプログラムを組む際にメリットがありますよね。

 

高校教員の立場としては(方法③)でしばらく教えて、ある程度慣れてきたら(方法①)、あるいは(方法②)もあるんだよ〜という風に持って言った方がいいと思っております。

  

では今回はこの辺で。

 

(補足)

(方法③)では係数が小さくなって当てはまるものが見つかった場合にはそれらの数を代入して、\displaystyle x,y を求めています。当てはまるものを見つけるのをグッと我慢して割り算を続ければ、31と22のように互いに素な係数をもつ一次不定方程式の場合は最終的には係数が\displaystyle  1 になる場面が登場するので、そのときに係数が\displaystyle 1 の文字を1、もう一方の文字を0とおけば互除法で計算するときと同様に、当てはまるものを見つけようと探すことなく、”アルゴリズム的”に特殊解が求められます。上の例では

 \displaystyle 9w+4z=1

でもう一度割り算をして

 \displaystyle 4(2w+z)+w=1

となるので、\displaystyle w=1,2w+z=0として変数を置き換えた部分を辿っていけば\displaystyle x=5,y=-7 が”アルゴリズム的”に求まります。