多項式の最大公約数

因数分解を用いて2つの多項式の最大公約数を求めるには、まず2つの多項式を完全に因数分解します。次に、すべての共通因数を積みます。この段階では、必ずしも単項式になるとは限らないため、最後に定数を掛けて単項式にします。すべての共通因数を含み、かつ単項式であるため、これが2つの多項式の最大公約数となります。

^{例１ ：} x² + 7x + 6とx² − 5x − 6の最大公約数を求め^なさい。

したがって、それらの最大公約数はx + 1です。

多項式の因数分解は、特に次数が大きい場合、難しい場合があります。ユークリッドの互除法は、任意の2つの多項式に対して有効な方法です。これは、ユークリッド除法を繰り返し使用します。このアルゴリズムを2つの数に適用すると、各段階で数の大きさが減少します。多項式の場合、各段階で多項式の次数が減少します。必要に応じて1つの多項式に変換した最後の非ゼロの剰余が、 2つの多項式の最大公約数になります。

より具体的には、2 つの多項式a ( x )とb ( x )の最大公約数を求めるには、b ≠ 0 と仮定することができます(そうでない場合、最大公約数はa ( x )です)。 $${\displaystyle \deg(b(x))\leq \deg(a(x))\,.}$$

ユークリッド除法は、商であるq ( x )と剰余で あるr ( x )という2 つの多項式を与え、$${\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{かつ}}\quad \deg(r_{0}(x))<\deg(b(x))}$$

多項式g ( x )がa ( x )とb ( x )の両方を割り切るのは_、それがb ( x )とr0 ( x )の両方を割り切る場合のみである。したがって $${\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).}$$ 設定 $${\displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}$$ ユークリッド除法を繰り返すことで、新しい多項式q ₁ ( x ) 、r ₁ ( x ) 、a ₂ ( x ) 、b ₂ ( x )などを得ることができます。各段階で、 $${\displaystyle \deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),}$$ そのため、シーケンスは最終的に次の点に到達します。 $${\displaystyle b_{N}(x)=0}$$ そして、1つは最大公約数を持っています。 $${\displaystyle \gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.}$$

例：x² ⁺ 7x + 6とx² − ^5x − 6の最大公約数を求める：

12 x + 12は最後の非ゼロの剰余なので、元の多項式の最大公約数であり、単項式の最大公約数は x + 1です。

この例では、2番目のステップの前に12を因数分解することで分母の導入を避けることは難しくありません。これは擬似剰余数列を用いることで常に可能ですが、注意しないと計算中に非常に大きな整数が導入される可能性があります。そのため、コンピュータによる計算では、以下に説明する別のアルゴリズムが使用されます。

この方法は、計算中に現れる係数がゼロに等しいかどうかをテストできる場合にのみ有効です。したがって、実際には、係数は整数、有理数、有限体の要素であるか、または前述のいずれかの有限生成体拡張に属している必要があります。係数が、近似的にしかわからない実数を表す浮動小数点数である場合は、数値的に安定した結果を得るために最大公約数の次数を知っている必要があります。この場合、通常は特異値分解に基づく他の手法が使用されることがあります。

多項式のユークリッド除法は、最大公約数を計算するためのユークリッドの互除法で使用されており、整数のユークリッド除法と非常によく似ています。その存在は次の定理に基づいています。2 つの 1 変数多項式が与えられたとき、${\textstyle a}$そして${\displaystyle b\neq 0}$体上で定義される多項式は、2つ存在する。${\displaystyle q}$（商）と${\displaystyle r}$（残りの） $${\displaystyle a=bq+r}$$ そして $${\displaystyle \deg(r)<\deg(b),}$$ ここで「deg(...)」は次数を表し、零多項式の次数は負の値として定義されます。さらに、qとrはこれらの関係式によって一意に定義されます。

整数のユークリッド除法との違いは、整数の場合、次数が絶対値に置き換えられること、そして一意性を確保するためにはrが非負であると仮定する必要があることである。このような定理が存在する環は、ユークリッド整域と呼ばれる。

