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) である。