一次不定方程式ax+by=cの３つの解法について

1. 一次不定方程式

今回は3つの方法を駆使して不定方程式を解きたいと思います。aとbは互いに素であるとします。

2. 解を一組見つける

2.1. 解を一組見つける考え方

仮に、不定方程式を満たす解を一組見つけたとします。その解の組をそれぞれ、$(x,y)=(x_{0},y_{0})$とすると、不定方程式を満たすから以下の式が成立する。

$ax_{0}+by_{0}=c$

$ax+by=c$から$ax_{0}+by_{0}=c$を引くと、

$a(x-x_{0})+b(y-y_{0})=0$

$\Leftrightarrow a(x-x_{0})=-b(y-y_{0})$

$a$と$b$は互いに素であるから、$x-x_{0}$は$b$の倍数であるため、整数$k$を用いると、

$x-x_{0}=-bk$

$\therefore x=-bk+x_{0}$

となる。$x$を$a(x-x_{0})=-b(y-y_{0})$に代入すると、

$a(-bk+x_{0}-x_{0})=-b(y-y_{0})$

両辺を-bで割ると、

$y-y_{0}=ak$

$y=ak+y_{0}$

となる。

2.2. 解の組を見つける例題

(1)$x=-1,y=1$は方程式の解であるから、

$12(x+1)=-13(y-1)$

となるから、整数$k$を用いて、$y-1$が$12$の倍数であるため、

$y-1=12k$

$y=12k+1$

$y$を$12(x+1)=-13(y-1)$に代入すると、

$x+1=-13k$

$x=-13k-1$

となる。

(2)(1)の結果を用いると、$12 \cdot (-1)+13\cdot 1 =1$であるから両辺を$5倍$すると

$12\cdot (-5)+13\cdot 5 = 5$

となるため、$x=-5,y=5$のときに不定方程式を満たす。

$12(x+5)=-13(y-5)$

となるため、整数$k$を用いて、$y-5$が$12$の倍数であるため、

$y-5=12k$

$y=12k+5$

$y$を$12(x+5)=-13(y-5)$に代入すると、

$x+5=-13k$

$x=-13k-5$

となる。

3. ユークリッドの互除法を用いる

3.1. ユークリッドの互除法がなぜ有効な手段なのか？

例えば、37と11をユークリッドの互除法を用いて最大公約数を求めてみたいと思います。

$37 = 11 \cdot 3 +4$

$11 = 4 \cdot 2 +3$

$4 = 3\cdot 1 +1$

とのように、ユークリッドの互除法を用いると、計算しなくてもわかると思いますが最大公約数が1となりました。ですが、$4 = 3\cdot 1 +1$この式が重要なのです。なぜなら、$4 = 3\cdot 1 +1$を移項すると、$4 – 3\cdot 1 =1$という形になり、$37 = 11 \cdot 3 +4$、$11 = 4 \cdot 2 +3$という式を用いて、$37x+11y=1$の解の一つを見つけることができるからです。以下にその過程を示します。

$4-3\cdot1 =1$

$11 = 4 \cdot 2 +3$であるから、$3=11-4\cdot2$となるため、

$4-1(11-4\cdot2)=1$

$4+4\cdot2-11=1$

$4\cdot3-11\cdot1=1$

$37 = 11 \cdot 3 +4$であるあから、$4=37-11\cdot3$となるため、

$3(37-11\cdot3)-11\cdot1=1$

$37\cdot3+11\cdot(-10)=1$

となり、$x=3,y=-10$という解を見つけることができる。

3.2. ユークリッドの互除法を用いた例題

57と34にユークリッドの互除法を用いると、

$57=34\cdot 1 +23$

$34 =23\cdot1 +11$

$23=11\cdot2+1$

となるから、

$23-11\cdot2=1$

$23-(34-23)2=1$

$23\cdot3-34\cdot2=1$

$(57-34)\cdot3-34\cdot2=1$

$57\cdot3-34\cdot5=1$

となる。$x_{0}=3,y_{0}=-5$を満たす。
したがって、$y=ak+y_{0}$、$x=-bk+x_{0}$となることを用いると、

$x=-34k+3$

$y=57k-5$

となる。

4. 合同式(mod)を用いる

4.1. 今までの解法との違いと考え方

合同式(mod)を用いると、解のペアを見つけるということを行わなくて済むというメリットがあります。以下に合同式(mod)を用いた解法を書きます。
$ax+by=c$に$a$を法とした合同式を用いると、

$by\equiv c \pmod{a}$

この形から、$y\equiv c’ \pmod{a}$という形に変形して、$y=ak+c’$と置いて、不定方程式に代入することでxを求める。$c’$と$c$は異なります。

ここで、合同式の次の性質を利用しています。

4.2. 合同式を用いた例題

11を法とする合同式を用いると、

$57x\equiv17\pmod{11}$

$2x\equiv6\pmod{11}$

11と2は互いに素であるから、

$x\equiv3\pmod{11}$

となるため、整数kを用いると、

$x=11k+3$

与えられた不定方程式にxを代入すると、

$57(11k+3)+11y=17$

$\therefore y=-57k-14$

となる。