今回は、最大公約数を求める方法として、ユークリッドの互除法を紹介します。
たとえば、次のような問題を考えます。
最大公約数と聞くと、まず素因数分解を考える人が多いと思います。 しかし、8643や1591のように数が大きくなると、素因数分解で進めるのは少し面倒です。
そこで使えるのが、ユークリッドの互除法です。
最大公約数とは何か
最大公約数とは、2つの数をどちらも割り切ることができる数のうち、もっとも大きい数のことです。
たとえば、30と18の最大公約数を考えてみます。
- 30を割り切る数：1, 2, 3, 5, 6, 10, 15, 30
- 18を割り切る数：1, 2, 3, 6, 9, 18
共通している数は、1, 2, 3, 6です。 その中で一番大きい数は6なので、30と18の最大公約数は6です。
素因数分解で解けるが、大きい数だと面倒
小さい数なら、約数を書き出したり、素因数分解したりして最大公約数を求めることができます。
しかし、8643と1591のように数が大きくなると、素因数分解はかなり面倒です。
そこで、割り算の余りを使って最大公約数を求める方法があります。 それがユークリッドの互除法です。
ユークリッドの互除法は、長方形で考えるとわかりやすい
まずは、小さい数で考えてみます。
30と18の最大公約数を、図形的に考えます。
横が30、縦が18の長方形を考えます。
最大公約数は、この長方形を同じ大きさの正方形でぴったりしきつめるときの、一番大きい正方形の1辺だと考えることができます。
図形的なイメージ
最大公約数 ＝ 長方形をぴったりしきつめられる正方形のうち、最大の正方形の1辺
30×18の長方形を分割する
まず、30×18の長方形の中に、18×18の正方形を1個入れます。
すると、横に12だけ余ります。
これは、割り算で書くと次のようになります。
次に、余った12×18の長方形を考えます。
18の中に12が1個入り、6が余ります。
次に、12×6の長方形を考えます。
12の中に6が2個ぴったり入ります。
余りが0になったので、ここで終了です。
最後にぴったり入った正方形の1辺は6なので、30と18の最大公約数は6です。
割り算で見るとこうなる
さきほどの長方形の分割を、割り算だけで書くと次のようになります。
30 = 18 × 1 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0余りが0になったとき、直前に出てきた数が最大公約数です。
したがって、30と18の最大公約数は6です。
なぜ余りを使っても最大公約数が変わらないのか
ここが、ユークリッドの互除法の大事なところです。
30と18の最大公約数を考えるとき、
となります。
これは、30から18を1回引くと12が残るという意味です。
30と18をどちらも割り切る数は、30から18を引いた12も割り切ることができます。
つまり、30と18の最大公約数を求める問題は、18と12の最大公約数を求める問題に変えてもよいということです。
同じように、
なので、18と12の最大公約数を求める問題は、12と6の最大公約数を求める問題に変わります。
ポイント
大きい数を小さい数で割り、その余りを使って問題を小さくしていく。これがユークリッドの互除法です。
8643と1591の最大公約数を求める
では、最初の問題に戻ります。
8643と1591の最大公約数を求めます。
素因数分解でやろうとすると少し大変なので、ユークリッドの互除法を使います。
1回目：8643を1591で割る
余りは688です。
2回目：1591を688で割る
余りは215です。
3回目：688を215で割る
余りは43です。
4回目：215を43で割る
余りが0になりました。
余りが0になったとき、直前に出てきた数が最大公約数です。
計算の流れをまとめる
ユークリッドの互除法では、次のように割り算を連鎖させます。
8643 = 1591 × 5 + 688
1591 = 688 × 2 + 215
688 = 215 × 3 + 43
215 = 43 × 5 + 0最後に余りが0になったので、最大公約数は43です。
確認すると、
となり、たしかにどちらも43で割り切れます。
ユークリッドの互除法のポイント
ユークリッドの互除法のポイントは、次の3つです。
- 大きい数を小さい数で割る
- 出てきた余りで、もう一度割る
- 余りが0になったら、直前の割る数が最大公約数
図形的に言えば、長方形を正方形でどんどん切り分けていき、最後にぴったりしきつめられる正方形の1辺を探していることになります。
まとめ
最大公約数は、素因数分解で求めることもできます。
しかし、数が大きくなると素因数分解は大変です。 そのようなときに便利なのが、ユークリッドの互除法です。
ユークリッドの互除法は、単なる計算テクニックではありません。
長方形を同じ大きさの正方形でしきつめるときの、一番大きい正方形の1辺を探す方法として考えると、意味がわかりやすくなります。
8643 = 1591 × 5 + 688
1591 = 688 × 2 + 215
688 = 215 × 3 + 43
215 = 43 × 5 + 0したがって、8643と1591の最大公約数は、
とだ塾での数学学習について
とだ塾では、公式や解き方をただ暗記するのではなく、「なぜその方法で解けるのか」を大事にしています。
今回のユークリッドの互除法も、割り算の手順だけを覚えるのではなく、長方形の分割として理解しておくと、最大公約数の意味がかなり見えやすくなります。
数学が苦手な生徒ほど、いきなり計算だけで進めるより、図や具体例から入る方が理解しやすいことがあります。
神戸市須磨区・板宿駅近くで、数学の基礎から見直したい方は、とだ塾の学習相談をご利用ください。