[IVA] Chapter 1, Section 5, Exercise 1, 6, 13

Exercise 1.

$f \in \mathbb{C}[x]$ が $n = \mathrm{deg}f > 0$ なる多項式とすると定理1-1-7より$f(a_n)=0$ となる $a_n \in \mathbb{C}$ が存在する。
すると系1-5-3の議論と同様にして $f = q (x-a_n), \; q \in \mathbb{C}[x], \; \mathrm{deg} q = n-1$ となる。すると数学的帰納法より $f = q_0 (x-a_1) \cdots (x - a_n), \; \mathrm{deg} q_0 = 0$ となって$q_0$ は定数であるが、$f$ の最高次係数を $c$ とすると $q_0 = c$ となるのは明らか。

Exercise 7.

入力: $f_1, \cdots f_s$
 $f_1, \cdots f_s$ の中で最も次数の低いものを $f_i$ とする。(同じ次数のものが複数有る場合は添字$i$が最小のものを選択する。
$j = 1, \cdots s, \; i \neq j$ なる $j$ に対して $q_j = \mathrm{LT}(f_j) / \mathrm{LT}(f_i)$ から定まる$q_j$ を用いて$r_j = f_j  - q_j f_i$ として$f_j$ を $f_i$ で割った余りを求める。
$\{r_j \;|\; j=1,\cdots,s, j \neq i\}$ が全て$0$の場合、$\mathrm{GCD}=f_i$。
さもなければ $r_1, \cdots, r_{i-1}, f_i, r_{i+1}, \cdots, r_s$ の中で零多項式で無いもののみを選んで入力とする。

$\mathrm{deg} r_j < \mathrm{deg} f_i$ であるからループを回す毎に入力の次数は減少するため、アルゴリズムが停止する事が保証される。

Exercise 13.

$f = a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1}x + a_n$ とするとき、

$af = (a a_0) x^n + (a a_1) x^{n-1} + \cdots + (a a_n)$ ゆえ

$(af)' = n (a a_0) x^{n-1} + (n-1)(a a_1) x^{n-2} + \cdots + (a a_{n-1})$ ゆえ
$(af)' = a f'$

$n = \mathrm{max}(\mathrm{deg}f, \mathrm{deg}g)$ として$f,g$ を共に$n$次の$k[x]$と看做して、

$f = a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1}x + a_n$

$g = b_0 x^n + b_1 x^{n-1} + \cdots + b_{n-1}x + b_n$ とするとき、

$f+g = (a_0+b_0) x^n + (a_1+b_1) x^{n-1} + \cdots + (a_{n-1}+b_{n-1})x + (a_n+b_n)$

$(f+g)' = n(a_0+b_0) x^{n-1} +  \cdots + (a_{n-1}+b_{n-1}) = f' + g'$

上記より線形性が保証されるので、$f = x^n, \; g=x^m$ という単項式について考えれば充分である。
$(fg)' = (x^{n+m})' = (n+m)x^{n+m-1}$
$f'g + fg' = nx^{n-1}x^m + x^n mx^{m-1} = (n+m)x^{n+m-1}$
よって示せた。