まず６４と７２の最大公約数を考えよう
引き算で出来る？
くま先生・・・まず、そうするとできることがあるっていう手頃な方法からしましょう。
７２－６４＝８
と引き算をして、公約数は最大公約数は８だ。
７２÷８＝９，６４÷８＝８で、どっちも８で割れるよね。
りす君・・・ え、引き算で最大公約数が計算できるんですか。
くま先生・・・手頃な方法って言ったでしょ。そういうこともあるということですね。
リス君・・・どうしてですか
ユークリッドの互除法
くま先生・・・ユークリッドの互除法っていう最大公約数の求め方があるのです。
AとBという数の最大公約数を求めるとき、最大公約数をZと考えてみます。
A÷B=CあまりDと なったとする。
つまり A=C×B＋D
左辺のAばZ(最大公約数）でわれるから、右辺のC×B＋DもZで割れるはずです。
ここでBはZでわれるから、C×BもZでわれる。
また、あまりのDもZで割れます。
そこで、あまりのＤとＢの最大公約数Ｚを求めればいいのです。
そこで、あまりのＤでＢを割って
Ｂ÷Ｄを計算する。
このあまりと、先ほどのあまりＤの最大公約数を探せばいい。
こうやって、数字をだんだん小さくして
あまりが0になったときの割る数が最大公約数なんだ。
（わかりにくい説明だ～～）
そこで、７２÷６４＝１・・・８
次に、６４÷８＝８ で割り切れたから８が最大公約数なんだ。
つまり、この場合は、７２－６４＝８って計算したのと同じでしょ。
これをちょっと応用すると・・・
割り算じゃなくて引き算して
出た数と、引いた数の最大公約数を求めれば、それが基の数の最大公約数になる。
数が小さくなるから楽でしょ・・・
この割り算を何回か行って最大公約数を求める方法は、パソコンのプログラムで使われる方法なんだ。
でも他の方法もあるのです。
次に、公約数が1つでも分かるとき、計算でするとどうなるの
公約数がわからなくても、見つけるには、ユークリッドの互除法を使うと良い。
もどる