わたなべ学習塾 | 日記 | ユークリッドの互除法についての補足

今日は公式ブログにて、高校の数学の教科書に「ユークリッドの互除法」が
扱われていることに触れました。
ではその具体的な内容はどのようなものなのか。
それを簡単にこちらにまとめておこうと思います。

まず大雑把に言うと、ユークリッドの互除法とは
「二つの整数a,bの最大公約数を求める」ための、特別な計算の方法です。

その具体的な方法の根拠になるのが、次の定理。
（以下、二つの整数a,bの最大公約数を(a,b)と表すことにします）

定理
整数aをbで割ったときの余りをrとすると、(a,b)＝(r,b)となる。

これが意味するものは、a,bが大きな数だったとき、
最大公約数を求めることは非常に難しくなってきます。
しかし片方の整数をもう片方で割り、その余りとの最大公約数を考えることで、
対象になる整数をどんどんと小さくすることができるのです。

よってユークリッドの互除法とは、次のようなアルゴリズムになるのです。
１、aからbを引けるだけ引き算して、余る数を求める。
２、次にbから、１で求めた余りを引けるだけ引く。そして余る数を求める。
３、以下この余る数が０になるまで、１、２の計算を繰り返す。
４、余る数が０になったとき、そのときに引いていた数が最大公約数である。

さて、ここまで読むと、頭痛くなりますよね（笑）
そう、そこが問題なのです！

このことは高校の数学Aの教科書に載っていました。
そこで文理問わず、ほとんどの生徒が上に書いてあるようなことを勉強するのです。
増して、公式ブログに書いたように、このことを勉強したことが無い先生も、
存在するはずなのです。

そこで、この記事では、ユークリッドの互除法を理解してもらうつもりはありません。
ただこれが入ってくることの危うさを知っていただければと思うのです。
もちろん、これが入試問題に関係することになると・・・恐ろしいですね！

ちなみに少し発展内容。
ユークリッドの互除法は、倍数の関係をイデアルに直しても同じことができます。
つまり整数だけでなく、整式であっても使えるものなんです。
・・・だから、入試問題がどこまで踏み込むかが気になるんですね。

ということで結論！
今年３年生になった人は、２浪したら大変なことになります！
今年２年生になった人は、大学受験のときに浪人をすると大変なことになります！

ぜひ知っておかれて下さいね。

公式HP　→　ユークリッドの互除法