多項式の拡張 Euclid の互除法

$K$ を体、$a, b \in K[x]$、$b \ne 0$、$\deg a > \deg b$ とする。$r_0 = a$、$r_1 = b$、$s_0 = 1$、$s_1 = 0$、$u_0 = 0$、$u_1 = 1$ とおき、$r_i \ne 0$ である限り、$r_{i-1}$ を $r_i$ で割った商を $q_i$ として

と定める。このとき、ある $N \ge 1$ で $r_{N+1} = 0$ となって手順は止まり、次が成り立つ。

1. $\deg r_0 > \deg r_1 > \cdots > \deg r_N$。
2. $s_ia + u_ib = r_i$（$0 \le i \le N+1$）。
3. $s_iu_{i+1} - s_{i+1}u_i = (-1)^i$（$0 \le i \le N$）。とくに $s_i$ と $u_i$ は定数でない共通因子をもたない。
4. $\deg u_i = \deg a - \deg r_{i-1}$（$1 \le i \le N+1$）。