最大公約数
最大公約数 (さいだいこうやくすう) とは、0 ではない二つの整数に共通する約数のうち最大のものをさす。GCD (Greatest Common Divisor) と省略されることが多い。二つの整数 a, b に対して、その最大公約数を gcd(a, b) と書く。例えば、gcd(3,18) = 3, gcd(49,91) = 7, gcd(-14,22) = 2 である。一方が 0 である場合、gcd(a, 0) = a として、最大公約数を決めることもできる。最大公約数が 1 であるとき、二つの整数は互いに素であるという。
最大公約数を求めるためには、ユークリッドの互除法を用いるのが便利である。
最小公倍数 LCM (Least Common Multiple) との間に、
- gcd(a, b) · lcm(a, b) = ab
