西川一誠後援会サイト

イッセイエッセイ詳細

イッセイエッセイ

1127号 ニ元一次の不定方程式の整数解を求める(互除法) 92x+197y=1の整数解xとy(その1)

2016年03月19日(土)

 ことしのセンター試験に「互除法」を使う問題が出た。この週末から二次試験の発表もはじまる。互除法は教科書には解説のある分野であるが、教科書を教えるだけでは残念ながら今回の問題はやや手をやく傾向のものである。教え方を改善しなければならない。
 以下、先生や若い人たちと話し会いながら整理した点を記す。

q1.大きな二つの数の最大公約数のさがし方(「互除法」によるやり方)

1.最大公約数を知りたい二つの大きな数について、より「大きい方」の数を「小さい方」の数(割る方の数)で割り、余りを出す。
2.次にさらに前の式で「割る方の数」つまり「小さい方」だった数を、「余りの数」で割る。以下同様に、割っては余りを出す計算を繰り返す。
3.余りがちょうど0になったとき、そのときの「割る方の数」が二つの数の最大公約数となる。

【例題】221と323の最大公約数を求めてみよう(22と32の最大公約数なら直観で解けるのだが)。
 (第一段階)「大きい方」の数を、「小さい方」の数で割り、商と余りを出す。
   323÷221=1 余り 102 ⇔   323=221×1+102 …(1)
 (第二段階)前の式の「割る数」を「余りの数」で割る。
   221÷102=2 余り  17 ⇔   221=102×2+ 17 …(2)
 (第三段階)余りが0になるまで、上記の操作を繰り返す。
   1つ前の式の「割る数」を「余りの数」で割る、という操作を繰り返す。
   102÷ 17=6 余り  
0 ⇔   102= 17×6+  0 …(3)
 余りが0になったとき、この(3)式の「割る数」に当る数が、323と221の最大公約数となる。この例題では、17が最大公約数になる。
 つまり、aとbの最大公約数(GCM)を[a,b]で表すと、[323,221]=[221,102]=[102,17]=17となる。
 なおこの場合に(2)式の段階で、余りの17が素数であるということがわかれば、(3)まで行かなくて(2)の段階で、その数17が最大公約数である、としてもよい。
 なお余談だが、(2)式の段階においてもし17に相当する余りの数が、1となるような二つの数字の組合せの場合であれば、最大公約数を求める二つの数は、互いに素(1以外の公約数をもたない)ということを示していることになる。

(解説)互除法によって最大公約数が見つけられる数式的な理由づけは、以下のとおりである。
 二つの整数をA、Bとし、(A>Bとする)、A-B=Rとおくと、AとBの最大公約数がB、Rの最大公約数でもあることを証明すればよい。
 その理由は、A、Bの最大公約数をGとすると、A=A’×G、B=B’×Gである。
 よってR=(A-B)=(A’×G)-(B’×G)=(A’-B’)×Gとなり、RもGという約数をもつはずになる。
 このような数字の関係を用いて、A、Bの替わりにB、Rを考え、順次に最大公約数をもつ数字の、常により小さな数字の組合せを作ることにより、最後には最大公約数に至ることができる。

q2.なぜ「互除法」によって最大公約数を発見できるのかの図形的証明。

 「ユークリッド互除法」の計算の意味を、図を描きながら幾何学的に考えてみる。
 ここでは前の例と同じ「221と323」で考える。
 これを式で求めると
           商  余り
   323 ÷ 221 = 1・・・102  …①
   221 ÷ 102 = 2・・・ 17  …②
   102 ÷  17 = 6・・・  0  …③
 答えが17になるこの計算を、次のような長方形を使って考えてみる。

 221と323の最大公約数を求めるというのは、「二つの大小のある長辺と短辺をもつ長方形の中に、最も辺の長い大きな正方形をぴったり埋めようとしたとき、その最大の正方形の一辺はいくらになるか」という問題に置き換えられる。なぜなら、タテとヨコの大きさが違う長方形に並べてぴったりはまる最大の一辺の長さをもつ正方形は、タテとヨコにそれぞれ割り切れて並べることができるのであるからその1辺の長さこそ、求める最大公約数となるからである。
 ①の計算は、まずこの長方形の中に「最も大きな正方形をつくってみる」ことを示している。これを図で表すと次の通りである。

 上の図で示しているように、「最も大きな」正方形の一辺はこの長方形の短辺、すなわち221になる。よって①の式「323 ÷ 221 = 1・・・102」は、「この長方形には一辺の長さが221の正方形が1つだけ入り、縦221、横102の長方形が残る」ことを示していることになる。よって221を一辺とする正方形はまだ該当する最大の正方形ではなく(大きすぎる)、もっと小さい正方形がおそらくありうるだろうと予測される。つまり、221はまだ最大公約数ではないことを意味する。
 同様に②の計算は、「①の計算で余った縦221、横102の長方形の中に入る最も大きな正方形をつくってみる」ことを示している。これを図で表すと次の通りである。

 上の図で示しているように、「最も大きな」正方形の一辺は残った長方形の短辺すなわち102であるから、②の式「221 ÷ 102 = 2・・・17」は、「この長方形には一辺の長さが102の正方形が2つ入り、さらに縦17、横102の長方形が残る」ことを示している。
 ③の計算も同様に、「②の計算で余った縦17、横102の長方形の中に最も大きな正方形をつくってみる」ことを示している。これを図で表すと次の通りである。

 上の図で示しているように、「最も大きな」正方形の一辺はこの長方形の短辺、すなわち17になるので、③の式「102 ÷ 17 = 6」はちょうど割り切れ、「この長方形には一辺の長さが17の正方形がすき間なく6つ入る」ことを示している。
 このことから、最初の縦221、横323の長方形を最も大きな正方形でぴったり埋めるとき、そのときの正方形の一辺は17である、すなわち221と323の最大公約数は17であることが分かる。
 なおこの長方形の場合においても、タテとヨコの長さの双方の数が互いに素、つまり最大公約数が1ならば、原単位が1の正方形が、最大の正方形(しかし実際は最小の1という公約数)になる。つまりタテ221ヨコ323の長方形に1(㎝)四方の方眼線をひいたのと同じ意味になり、これは必ず存在する。

(2016.2.28~3.18 記)