2元1次方程式の整数解

1.ユークリッドの互除法のイメージ

まず、おさらい

この原理のため、また $bとr$ に対して同じことを繰り返せば、

最終的に最大公約数が出てくるという訳だ。

 

実際に$377と221$を例に互除法を行っていきます。

$$\begin{eqnarray} 377 &=& 1 \cdot 221 + 156 \\ 221 &=& 1 \cdot 156 + 65 \\ 156 &=& 2 \cdot 65 + 26 \\ 65 &=& 2 \cdot 26 + 13 \\ 26 &=& 2 \cdot 13 \end{eqnarray}$$

よって、最大公約数が $13$ と求まりました。

この最大公約数が何故求まるのか分かりやすいように

$377と221$、それと余りを最大公約数() $13$ )の積で

表す。(補足：$377 = 29 \cdot 13 \quad ,\quad 221 = 17 \cdot 13$)

$$\begin{eqnarray} ( 29 \cdot 13 ) &=& 1 \cdot ( 17 \cdot 13 ) + ( 12 \cdot 13 ) \\ ( 17 \cdot 13 ) &=& 1 \cdot ( 12 \cdot 13 ) + ( 5 \cdot 13 ) \\ ( 12 \cdot 13 ) &=& 2 \cdot ( 5 \cdot 13 ) + ( 2 \cdot 13 ) \\ ( 5 \cdot 13 ) &=& 2 \cdot ( 2 \cdot 13 ) + ( 1 \cdot 13 ) \\ ( 2 \cdot 13 ) &=& 2 \cdot ( 1 \cdot 13 ) \end{eqnarray}$$

ここで色んな見方が出てくると思う。

① この計算は、ただ最大公約数という一つの単位で

　差し引きをしているだけのように見えるかもしれないし、

② 全ての式で割れる数(最大公約数)は蚊帳の外で、

　計算しているように見えるかもしれない。

$$\begin{eqnarray} 13( 29 &=& 1 \cdot 17 + 12) \\ 13( 17 &=& 1 \cdot 12 + 5) \\ 13( 12 &=& 2 \cdot 5 + 2 )\\ 13( 5 &=& 2 \cdot 2 + 1 ) \\ 13( 2 &=& 2 \cdot 1 ) \end{eqnarray}$$

 

そんな見方で見ていただけると良いです。

①のように、もし世界が100円玉のみで生活をしているなら、

何回も差し引きした最終結果は、10円や50円にならずに、

100円になるはずです。

$377と221$ の二つの数の世界では、その単位が最大公約数

$13$ というだけです。

その単位が最大公約数となる理由は②のような考えで、

互除法の原理から、全ての式の数字が最大公約数13でくくれるからです。

このイメージで互除法を行ってもらえると幸いです。

 

ここまで言いましたが、実は少し疑問が残る個所があります。

$377 = 29 \cdot 13 \quad ,\quad 221 = 17 \cdot 13$

なので、$29 と 17$ は互いに素なのですが、

その $29から17$ を引いた $12と17$ は互いに素になる

のかという疑問です。

つまり上の話で行けば、$29と17$の世界では単位が$1$(:最大公約数)

になるのかという事です。

 

下記の補足証明が必要です。

これは、このページの一番下で証明しているので、

見たい方は下にスクロールしてください。

2.最大公約数の性質

たとえば、

$377X + 221Y = 13$

を満たす整数 $X、Y$ が存在する。

という事である。

だが、

$377X + 221Y = 1$

は存在しない。右辺が最大公約数で割り切れないためです。

上の話で言えば、$377と277$ をいくら差し引きしようと

しても、最大公約数($13$)という単位が残ってしまうためである。

 

そのため以下も成り立つ。

つまり、

$377X + 221Y = 1$

だとか、

$377X + 221Y = 15$

とかは整数解 $X,Y$ は存在しないという事である。

 

3.1次不定方程式の解法 (=0)

$2x = -3y$

となる。$2xは3$の倍数でなければならないので。

$x = 3k \quad ( k \in \mathbb{Z} )$

となるので、

$y= -2k$

よって、整数解は

$(x,y) = (3k , -2k)$

となる。

 

$8x + 12y = 0 \quad \to \quad 4(2x + 3y) = 0$

よって、

$(x,y) = (3k , -2k) \quad (k \in \mathbb{N})$

 

4.1次不定方程式の解法 (=G)

まず、特殊解を求める。(整数解を一つだけ求める。)

$(x,y) = (2,-1)$

よって、

$(2x + 3y) + (2 \cdot 2 + 3 \cdot (-1)) = 0 + 1$

$(x,y) = (3k, -2k)$ の時、$2x + 3y = 0$

ゆえに、

$(2 \cdot 3k + 3 \cdot (-2k)) + (2 \cdot 2 + 3 \cdot (-1)) = 0 + 1$

$2 \cdot (3k + 2) + 3 \cdot (-2k-1) = 1$

∴ $(x,y) = (3k+2 , -2k -1 )$

 

$4(2x + 3y) = 4 \cdot 1$

∴ $(x,y) = (3k+2 , -2k -1 )$

 

$8と12$ の最大公約数は $4$ であるが、

右辺は $4$ で割れないので、整数解はない

 

5.1次不定方程式の解法 (=C)

まず、特殊解を求める。(整数解を一つだけ求める。)

右辺が3なので、例題1（=G）の特殊解の3倍となる。

$(x,y) = (6,-3)$

$2x’ + 3y’ = 0$

になる時の解が、

$(x’,y’) = (3k,-2k)$

よって、

$(x,y) = (3k+6 , -2k-3)$

 

$4(2x + 3y) = 4 \cdot 2$

まず、特殊解を求める。(整数解を一つだけ求める。)

右辺が$4\cdot 2$なので、例題1（=G）の特殊解の2倍となる。

$(x,y) = (4,-2)$

$2x’ + 3y’ = 0$

になる時の解が、

$(x’,y’) = (3k,-2k)$

よって、

$(x,y) = (3k+4 , -2k-2)$

 

補足

$bと(a – nb)$ の最大公約数を $g$ とすると、

$b=cg \quad , \quad a-nb = dg \quad (c,d \in \mathbb{Z} : c,dは整数という意味)$

二個目の式に、一個目の式を代入すると、

$a-n(cg) = dg \quad \to \quad a = (d+nc)g$

よって、$aとb$の公約数が$g$となるが、

$aとb$は互いに素なので、$g=1$ となる。

ゆえに、$bと(a-nb)$ も互いに素になる。