// ユークリッド互除法は２つの整数の最大公約数を求めるアルゴリズムである．証明も含めて紹介する． 定理１： を整数，をで割った余りをとする．このとき$$\mathrm{gcd}(a,b) = \mathrm{gcd}(b, r)$$である． 証明： とする．定義よりを満たす整数が存在す…