そしてとあるモニック多項式

多項式版の最大公約数

定義

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)

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

求める手順

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

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

例えば、

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になる