前回の数学ネタから
随分と時間が空いてしまいました
『友愛数と循環数 数のおもしろさを味わう（３）』
では、始めましょう
50／100 は約分できて
1／２ になりますね
それは、
共通の約数として 50 があって
分子と分母を 50 で割れば OK
共通の約数のことを 公約数
その最大のものを 最大公約数
といいます
50 と 100 の最大公約数は 50
というわけです
これは簡単
では、
13081 と 5459
の最大公約数は？
日常生活で大きい２つの数の
最大公約数が知りたいことって
ありませんか？
あ、ありませんか。。
そうですよね
なくてもいいのです
一見しただけでは
出来なさそうに見えることが
出来てしまう、
というおもしろさを
味わうことが楽しいのです
この方法は
ユークリッドの互除法 とよばれます
とりあえず、
実際にやってみますね
やり方としましては
まず、大きい数を小さい数で割って
今度は、求まった余りで
小さい方（直前で割った数）を割る、
というのを繰り返します
具体的に計算してみましょう
まず、
大きい数を小さい数で割ります
13081 ÷ 5459 = 2 … 2163
今度は、
割った数（5459）を
余り（2163）で割ります
5459 ÷ 2163 = 2 … 1133
これを繰り返します
2163 ÷ 1133 = 1 … 1030
1133 ÷ 1030 = 1 … 103
1030 ÷ 103 = 10
割り切れました
このときの割った数が
実は、最大公約数なのです
この場合は 103 ですね
元の２つの数を
103 で割ってみましょう
13081 ÷ 103 = 127
5459 ÷ 103 = 53
２つの数とも
103 で割り切れましたね
割って求まった数は、いずれも素数
道理で検討がつきにくいわけです
最大公約数を GCM と言いますが
Greatest Common Measure
{ 13081, 5459 } の GCM は
{ 5459, 2163 } の GCM で、
{ 5459, 2163 } の GCM は
{ 2163, 1133 } の GCM で、
{ 2163, 1133 } の GCM は
{1133, 1030 } の GCM で
{1133, 1030 } の GCM は
{1030, 103 } の GCM
つまり、103 となります
なぜ
割る数 と 余り の GCM を
追いかけていけばいいのでしょうか？
証明は以下の通りです
２つの数 A と B があって
A の方が B よりも大きく
その最大公約数を D としましょう
A = D x a, B = D x b
A を B で割ったときの
商を E、余りをF とすると
A = B x E + F
よって、
F = A - B x E
= D (a - b x E )
A と B の最大公約数が D ですから
余りの F も D を約数に持つ
ということが分かります
次に、
最初の２つの数で小さい方 B と
余りの F の最大公約数を d とします
B と F は約数として
先ほどの D を持つので
D ≦ d
これを（１）式とします
最初の式に戻りまして
A = B x E + F
でしたから
B と F の最大公約数 d は
B = d x s
F = d x t
として
A = d x ( s x E + t )
ですから
A も d を約数として持つことが
分かります
最初の仮定で
A と B の最大公約数は D ですから
d ≦ D
これを（２）式とします
（１）式と（２）式から
d = D
となります
つまり、
２つの数の最大公約数は
その２つの数を割り算して
その余りで小さい方を割る
という計算を繰り返せば
最大公約数が残ることになるのです
数の面白さを味わうシリーズ
とりあえず、終わりとします
吉田武『はじめまして数学３』
などを参考にしました
※ 思うところがありまして
しばらく、お休みとさせて頂きます
また再開する予定ですので、
それまでは、以前のエントリーを
お楽しみいただけたらと嬉しいです
（おしまい）
文：生塩研一
お読みいただきまして、ありがとうございました。
コメントもお待ちしています。お気軽にどうぞ～！
応援してくださる方は、下のバナーをクリック
ランキングサイトが開いたらOK！
自然科学 ブログランキングへ
にほんブログ村
Facebook の「いいね！」も嬉しいです！
Twitterもやってます
