最大公約数（HCF）とは何か？

最大公約数（HCF）とは

最大公約数（Highest Common Factor、HCF）とは、2つ以上の整数に共通する正の約数のうち、最も大きいものです。

例えば、12 と 18 の最大公約数は 6 です。6 は 12 も 18 も余りなく割り切れる最大の正整数です。

ユークリッドの互除法は、2つの数の最大公約数を求める効率的な手法です。大きい方の数を小さい方で割り、余りを次の除数として繰り返します。最後に残る非零の余りが最大公約数になります。

例：12 と 18 の最大公約数を求める手順

最後の非零余りは 6 なので、最大公約数は 6 です。

各数を素因数の積に分解し、共通する素因数を最低の指数で掛け合わせると最大公約数が得られます。

例：12 と 18 の素因数分解

共通する素因数は 2 と 3 で、2×3 = 6 が最大公約数です。

2つの数の最小公倍数（Least Common Multiple、LCM）は、両方の数を割り切れる最小の正整数です。LCM は次の式で求められます。

LCM = （両数の積） ÷ 最大公約数

例：12 と 18 の LCM