2元1次不定方程式ax+by=cの整数解

こんにちはもちもちの実です！

今回は、2元1次不定方程式の整数解の求め方について解説していきます。

それでは本編へどうぞ！

1　整数解の存在条件

前提として、a,bは整数とします。このとき、

a,bは互いに素⇔ax+by=1を満たすx,yの整数解は存在

が成り立つ。証明が長いので、ここでは割愛させていただく。

また、ax+by=1の両辺をc倍すれば、

acx+bcy=c

X=cx,Y=cyとすれば、

aX+bY=c

となり、aX+bY=c型の連立方程式も整数解(cx,cy)を持つことが分かる。

2　解法の解説

それでは例題を踏まえながら、解法について説明しよう。

例題1)  7x+5y=1の整数解を求めよ。

例題1)  27x-40y=11の整数解を求めよ。

まず初めに、ax+by=c型の方程式は変数の個数(2つ)>式の個数(1つ)なので、答えは一つに絞ることはできない。このような方程式を、答えが一つに定まらないことから不定方程式と言う。

不定方程式の整数解を求めるには、まず一組の整数解(特殊解)を求める必要がある。

特殊解を求めるには、一苦労いるように思えるだろうが、次の事実を用いることで、割と簡単に求められる。

「0≦x≦bあるいは0≦y≦aの範囲で、必ず1解存在する。」

よって、a,bの値が小さい方を採用すればよい。

例えば、例題1だと、a=7,b=5より、x=0,1,2,3,4,5を代入していけばよい。

このようにして求まった特殊解(x,y)=(p,q)を用いて、解を求める。

元の式から,(x,y)=(p,q)を代入した式を引く。

(ax+by)-(ap+bq)=c-c

a(x-p)+b(y-q)=0

よって、

a(x-p)=-b(y-q)

したがって、x-p=-bk,y-q=ak(kは任意の整数)

ゆえに、x=-bk+p,y=ak+qが解(一般解)である。

以上を踏まえて、例題1,2を解いていく。

(1)   7x+5y=1の1組の特殊解は(x,y)=(3,-4)

　上記の手順の通りにやると、x=-5k+3,y=7k-4(kは任意の整数)

(2)　まず、27x-40y=11を求めたい。

　しかし、x,yの係数ともにおおきいため、探すのが困難である。

　だからまず今回は、27x-40y=1の特殊解を求める。

　すると、(x,y)=(3,2)が求まる。

　27・3-40・2=1に両辺11倍すると、　27・33-40・22=11

　よって、27x-40y=11の特殊解は(x,y)=(33,22)

　したがって、x=40k+33,y=27k+22(kは任意の整数)

いかがでしたでしょうか？

このような方程式は、共通テスト・入試でも頻出の内容です。

是非覚えておくようにしておきましょう！

それでは！