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) \) も互いに素になる。