最大公約因子

定義

$ a(x),b(x)\in F[x], \deg b(x)\gt0 に対して、

$ d(x)|a(x)と$ d(x)|b(x)を満たす最大次数の

モニック多項式$ d(x)\in F[x] を$ a(x)と$ b(x)の最大公約因子といい、

$ \gcd(a(x),b(x))と表記する

定理

$ a(x), b(x) \in F[x], \operatorname{deg} b(x)>0 に対して

$ \exists s(x), t(x) \in F[x] ; \operatorname{gcd}(a(x), b(x))=s(x) a(x)+t(x) b(x)

これも普通の最大公約数と同じ話mrsekut.icon

求める手順

普通にユークリッドの互除法でやっていけばいい

ただし、最終的にモニック多項式に変換する必要がある

例えば、

$ a(x)=x^{5}+x^{4}+x^{3}+x^{2}+1, b(x)=x^{4}+1 \in \mathbb{F}_{3}[x] に対して、ごにょごにょしていくと

最終的に$ r_2=2x^2+2x+1が得られるが、モニック多項式にするために$ 2^{-1}=2をかける必要がある

よって$ \gcd(a(x),b(x))=2^{-1}2_2=x^2+x+2になる