最大公約数

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

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

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

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

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