「倍数」、「公倍数」、「最小公倍数」
「約数」、「公約数」、「最大公約数」
これらは全て、小学校5年で履修する概念ですが、いざ説明してみると、高校生や大学生にも、なかなか難しい…。
それだけ、考え方が多岐に亘り、計算が煩雑な単元なのです。
本題では、その中でも特に多くの人々の頭を悩ませる「最大公約数」を、
大幅に手間を省いて求められる、「ユークリッドの互除法」をご紹介いたします！！
一般的な方法は、2つの数の「約数リスト」を作って、両方のリストにあるうちの最大の数を「最大公約数」としますね。
これでは、列挙し忘れた約数があったら「投了」ですね。
そのリスクも、この「ユークリッドの互除法」で、回避できるのです！！
「ユークリッドの互除法」を言葉でご説明致しますね。
自然数2個の最大公約数は、大きい方の数を小さい方の数で割って、
余りが生じる場合、小さい方の数と余りの最大公約数と一致し、
余りが生じない場合、小さい方の数自体が最大公約数となる。
…実際に、確かめてみましょう！！
証明の段階で、文字をずいぶんたくさん使ってしまいましたが、
まずは適当な2つの数の最大公約数をこの方法で求めてみて、
「約数リスト」を作る方法と比較して、その便利さを実感してみましょう！！
ちなみに、本題で最大公約数のことを「G.C.M.」と表記していますが、
これは「Greatest Common Measure」という英語の略であり、「G.C.D.」もしくは「G.C.F.」と表す場合もあるのです！！
ちなみに、最小公倍数は「L.C.M」(Least Common Multiple)と表記します。
ちょっとした雑学、失礼いたしました…。