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は任意の整数)
いかがでしたでしょうか?
このような方程式は、共通テスト・入試でも頻出の内容です。
是非覚えておくようにしておきましょう!
それでは!
この記事が気に入ったらサポートをしてみませんか?