[#アルゴリズム](アルゴリズム) - [[最大公約数]]([[GCD]])を求める アルゴリズム $\mathrm{gcd}(n, m)$を求めるには...($n \ge m$) 1. 以下の手順を$n, m$が割り切れるまで繰り返す - a. $n$を$m$で割ったあまり$r$を求める - $\mathrm{gcd}(n, m)と\mathrm{gcd}(m, r)$は等しい - $n = q \cdot m + r$, $r = n - q \cdot m$より - b. $n, m$を$m, r$で置き換える 2. 割り切れて、余り$r$が0になる - $\mathrm{gcd}(n, 0) = n$