- 63 名前：Kummer ◆g2BU0D6YN2 [2007/03/31(土) 09:55:20 ]
- Euclid の互除法は連分数と密接に関係する。
これを以下に説明する。
a と b を有理整数で a ＞ b ＞ 0 とする。
d = gcd(a, b) を Euclid の互除法によって求める場合を検討する。
x_0 = a
x_1 = b とおく。
k_0 = [a/b] とする。
[a/b] は a/b以下の最大の有理整数を表す(>>41)。
x_0 = k_0(x_1) + x_2 となる x_2 がある。
ここで 0 ≦ x_2 ＜ x_1
0 ＜ x_2 なら
k_1 = [x_1/x_2]
x_1 = k_1(x_2) + x_3 0 ≦ x_3 ＜ x_2
これを続けて
x_(n-1) = k_(n-1)x_n + x_(n+1)
x_n = k_n(x_(n+1)) で x_(n+2) = 0 とする。
d = x_(n+1) である。
