最大公約数(GCD)と最小公倍数(LCM)の基本概念
整数論において最も基本的かつ強力な2大指標が最大公約数(Greatest Common Divisor, GCD)と最小公倍数(Least Common Multiple, LCM)です。
- 最大公約数(GCD): 2つ以上の整数に共通する約数(公約数)の中で、最も大きい数値。分数の「約分」において一発で既約分数にする際に利用されます。
- 最小公倍数(LCM): 2つ以上の整数に共通する倍数(公倍数)の中で、最も小さい正の数値。分数の「通分」において共通分母を最小にする際に利用されます。
最速アルゴリズム:ユークリッドの互除法
2つの数が 1071 と 1029 のように桁数が大きい場合、素因数分解を行うのは大変です。そこで紀元前から受け継がれる世界最古のアルゴリズム「ユークリッドの互除法(Euclidean Algorithm)」を用います。
「2つの数 A と B の最大公約数は、B と “AをBで割った余りR” の最大公約数に等しい」という性質を利用し、余りが 0 になるまで割り算を繰り返すだけで、確実にGCDが導かれます。
GCDとLCMの美しい恒等式
正の整数 $a$ と $b$ の間には、常に次の絶対的な関係式が成り立ちます。
したがって、ユークリッドの互除法で最大公約数 $\gcd(a, b)$ を求めてしまえば、最小公倍数は $\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$ の割り算1回で瞬時に計算できるのです。