整数の場合と同様に、多項式のユークリッド除法は長除法アルゴリズムで計算できます。このアルゴリズムは通常、紙と鉛筆を使った計算用に提示されますが、以下のように形式化するとコンピュータでもうまく機能します（変数名は、紙と鉛筆を使った長除法の計算における紙の領域と正確に対応していることに注意してください）。以下の計算では、「deg」は引数の次数（慣例としてdeg(0) < 0）を表し、「lc」は先頭係数、つまり変数の最高次の係数を表します。

ユークリッド分割

入力: aとb ≠ 0 は変数xに関する 2 つの多項式です。 出力:商qと余りrです。

始める

q := 0 r := a d := deg( b ) c := lc( b ) while deg( r ) ≥ d do s := (lc( r )/ c ) ⋅ x deg( r )− d q := q + s r := r − sb end do return ( q , r )

終わり

このアルゴリズムの妥当性の証明は、「while」ループ全体を通して、a = bq + rであり、deg( r )が各反復ごとに減少する非負の整数であるという事実に基づいています。したがって、このアルゴリズムの妥当性の証明は、ユークリッド除法の妥当性も証明することになります。

整数に関しては、ユークリッド除法を用いることで、最大公約数を計算するためのユークリッドの互除法を定義することができる。

2つの多項式aとbから始めて、ユークリッドの互除法は、( a , b )のペアを( b , rem( a , b )) (ここで「rem( a , b )」は、前のセクションのアルゴリズムによって計算されたユークリッド除法の余りを表す)で再帰的に置き換え、 b = 0 になるまで続ける。最大公約数は、最後のゼロでない余りである。

ユークリッドの互除法は、再帰プログラミングのスタイルで次のように定式化できる。 $${\displaystyle \gcd(a,b):={\begin{cases}a&{\text{if }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{otherwise}}.\end{cases}}}$$

命令型プログラミングスタイルでは、同じアルゴリズムは、各中間剰余に名前を付けることで、次のようになります。

r ₀  := a r ₁  := b

for ( i  := 1; r _i ≤ 0; i  := i + 1) do

r i +1 := rem( r i −1 , r i )

end do

return r _{i -1}。

r _iの次数列は厳密に減少します。したがって、最大でdeg( b )ステップ後には、剰余r _kが得られます。( a , b )と( b , rem( a , b ))は同​​じ約数を持つため、共通約数の集合はユークリッドの互除法によって変更されず、したがってすべてのペア( r _i , r _{i +1} )は同じ共通約数の集合を持ちます。したがって、 aとbの共通約数はr _{k −1}と 0の共通約数です。したがって、 r _{k −1}はaとbの最大公約数です。これは、ユークリッドの互除法が最大公約数を計算することを証明するだけでなく、最大公約数が存在することも証明します。

ベズーの恒等式は、最大公約数に関連する定理であり、最初は整数に対して証明されましたが、すべての主イデアル整域に対して有効です。体上の一変数多項式の場合、次のように述べることができます。

gが 2 つの多項式aとbの最大公約数 (両方ともゼロではない) である場合、次 の 2 つの多項式uとvが存在する。

${\displaystyle au+bv=g}$ （ベズーの正体）

そして、u = 1、v = 0、またはu = 0、v = 1、または

$${\displaystyle \deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g).}$$

多項式の場合、この結果の興味深い点は、多項式uとvを計算する効率的なアルゴリズムが存在することです。このアルゴリズムは、ループの各反復で行われる計算がいくつか多い点でユークリッドの互除法とは異なります。そのため、拡張最大公約数アルゴリズムと呼ばれます。ユークリッドの互除法とのもう 1 つの違いは、余りだけでなく、ユークリッド除法の商 (「quo」と表記) も使用することです。このアルゴリズムは次のように動作します。

拡張GCDアルゴリズム

入力： a、 b、単変数多項式

出力：

gはaとb の最大公約数、u、vは上記の記述と同様、 a 1、b 1はa = g a 1 、 b = g b 1となる 。

