2013年02月28日

【数A・新】ユークリッドの互除法

りんたろーさんから質問いただきました。
ありがとうございます。

=========================================
Q.
ユークリッドの互除法の意味を教えて下さい。
本当にお願いします。でもできたらでいいです。

=========================================

A.
ユークリッドの互除法は
2つの自然数の最大公約数を
求める方法です。

具体例で雰囲気を伝えるくらいでよければ
書いておきますので読んでみてください(^^)




例えば12と8の最大公約数を考えてみましょう。
12個の○と8個の○を考えます。

 ○○○○○○○○○○○○
 ○○○○○○○○

これらを「同じ個数の○のセットを作る」
というのが割り算の目的です。
例えば○を3個ずつのセットにしてみます。

 ○○○|○○○|○○○|○○○|
 ○○○|○○○|○○

12の方はちょうど4セット、
8の方は2セットと2個余ります。
余りがあるので8の方は3では割り切れない。
言い換えれば3は8の約数ではない
ということになります。
3は約数ではないということから
当然3は12と8の公約数ではない
というダメな例。


ちなみに今、
「何セットできるか」ということは
約数かどうかを考える上では全く関係なく
とにかく余りが出なければOKということも
大事なポイントなので覚えておいてください。


2個ずつのセットなら大丈夫ですよね?

 ○○|○○|○○|○○|○○|○○|
 ○○|○○|○○|○○|

というように12も8も2個ずつに
きっちり分けられるので
2は12と8の公約数ということになります。
でも最大公約数ではありません。

「最大」っていうくらいなので
なるべく多くの個数でセットを作りたい
という考えを取り込んで改めて考えましょう。





 ○○○○○○○○○○○○
 ○○○○○○○○

12と8で可能な限りの個数で
セットを作ろうと思ったら
12と8のうちの少ない方の
「8個」が最大個数になります。
そこで12も8も8個ずつの
セットに分けてみましょう。

 ○○○○○○○○|○○○○
 ○○○○○○○○|

8個の方はちょうど1セット。
12の方は1セットと4個余り。
ということで8は12と8の
最大公約数ではない。
もちろん公約数ですらありません。

ここで今描いた図に注目。
上の12も下の8も
「|」のところまでは割り切れています。
公約数を求めるならどちらも
割り切れなければいけません。
今、下の8は8で割り切れていますが
上の12は「|」よりも右側の部分が
8では割り切れていないので
公約数ではありません。

もし公約数で割るなら
上の12も下の8も割れます。
8を割り切ることができるなら
上の段でも「|」までは割りきれるので
そこよりも右側の4も
その数で割りきることができれば
12も8も割れることになります。

さらにこの
「右側の4が割れないと公約数ではない」
ということから
4より大きな数が公約数になることは
ありえないので
この段階で4より大きい公約数はなく
もちろん最大公約数も4よりは大きくない
ことが言えます。

そこで今度は
「|」までの8と
そこより右側の4との
最大公約数を考えることになります。

従って

 ○○○○○○○○
 ○○○○

この8と4を可能な限りの個数で
セットを作っていくことを
先ほどと同様に考えて行くことになります。
最大個数は4なので

 ○○○○|○○○○|
 ○○○○|

今度はどちらも割り切れました。
よって4が8と4の最大公約数であり、
同時に12と8の最大公約数でもある。


今言ったことを割り算の式と
図を一緒に書いてまとめにさせていただきます。


 12÷8=1...4
 ○○○○○○○○|○○○○
 ○○○○○○○○|

 8÷4=2...0
 ○○○○|○○○○|
 ○○○○|

よって12と8の最大公約数は4である。





この方法を使えば大きな数の最大公約数を
求めるスピードが格段にアップします。
この方法以外だと素因数分解して
共通因数を求める方法もありますが
そもそも大きな数を素因数分解するのは難しいですね。
2や3で割っていくことができればいいですが
「77441」を素因数分解するのは
手計算ではかなり時間がかかると思います。
なので

 77441 と 69223 の最大公約数

を求めるような場合はユークリッドの互除法を使いましょう。

77441÷69223=1...8218
69223÷8218=8...3479
8218÷3479=2...1260
3479÷1260=2...959
1260÷959=1...301
959÷301=3...56
301÷56=5...21
56÷21=2...14
21÷14=1...7
14÷7=2...0

よって最大公約数は7である。

ちなみに77441と69223をそれぞれ素因数分解すると
77441=7×13×23×37
69223=7×11×29×31
でした(^^)

ユークリッドの互除法は
「探す」手間が一切なく
「計算」するだけで
最大公約数が求まるのが特徴です。
posted by ジュンジ at 03:24 | Comment(2) | TrackBack(0) | 数学A