最大公約数
出典: フリー百科事典『ウィキペディア（Wikipedia）』
最大公約数（さいだいこうやくすう）とは、0 ではない複数の整数の公約数（共通の約数）のうち最大のものをさす。G.C.D. (Greatest Common Divisor)、G.C.M.(Greatest Common Measure)、もしくは G.C.F.(Greatest Common Factor) と省略されることが多い。二つの整数 a, b に対して、その最大公約数を gcd(a, b) と書く。例えば、gcd(3,18) = 3, gcd(49,91) = 7, gcd(-14,22) = 2 である。一方が 0 である場合、gcd(a, 0) = a として、最大公約数を決めることもできる。最大公約数が 1 であるとき、二つの整数は互いに素であるという。
最大公約数を求めるためには、ユークリッドの互除法を用いるのが便利である。
2数の場合に限り、最小公倍数 LCM (Least Common Multiple) との間に、
- gcd(a, b) · lcm(a, b) = ab
という関係がある。
二つの数に限らず、より多くの数の最大公約数を求めたい場合は、上記のgcd関数を入れ子にすればよい。