始める

 ( r 0 , r 1 ) := ( a , b ) ( s 0 , s 1 ) := (1, 0) ( t 0 , t 1 ) := (0, 1) for ( i := 1; r i ≠ 0; i := i +1) do q := quo( r i −1 , r i ) r i +1 := r i −1 − qr i s i +1 := s i −1 − qs i t i +1 := t i −1 − qt i end do g := r i −1 u := s i −1 v := t i −1 a 1 := (−1) i −1 t i b 1 := (−1) i s i

終わり

アルゴリズムが出力仕様を満たすという証明は、すべてのiに対して次 の事実に基づいています。$${\displaystyle r_{i}=as_{i}+bt_{i}}$$$${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},}$$ 後者の等式は、 $${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.}$$次数に関する主張は、各反復において、 s _iとt _i の次数が最大でr _iの次数が減少するにつれて増加するという事実から導かれる。

このアルゴリズムの興味深い特徴は、ベズーの恒等式の係数が必要な場合、入力された多項式をそれらの最大公約数で割った商が無料で得られる点です。

単変数多項式の場合、最大公約数と終結式の間には強い相関関係があります。より正確には、2つの多項式PとQの終結式は、 PとQの係数の多項式関数であり、 PとQの最大公約数が定数でない場合のみ、その値はゼロになります。

部分終結式の理論は、この性質を一般化したもので、2 つの多項式の最大公約数を一般的に特徴付けることができ、終結式は 0 番目の部分終結式多項式です。^{[ 1 ]}

2つの多項式PとQのi番目の部分結果多項式S _i ( P , Q )は、次数が最大でiの多項式であり、その係数はPとQの係数の多項式関数であり、i番目の主部分結果係数s _i ( P , Q )はS _i ( P , Q )の次数iの係数である。PとQの最大公約数が次数dであるのは、次の場合に限る。 $${\displaystyle s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0,\ s_{d}(P,Q)\neq 0.}$$

この場合、S _d ( P , Q )はPとQの最大公約数であり、 $${\displaystyle S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.}$$

部分終結式多項式の各係数は、 PとQのシルベスター行列の小行列の行列式として定義されます。これは、部分終結式がうまく「特化」することを意味します。より正確には、部分終結式は任意の可換環R上の多項式に対して定義され、次の性質を持ちます。

φ をRから別の可換環Sへの環準同型とする。これは、RとS上の多項式環間の別の準同型 (これもφと表記) に拡張される。この とき、PとQ がRの係数を持つ一変数多項式で、$${\displaystyle \deg(P)=\deg(\varphi (P))}$$ そして $${\displaystyle \deg(Q)=\deg(\varphi (Q)),}$$すると、 φ ( P )とφ ( Q ) の副結果多項式と主副結果係数は、PとQのそれらをφで写像したものになります。

部分結果式には、整数係数を持つ2つの多項式の最大公約数をコンピュータ上で計算する上で不可欠な2つの重要な性質があります。第一に、行列式による定義により、アダマールの不等式を用いて最大公約数の係数の大きさを制限できます。第二に、この制限と優れた特殊化の性質により、モジュラー計算と中国剰余定理（下記参照）を用いて、整数係数を持つ2つの多項式の最大公約数を計算できます。

多項式p ∈ R [ X ]の内容は「cont( p )」と表記され、その係数の最大公約数である。多項式q ∈ F [ X ]は次のように書ける。 $${\displaystyle q={\frac {p}{c}}}$$ ここで、p ∈ R [ X ]およびc ∈ Rである。c には qの係数のすべての分母の倍数(例えばそれらの積)を取り、 p = cqとすれば十分である。qの内容は次のように定義される。 $${\displaystyle \operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.}$$ どちらの場合も、内容はRの単位を掛けた分まで定義されます。

R [ X ]またはF [ X ]における多項式の原始部分は次のように定義される。 $${\displaystyle \operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.}$$

どちらの場合も、それは R [ X ] の原始多項式であり、つまり1はその係数の最大公約数です。

したがって、 R [ X ]またはF [ X ]のすべての多項式は次のように因数分解できます。 $${\displaystyle p=\operatorname {cont} (p)\,\operatorname {primpart} (p),}$$ そしてこの因数分解は、内容にRの単位を掛け、原始部分にこの単位の逆数を掛けるという操作を除いて一意である。

