2.2.4 多項式のユークリッドの互除法

多項式の最大公約式についても整数の最大公約数と同様の公式が成り立ちます。本講でも $\mathbb{Q},\mathbb{R}$又は $\mathbb{C}$のいずれかを $\mathrm{K}$と記載します。（体であれば常に成り立ちます。）

命題 2.2.14
$\mathrm{K}$係数多項式 $f(\mathrm{X}),g(\mathrm{X})$に対して、最大公約式の集合を$(f,g)$とすると、
（1） $(f,g)=(g,f)$
（2） $\mathrm{K}$の元$k$に対し、 $(f,g)=(kf,g)$
（3） $(f,0)=\{kf \vert k\in \mathrm{K}\}$
（4） 多項式 $q(\mathrm{X})\in \mathrm{K}[\mathrm{X}]$に対し、 $(f,g)=(f,g-qf)$

証明 (1)
(2)(3)は定義より明らか。
(4)は、$d$を$f,g$の公約式とすると、多項式$f_1,g_1$が存在して $f=df_1,g=dg_1$となる。すると、 $g-qf=d(g_1-qf_1)$であるため$d$は$f,g-qf$の公約式となる。
同様に$f,g-qf$の公約式は$f,g$の公約式でことがいえる。
$f,g$の公約式の集合と、$f,g-qf$の公約式の集合が等しいことがいえたため、最大公約式の集合も等しいことがいえた。

この命題と多項式における除法の原理を用いることにより、最大公約式を求める方法をユークリッドの互除法といいます。除法の原理により次数を下げることができ、最終的には0との最大公約式まで還元できます。それにより、次の最大公約式の存在定理が証明できます。

定理 2.2.15
$\mathrm{K}=\mathbb{Q},\mathbb{R},\mathbb{C}$とし、 $f,g\in \mathrm{K}[\mathrm{X}]$とすると、$f$と$g$の最大公約式は必ず存在する。
$d$を$f,g$の最大公約式とすると、$f,g$の最大公約式は、 $kd, k\in \mathrm{K}$の形である。

証明
$f,g$のいずれも0でないとする。このとき、 $\deg(f)\geqq\deg(g)$と仮定できる。除法の原理により $f=qg+r,\deg(g)>\deg(r)$とでき、 $(f,g)=(g,r)$である。つまり、最大公約式を保ったまま2つの式のうち次数を高い方の多項式の次数を下げることができる。$g,r$の一方が0でない場合は同様の操作を繰返す。これにより、片方を0にすることができる。このとき、残ったもう一方を$d$とおくと、 $(f,g)=(d,0)$である。
一方、上記の定理より$(d,0)$は、$d$の定数倍からなる集合である。