Euclid の互除法

1. 概要 本記事では，Euclid の互除法（Euclidean Algorithm）について解説します． Euclid の互除法は 2 つの整数の最大公約数（gcd）を求めるアルゴリズムとして有名です．しかし，その応用は最大公約数を求めることだけに留まりません． 特に Euclid の互…