ガウスの補題は、2つの原始多項式の積が原始多項式であることを意味する。したがって、 $${\displaystyle \operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)}$$ そして $${\displaystyle \operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).}$$

前節の関係式は、R [ X ]とF [ X ]における最大公約数の間に強い関係があることを示唆している。曖昧さを避けるため、以下では「 gcd 」という表記は、最大公約数が計算される環によって添え字付けされる。

q ₁とq _2がF [ X ]に属する場合、 $${\displaystyle \operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).}$$

p ₁とp _2がR [ X ]に属する場合、 $${\displaystyle \gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_{2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),}$$ そして $${\displaystyle \gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).}$$

したがって、多項式の最大公約数の計算は、本質的にはF [ X ]とR [ X ]上で同じ問題です。

有理数上の単変数多項式の場合、ユークリッドの互除法は最大公約数を計算するのに便利な方法だと考えられるかもしれません。しかし、この方法は多数の整数の分数を簡約する必要があり、結果として得られるアルゴリズムは効率的ではありません。このため、整数上の多項式のみを扱うようにユークリッドの互除法を修正する方法が考案されました。これらの方法は、分数を導入するユークリッド除法をいわゆる擬似除法に置き換え、ユークリッドの互除法の剰余列をいわゆる擬似剰余列に置き換えるものです（下記参照）。

前の節では、 R [ X ]の多項式の最大公約数は、RとF [ X ] の最大公約数から導き出せることを見てきました。証明を詳しく見てみると、R と F [ X ]に最大公約数が存在する場合、R [ X ]にも最大公約数が存在することを証明できることがわかります。特に、R に最大公約数が存在し、 X が 1 つの変数に還元される場合、R [ X ]にも最大公約数が存在することが証明されます(ユークリッドの互除法は F [ X ] に最大公約数が存在することを証明します)。

n変数の多項式は、 ( n -1 ) 変数の多項式の環上の単変数多項式とみなすことができます。したがって、変数の数に関する再帰により、Rに最大公約数が存在し計算できる場合、 R上のすべての多変数多項式環にも最大公約数が存在し計算できることがわかります。特に、Rが整数環または体である場合、 R [ x ₁ , ..., x _n ]に最大公約数が存在し、前述の内容はそれらを計算するアルゴリズムを提供します。

一意分解領域上の多項式環が一意分解領域でもあることの証明は同様ですが、アルゴリズムは提供されません。なぜなら、体上の一変数多項式を因数分解する一般的なアルゴリズムは存在しないからです（一変数多項式に対する因数分解アルゴリズムが存在しない体の例もあります）。

最も単純な（定義しやすい）剰余列は、常にα = 1とすることです。実際には、係数のサイズが入力多項式の次数とともに指数関数的に増加するため、これは興味深いものではありません。これは、前のセクションの例で明確に示されており、その場合の連続する擬似剰余は次のようになります。 $${\displaystyle -15\,X^{4}+3\,X^{2}-9,}$$$${\displaystyle 15795\,X^{2}+30375\,X-59535,}$$$${\displaystyle 1254542875143750\,X-1654608338437500,}$$$${\displaystyle 12593338795500743100931141992187500.}$$ アルゴリズムの各反復において、連続する剰余の係数の桁数は2倍以上に増加する。これは、自明な擬似剰余数列に典型的な挙動である。

原始擬似剰余数列は、αに分子の内容を取ることによって得られる。したがって、すべてのr _iは原始多項式である。

原始的な擬似剰余数列は、最小の係数を生成する擬似剰余数列です。しかし、 Zにおける多数の最大公約数を計算する必要があるため、特にZ自体が多項式環である場合、実用上は十分効率的ではありません。

前のセクションと同じ入力値で、その内容で除算した後の連続する剰余は次のようになります。 $${\displaystyle -5\,X^{4}+X^{2}-3,}$$$${\displaystyle 13\,X^{2}+25\,X-49,}$$$${\displaystyle 4663\,X-6150,}$$$${\displaystyle 1.}$$ 係数の小ささから、多数の整数の最大公約数と最大公約数による除算が計算されたという事実は隠されている。

