Math
ユークリッドの互除法
２つの自然数の最大公約数(GCD, Greatest Common Divisor)を求める手法。
$a = bq + r$（$a \geqq b$）において、「$a$と$b$の最大公約数」=「$b$と$r$の最大公約数」
という性質が成立するため、この性質を利用してあまりがゼロ(公約数)になるまで再帰的に演算をすれば２つの自然数の最大公約数を求めることができる。
２つの自然数の最大公約数(GCD, Greatest Common Divisor)を求める手法。
$a = bq + r$（$a \geqq b$）において、「$a$と$b$の最大公約数」=「$b$と$r$の最大公約数」
という性質が成立するため、この性質を利用してあまりがゼロ(公約数)になるまで再帰的に演算をすれば２つの自然数の最大公約数を求めることができる。