最大公約数・最小公倍数計算

最大公約数はすべての数を割り切る最大の数、最小公倍数はすべての数で割り切れる最小の数です。前者は分数の約分に、後者は通分のための共通の分母探しに使います。

仕組み

最大公約数はユークリッドの互除法で求めます。大きい方の数を、小さい方で割った余りに置き換え、どちらかが0になるまで繰り返します。2,000年以上前の方法ですが今でも最速で、12桁の数でもわずかな手順で済みます。

最小公倍数は積を最大公約数で割ったものですが、先に割ってから掛けます。先に掛けると、答えそのものよりずっと早くコンピュータの整数の範囲を超えてしまいます。割り算は常に割り切れるので、この順序にしても何も失いません。

3つ以上のリストは2つずつ順に処理します。どちらの演算も結合法則を満たすので、これで正しく求まります。a、b、cの最大公約数は、aと「bとcの最大公約数」の最大公約数です。

互いに素とはどういう意味ですか？

最大公約数が1であること、つまり1以外の共通の約数をもたないことです。素数である必要はありません。8と15は互いに素ですが、どちらも素数ではありません。

数の1つが0のときはどうなりますか？

0とnの最大公約数はnです。すべての数は0を割り切るからです。最小公倍数は0です。0の倍数は0しかないからです。どちらも特別扱いではなく、定義からそのまま導かれます。

符号は関係ありますか？

いいえ。どちらも正の数で示します。これが一般的な慣習で、−12と12はまったく同じ約数をもちます。