部分終結式列は擬似剰余を用いて計算することもできます。その手順は、すべてのr _{i が}部分終結式多項式となるようにα を選択することです。驚くべきことに、 αの計算は非常に簡単です（下記参照）。一方、アルゴリズムの正当性の証明は困難です。なぜなら、連続する 2 つの剰余の次数の差に関するすべての可能性を考慮する必要があるからです。

部分結果列の係数は、原始擬似剰余列の係数と比べて著しく大きくなることは稀である。Z における最大公約数計算は不要であるため、擬似剰余を用いた部分結果列は最も効率的な計算方法となる。

前のセクションと同じ入力値を用いると、連続する剰余は次のようになります。 $${\displaystyle 15\,X^{4}-3\,X^{2}+9,}$$$${\displaystyle 65\,X^{2}+125\,X-245,}$$$${\displaystyle 9326\,X-12300,}$$$${\displaystyle 260708.}$$ 係数は妥当な大きさである。最大公約数（GCD）の計算は一切行わず、正確な除算のみで得られる。このため、このアルゴリズムは従来の擬似剰余数列を用いたアルゴリズムよりも効率的である。

擬似剰余を用いて部分結果列を計算するアルゴリズムを以下に示します。このアルゴリズムでは、入力( a , b )はZ [ X ]の多項式のペアです。r _iはZ [ X ]の連続する擬似剰余であり、変数iとd _iは非負の整数であり、ギリシャ文字はZの要素を表します。関数deg()と は、多項式の次数rem()とユークリッド除算の剰余を表します。このアルゴリズムでは、この剰余は常にZ [ X ]にあります。最後に、/ で表される除算は常に正確であり、その結果はZ [ X ]またはZのいずれかになります。

r ₀  := a r ₁  := b for ( i  := 1; r _i ≠ 0; i  := i +1) do

d i := deg( r i −1 ) − deg( r i ) γ i := lc( r i ) if i = 1 then β 1 := (−1) d 1 +1 ψ 1 := −1 else ψ i := (− γ i −1 ) d i −1 / ψ i −1 d i −1 −1 β i := − γ i −1 ψ i d i end if r i +1 := rem( γ i d i +1 r i −1 , r i ) / β i

終了

注：「lc」は主係数、つまり変数の次数が最も高い係数を表します。

このアルゴリズムは、最大公約数（最後の非ゼロr _i）だけでなく、すべての部分結果多項式も計算します。剰余r _iは(deg( r _{i −1} ) − 1)番目の部分結果多項式です。deg ( r _i ) < deg( r _{i −1} ) − 1 の場合、deg( r _i )番目の部分結果多項式はlc( r _i ) ^{deg( r _{i −1} )−deg( r _i )−1} r _iです。その他の部分結果多項式はすべてゼロです。

シュトゥルム数列と同じ性質を持つ数列を構築するために、擬似剰余を用いることができる。そのためには、シュトゥルム数列と同じ符号を持つように、連続する擬似剰余の符号を制御する必要がある。これは、以下のように修正された擬似剰余を定義することによって行うことができる。

もし${\displaystyle \deg(A)=a}$そして${\displaystyle \deg(B)=b}$また、a ≥ b の場合、 AをBで擬似除算したときの修正擬似剰余prem2( A , B )は次のようになります。 $${\displaystyle \operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{a-b+1}A,B),}$$ ここで、| lc( B ) |はBの最高次係数 ( X ^bの係数)の絶対値です。

入力多項式が整数係数の場合、これにより整数係数の多項式からなるシュトゥルム数列を取得できます。部分結果の擬似剰余数列も同様に変更することができ、その場合、剰余の符号は有理数上で計算された符号と一致します。

上記の部分結果擬似剰余数列を計算するアルゴリズムは、以下を使用すると誤った部分結果多項式を計算することに注意してください。${\displaystyle -\mathrm {prem2} (A,B)}$の代わりに${\displaystyle \operatorname {prem} (A,B)}$。