Webであなたの夢が叶う！のHirokoです。
Webで数学、
今回はユークリッドの互除法についてです。
前回、完全数をメルセンヌ数の結びつきを論じたのは、
紀元前3世紀の古代ギリシャの数学者：ユークリッドだと
お話ししました。
ユークリッドは、幾何学の父と呼ばれており、
古代ギリシャ数学を代表するユークリッド原論の
著者でもあります。
ユークリッド原論は、1巻から13巻まであり、
平面図形の性質、
面積、
円と多角形、
比例と図形、
数論、
無理量論、
立方体と体積、
多面体、
などから構成されており、
幾何学だけでなく多岐にわたっています。
この中に互除法という最大公約数の算出方法があります。
最大公約数とは
２つ以上の整数に共通する約数の中で最大のもの。
互除法の計算式は、
A ÷ B ＝ C・・・D
B ÷ D ＝ E・・・F
D ÷ F ＝ G・・・H
F ÷ H ＝ I・・・J
H ÷ J ＝ K・・・L
・
・
・
と計算していき、
・
・
J ÷ L ＝ M・・・N
L ÷ N ＝ O （←割り切れました！）
と必ず割り切れるときが出てきます。
この割り切れたときのNがAとBの最大公約数になります。
では、
数Aを１１８８、数Bを６３０としたとき
をみていきましょう！
１１８８ ÷ ６３０ ＝ １・・・５５８
６３０ ÷ ５５８ ＝ １・・・・７２
５５８ ÷ ７２ ＝ ７・・・・５４
７２ ÷ ５４ ＝ １・・・・１８
５４ ÷ １８ ＝ ３ （←割り切れました！）
数Aを１１８８と数Bを６３０の最大公約数は１８になります。
このように簡単に確実に最大公約数を算出する方法を
ユークリッドの互除法といいます。
二千年以上前にこのような解法があったとは愕きますね。
古代の数学者たちに敬意を表したいと思います。
