第 $4$ 章 多 項 式 の 整 除
$\S\ 23.$ 多項式の最大公約数$\hspace{0.5mm}$，$\hspace{-0.5mm}$Euclid の法式
$\boldsymbol{1.}$ 一つの変数 $x$ の多項式が一次因数に分解されて\[a_0(x-\alpha)^a(x-\beta)^b\cdots(x-\lambda)^l\hspace{1cm}(\alpha\neq\beta\neq\cdots\neq\lambda)\]のような形に与えられているとすれば，多項式の整除または多項式の公約数などに関する問題ははなはだ簡明に解決される．$A$，$B$，$C$ などの文字は $x$ の多項式を表わすものとしていうのであるが，$A$ が $B$ で割り切れるために必要かつ十分な条件は，$B$ に含まれる一次因数が，その重複度数をも計算に入れて，ことごとく $A$ に含まれていることである．それが十分な条件であることは明白であるが，同時に必要な条件であることは，一次因数への分解の一意性からの帰結である．$A$ が $B$ で割り切れるとして，$A=BC$ とおけば，分解の一意性から，$A$ に含まれる一次因数は，$B$ と $C$ とに含まれる一次因数の全部であるから，$B$ に含まれる一次因数は $A$ に含まれる一次因数の一部でなければならない．また多項式 $A$，$B$，$C$ などの公約数はこれらの多項式に共通して含まれる一次因数のみを含むものである．特に最大公約数は共通の一次因数の全部の積である．もちろんここでも一次因数の重複度数を計算に入れていう．
$\boldsymbol{2.}$ 一次因数に分解された多項式の公約数を求めることは容易でも，多項式を一次因数に分解することは，実行上困難な問題である．しかるに多項式の最大公約数は有理的計算（四則）によって求めることができることは，著しい事実といわねばならない．この計算はいわゆる Euclid の互除法で，周知のことではあるが，念のためにここで一応説明しておくのである．
$f(x)$，$f_1(x)$ を与えられた多項式とするとき，$f$ を $f_1$ で割って整商を $q(x)$，剰余を $f_2(x)$ とすれば，$f_2$ は $f_1$ よりも低次である．次に $f_1$ を $f_2$ で割って整商を $q_1(x)$，剰余を $f_3(x)$ とすれば，$f_3$ は $f_2$ よりも低次である．このような操作を継続すれば，次々の剰余の次数がしだいに低下するから，いつか割り切れる場合に出会うに違いない．いま $f_{m-1}$ が $f_m$ で割り切れたとすれば，そこで演算が終局する．すなわち\[\left.\begin{alignat*}{1}f&=qf_1+f_2,\\[2mm]f_1&=q_1f_2+f_3,\\[2mm]{\small\cdots\cdots}&\hspace{0.1em}{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\\[2mm]f_{m-2}&=q_{m-2}f_{m-1}+f_m,\\[2mm]f_{m-1}&=q_{m-1}f_m.\end{alignat*}\hspace{2cm}\right\}\tag{$\ 1\ $}\] 上の第一の等式から $f_2=f-qf_1$．ゆえに $f$，$f_1$ の公約数は $f_2$ の約数，したがって $f_1$，$f_2$ の公約数である．同様に第二の等式から，$f_1$，$f_2$ の公約数は $f_2$，$f_3$ の公約数である．しだいにこのようにして $f$，$f_1$ の公約数は $f_{m-1}$，$f_m$ の公約数であるが，$f_{m-1}$ は $f_m$ で割り切れるから，$f_{m-1}$，$f_m$ の公約数はすなわち $f_m$ の約数にほかならない．ゆえに $f$，$f_1$ の公約数は $f_m$ の約数である．約数の中に，$f_m$ 自身をも含めていうのである．逆に $f_m$ の約数はもちろん $f_{m-1}$，$f_m$ の公約数，したがって $f_{m-2}=q_{m-2}f_{m-1}+f_m$ の約数，すなわち $f_{m-2}$，$f_{m-1}$ の公約数等等で，つまり $f$，$f_1$ の公約数である．
ゆえに $f_m$ は $f$，$f_1$ の公約数であって，かつ $f$，$f_1$ の公約数は $f_m$ の約数でなければならない．ゆえに $f_m$ は $f$，$f_1$ の公約数のうち，最高次のもので，かつ公約数中唯一の最高次のものである．もちろん定数因子は考えに入れないでいう．$f_m$ がすなわち $f$，$f_1$ の最大公約数である．上の説明において注意すべき要点は $f$，$f_1$ の公約数の中に $f_m$ のような特別のものがあって，それはすべての公約数で割り切れるというところにある．すべての公約数で割り切れるから，公約数の中で最高次であり，また定数因子をほかにしてただ一つである．すなわち最大公約数の特性は，すべての公約数を約数として含むような特別な公約数という点にある．それが公約数の中で最高次であるのは，いわば付帯的の条件にすぎないのである（最高次の公約数があることは初めから明白であるが，最高次の公約数がただ一つであることは，単に最高次であるということだけからは出て来ない）．
$\boldsymbol{3.}$ 上の Euclid の法式から，なお次の重要な定理が導かれる．$(\ 1\ )$ の第一の等式から\[f_2=f-qf_1.\] これを第二の等式の $f_2$ に代入すれば，\[f_3=f_1-q_1f_2=f_1-q_1(f-qf_1)=-q_1f+(qq_1+1)f_1.\] これを第三の等式の $f_3$ に代入すれば，\begin{alignat*}{1}f_4&=f_2-q_2f_3=(f-qf_1)-q_2(-q_1f+(qq_1+1)f_1)\\[2mm]&=(q_1q_2+1)f-(qq_1q_2+q+q_2)f_1.\end{alignat*} このようにして次々の剰余 $f_2$，$f_3$，$f_4$，$\cdots$ は，いずれも $Pf+Qf_1$ のような形に表わされる．$P$，$Q$ は $q$，$q_1$，$q_2$，$\cdots$ から加法，減法，乗法によって組み立てられる多項式である．このような計算を続行すれば，最後の剰余である最大公約数 $f_m$ もまた上の形に書き表わされるであろう．よって次の定理を得る．
〔定理 $\boldsymbol{4.\ 4}$〕 一つの変数の多項式 $f$，$f_1$ の最大公約数を $f_m$ とすれば，\[Pf+Qf_1=f_m\tag{$\ 2\ $}\]になるような多項式 $P$，$Q$ を求めることができる．
特に $f$，$f_1$ が互いに素であるとき（定数以外に公約数をもたないことをいう）は\[Pf+Qf_1=1\tag{$\ 3\ $}\]になるような多項式 $P$，$Q$ を求めることができる．
$f$ と $f_1$ とが互いに素であるときは，$f_m$ は定数である．それで $(\ 2\ )$ の $P$，$Q$ を割ったものを $P$，$Q$ に代用すれば，$(\ 3\ )$ を得る．
〔定理 $\boldsymbol{4.\ 5}$〕 $B$，$C$ が互いに素である多項式で，$AC$ が $B$ で割り切れるならば，$A$ が $B$ で割り切れる．
$A$，$B$，$C$ はいずれも一つの変数 $x$ の多項式である．
〔証〕 仮定によって $B$，$C$ は互いに素であるから，\[PB+QC=1\]になるような多項式 $P$，$Q$ が存在する．ゆえに\[PAB+QAC=A.\] 仮定によって，$AC$ は $B$ で割り切れ，また $PAB$ はもちろん $B$ で割り切れるから，$A$ が $B$ で割り切れる．
〔注意〕 多項式の因数分解を用いるならば，この定理は容易に証明されるのであるが，因数分解を用いないで，Euclid の法式を根拠として証明することが重要である．その理由は後に至って（$\S\ 25$）明らかになるであろう．
〔問題 $\boldsymbol{1}$〕 $A$，$B$ が互いに素である $x$ の多項式で，また $C$ は任意の多項式であるとき\[AU+BV=C\]になるような多項式 $U$，$V$ が求められる．その一組を $U_0$，$V_0$ とすれば，一般に\[U=U_0+BS,\hspace{1cm}V=V_0-AS.\]$S$ は任意の多項式である．
〔解〕 $P$，$Q$ を定理 $4.\ 4$ の多項式とする．すなわち $AP+BQ=1$．しからば $APC+BQC=C$．ゆえに $U=PC$，$V=QC$ が上の問題の一つの解である．ただし一般の解はこのように $C$ なる公約数をもつものではない．いま一組の解を $U_0$，$V_0$，任意の解を $U$，$V$ とすれば，\[AU+BV=AU_0+BV_0=C\]から\[A(U-U_0)=B(V_0-V).\] すなわち $A(U-U_0)$ は $B$ で割り切れる．しかも $A$ と $B$ とは互いに素であるから $U-U_0$ は $B$ で割り切れる（定理 $4.\ 5$）．よって $U-U_0=BS$ とおけば，$V_0-V=AS$，したがって $U=U_0+BS$，$V=V_0-AS$ でなければならない．逆に，このような $U$，$V$ が問題の解であることは明白である．
〔問題 $\boldsymbol{2}$〕 $A$，$B$，$C$ は $x$ の多項式で，公約数をもたないならば\[AU+BV+CW=1\]になるような多項式 $U$，$V$，$W$ が求められる．
〔解〕 $A$，$B$ の最大公約数を $M$ とすれば，$M$ と $C$ は互いに素である．いま $AP+BQ=M$，$MS+CT=1$ とすれば，\[A(PS)+B(QS)+CT=1.\] 〔注意〕 本節の定理は整数にもあてはまる．上の説明で，多項式とあるところを整数に代えて読み返すとよい．ただし多項式の低次というところは，整数の絶対値の小さいこととするのである．