Euclidの互除法〈龍孫江の環論道具箱〉

　前回は$${\mathbb{Z}}$$のイデアルの和の性質を観察し，

整数$${a, b > 1}$$の最大公約数を$${d}$$とするとき
$${ax + by = d}$$となる整数$${x, y}$$が存在する

を示しました．ただし，その証明は$${\mathbb{Z}}$$のイデアルの生成元に関する事実を利用したもので，$${x, y}$$をどう見つけるのかは別の問題でした．

　今回は，$${ax + by = d}$$をみたす$${x, y}$$を見つける方法としても有力なEuclidの互除法を紹介します．

https://youtu.be/F9sEi0MsKkg

定理（Euclidの互除法）

整数$${a, b > 1}$$の最大公約数$${d}$$は，次の手続きによって求められる：

1. $${r_0 := a}$$および$${r_1 := b}$$とおく；

2. $${r_n > 0}$$である限り，$${r_{n-1}}$$を$${r_n}$$で割った余りを$${r_{n+1}}$$と定める；

3. $${r_{n+1} = 0}$$となったとき，$${r_n = d}$$である．□

この手続きをEuclidの互除法と呼びます．