0-5 多項式の除法とBézout恒等式
読み始める前の問い
数の最大公約数と同じように、多項式にも「最大公約多項式」があり、割り算を繰り返して求められるだろうか。
このページでできるようになること
多項式の除法、因数定理、最大公約多項式、Bézout恒等式、根の重複度を、本書後半で自由に使えるようになる。
固有多項式、最小多項式、Cayley–Hamilton定理、一般固有空間分解では、多項式を行列へ代入します。特に「互いに素な多項式なら1をその線形結合で表せる」というBézout恒等式が、空間を固有値ごとに分解する鍵になります。そこで必要な多項式論をここで準備します。
多項式と次数
体 $K$ 上の一変数多項式とは
$$
f(t)=a_0+a_1t+\cdots+a_nt^n
$$
の形の形式的な式で、係数 $a_0,\ldots,a_n$ は $K$ の元である。すべての多項式の集合を $K[t]$ と書く。
$f\ne0$ のとき、$a_n\ne0$ となる最大の $n$ を $f$ の次数といい $\deg f=n$ と書く。零多項式の次数は通常の整数としては定めない。
多項式は関数として評価できますが、本書では係数列をもつ代数的対象として扱います。有限体上では異なる多項式が同じ関数を定める場合があるからです。たとえば $\mathbb{F}_2$ 上では $t^2$ と $t$ は $0,1$ のどちらを代入しても同じ値になりますが、多項式としては異なります。
零でない多項式 $f,g\in K[t]$ について
$$
\deg(fg)=\deg f+\deg g
$$
が成り立つ。
$\deg f=m$、$\deg g=n$ とし、最高次係数をそれぞれ $a_m\ne0$、$b_n\ne0$ とする。積 $fg$ の $t^{m+n}$ の係数は $a_mb_n$ である。$K$ は体なので零因子をもたず、$a_mb_n\ne0$ である。一方、$m+n$ より高い次数の項は積から生じない。したがって $\deg(fg)=m+n$ である。
多項式の除法
体 $K$ 上の多項式 $f,g\in K[t]$ について、$g\ne0$ とする。このとき
$$
f=qg+r,
\qquad
r=0\ \text{または}\ \deg r<\deg g
$$
を満たす多項式 $q,r\in K[t]$ がただ一組存在する。
証明の見取り図
存在は、$f$ の最高次項を $g$ の適当な倍で一つずつ消すことで次数を下げます。一意性は、二つの表示の差を取り、積の次数が小さくなれないことを使います。
まず存在を $\deg f$ に関する帰納法で示す。$f=0$ または $\deg f<\deg g$ なら、$q=0,r=f$ と取ればよい。
$\deg f=m\ge n=\deg g$ とする。$f$ と $g$ の最高次係数をそれぞれ $a,b$ とする。$b\ne0$ で $K$ は体だから $b^{-1}$ が存在する。そこで
$$
f_1:=f-ab^{-1}t^{m-n}g
$$
と置く。第二項の最高次項は $at^m$ なので、$f$ の最高次項と打ち消し合い、$f_1=0$ または $\deg f_1< m$ となる。
帰納法の仮定により
$$
f_1=q_1g+r,
\qquad
r=0\ \text{または}\ \deg r< n
$$
と書ける。したがって
$$
f=\left(q_1+ab^{-1}t^{m-n}\right)g+r
$$
となり、存在が示された。
次に一意性を示す。二組の表示
$$
f=qg+r=q'g+r'
$$
が条件を満たすとする。差を取ると
$$
(q-q')g=r'-r.
$$
$q-q'\ne0$ なら、積の次数の命題から左辺の次数は少なくとも $\deg g$ である。一方、右辺は零であるか、次数が $\deg g$ 未満である。これは矛盾する。よって $q=q'$ であり、続いて $r=r'$ である。
具体計算
$f(t)=t^3-2t+4$ を $g(t)=t-2$ で割ります。
$$
\begin{aligned}
t^3-2t+4
&=t^2(t-2)+(2t^2-2t+4)\\
&=t^2(t-2)+2t(t-2)+(2t+4)\\
&=(t^2+2t+2)(t-2)+8.
\end{aligned}
$$
したがって商は $t^2+2t+2$、余りは8です。検算として右辺を展開すると
$$
(t^2+2t+2)(t-2)+8=t^3-2t+4
$$
に戻ります。
根と因数
$f\in K[t]$ と $a\in K$ に対し、$f$ を $t-a$ で割った余りは $f(a)$ である。したがって
$$
f(a)=0
\quad\Longleftrightarrow\quad
t-a\text{ が }f\text{ を割り切る}.
$$
除法算法により
$$
f(t)=q(t)(t-a)+r
$$
と一意に書ける。余り $r$ は零または次数0なので、$K$ の元とみなせる。$t=a$ を代入すると
$$
f(a)=q(a)(a-a)+r=r.
$$
よって余りは $f(a)$ である。特に $f(a)=0$ であることと余りが零であること、すなわち $t-a$ が $f$ を割り切ることは同値である。
$f\ne0$ とし、$a\in K$ を $f$ の根とする。$(t-a)^m$ が $f$ を割り切る最大の正整数 $m$ を、根 $a$ の根の重複度|重複度という。$m=1$ の根を単根、$m\ge2$ の根を重根という。
たとえば
$$
f(t)=(t-1)^3(t+2)
$$
では、$1$ は重複度3、$-2$ は重複度1の根です。後に、固有多項式における根の重複度を固有値の代数的重複度と呼びます。
最大公約多項式とEuclidの互除法
$f,g\in K[t]$ が同時に零でないとする。多項式 $d$ が $f,g$ の最大公約多項式であるとは、
- $d$ が $f$ と $g$ の両方を割り切る。
- $f$ と $g$ の任意の公約多項式が $d$ を割り切る。
- $d$ の最高次係数が1である。
ことをいう。$\gcd(f,g)=1$ のとき、$f$ と $g$ は互いに素であるという。
最高次係数を1とする条件は、非零定数倍の曖昧さを除くためです。
$f,g\in K[t]$ が同時に零でないとき、最大公約多項式 $d$ が存在し、ある $a,b\in K[t]$ により
$$
d=af+bg
$$
と表される。特に $f,g$ が互いに素なら
$$
1=af+bg
$$
となる $a,b\in K[t]$ が存在する。
証明の見取り図
$af+bg$ と表される零でない多項式のうち次数最小のものを選びます。それで $f,g$ を割った余りも同じ形になるため、最小性から余りは零になります。
集合
$$
I:=\{af+bg\mid a,b\in K[t]\}
$$
を考える。$f$ と $g$ は同時に零でないので、$I$ は零でない多項式を含む。その中から次数が最小の多項式 $d_0$ を選び、最高次係数で割って最高次係数1の多項式 $d$ にする。$d$ も $I$ に属するので、ある $a,b$ により $d=af+bg$ と書ける。
$f$ を $d$ で割り、
$$
f=qd+r,
\qquad
r=0\ \text{または}\ \deg r<\deg d
$$
とする。このとき
$$
r=f-qd=f-q(af+bg)=(1-qa)f+(-qb)g
$$
だから $r\in I$ である。もし $r\ne0$ なら、$d$ より次数の小さい零でない元が $I$ に存在し、$d$ の選び方に反する。したがって $r=0$ で、$d$ は $f$ を割り切る。同じ議論で $d$ は $g$ も割り切る。
次に $c$ を $f,g$ の任意の公約多項式とする。$c$ は $f$ と $g$ を割り切るので、それらの多項式係数線形結合 $af+bg=d$ も割り切る。よって $d$ は最大公約多項式の条件を満たす。
最後に一意性を示す。$d'$ も最高次係数1の最大公約多項式なら、最大性から $d\mid d'$ かつ $d'\mid d$ である。積の次数から両者の次数は等しく、商は非零定数である。双方の最高次係数が1なので商は1、したがって $d=d'$ である。
計算例：拡張Euclid互除法
$$
f=t^3-1,
\qquad
g=t^2-1
$$
とします。割り算を行うと
$$
f=tg+(t-1),
$$
$$
g=(t+1)(t-1).
$$
したがって最大公約多項式は $t-1$ です。また第一式を戻すと
$$
t-1=f-tg
$$
なので、Bézout表示も得られています。
別の例として $f=t$、$g=t-1$ は互いに素であり、
$$
1=t-(t-1)=1\cdot f-1\cdot g
$$
です。後に $t$ と $t-1$ の代わりに、互いに素な多項式を線形写像へ代入して、空間を直和分解します。
適用限界
除法算法の証明では、$g$ の最高次係数の逆元を使いました。係数が整数の場合、たとえば $t$ を $2t+1$ で整数係数のまま割って最高次項を消すには $1/2$ が必要です。したがって $\mathbb{Z}[t]$ では、ここで述べた形の除法算法は一般には成り立ちません。係数が体であるという仮定は実際に使われています。
演習
確認
$t^4+2t^3-t+1$ を $t^2+t+1$ で割り、商と余りを求めて検算せよ。
最高次項から順に消す。
$$
\begin{aligned}
t^4+2t^3-t+1
&=t^2(t^2+t+1)+(t^3-t^2-t+1)\\
&=t^2(t^2+t+1)+t(t^2+t+1)+(-2t^2-2t+1)\\
&=(t^2+t-2)(t^2+t+1)+3.
\end{aligned}
$$
商は $t^2+t-2$、余りは3である。右辺を展開すると元の多項式へ戻る。
理由
体 $K$ 上の零でない $n$ 次多項式は、$K$ の中に相異なる根を高々 $n$ 個しかもたないことを証明せよ。
$n$ に関する帰納法で示す。$n=0$ の非零定数多項式は根をもたない。
$n\ge1$ とし、$f$ が根 $a$ をもたなければ主張は成り立つ。根 $a$ をもつなら因数定理により
$$
f(t)=(t-a)g(t),
\qquad
\deg g=n-1
$$
と書ける。$a$ と異なる根 $b$ について
$$
0=f(b)=(b-a)g(b)
$$
であり、$b-a\ne0$ かつ体には零因子がないので $g(b)=0$ である。帰納法の仮定から、$a$ 以外の根は高々 $n-1$ 個である。$a$ を加えて根は高々 $n$ 個である。
転用
$f=t^2+1$ と $g=t+1$ の最大公約多項式を求め、$af+bg=\gcd(f,g)$ となる $a,b\in\mathbb{R}[t]$ を一組求めよ。
除法すると
$$
t^2+1=(t-1)(t+1)+2.
$$
したがって最大公約多項式は1である。式を2で割って整理すると
$$
1=\frac12(t^2+1)-\frac12(t-1)(t+1).
$$
よって
$$
a=\frac12,
\qquad
b=-\frac12(t-1)
$$
が一つのBézout表示を与える。展開して右辺が1になることを検算できる。
このページで回収したもの
多項式の割り算は単なる計算法ではなく、因数・最大公約多項式・Bézout恒等式を生む仕組みでした。後半では、多項式を線形写像へ代入することで、高い冪を短縮し、空間を固有値ごとの成分へ分解します。
次は、異なる対象を「同じもの」とみなすための同値関係と商集合を準備します。
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
