二つ(以上)の整数の公約数のうちで最大のもの。

目次 特徴 計算

特徴

例えば、2と10の最大公約数は2である。

その計算方法は色々ある。最も単純な方法は、二つの整数AとBのそれぞれを素因数分解し、その共通項を見つける方法である。

例えば15と27の最大公約数は、15=3×5、27=3×9、であるので、答えは3である。しかしながら数が小さいうちは良いが、数が大きくなった場合は素因数分解は極めて難しくなるため、この方法は使えなくなる。

計算

効率的な方法として古くから使われているものにユークリッドの互除法がある。

コンピューターで最大公約数を算出する場合も、この方法が最も一般的と考えられる。

リンク

用語の所属
公約数
約数
関連する用語
ユークリッドの互除法
最小公倍数
素因数分解

[再検索] [戻る]