古早笔记拉出来测试

[TOC] # 2.2 多项式的表示和运算 ## 2.2.1 一元多项式 对于一个非零的整系数多项式 $$ f(x) = a_{m}x^{m} + \cdots + a_1x + a_0,\ a_m \neq 0 $$ 称它的所有系数的最大公因数 $GCD(a_1,\ a_1,\ \cdots,\ a_m)$ 为该多项式的**容度**,记作 $cont(f)$.容度为1的整系数多项式称为**本原多项式**。$\frac{sgn(a_m)f(x)}{cont(f)}$ 称为多项式 $f(x)$ 的**本原部分**，记作 $pp(f)$. Gauss 引理 设 $f(x),\ g(x)$ 是两个整系数多项式，则下面的等式成立: $$ cont(f \cdot g) = cont(f) \cdot cont(g)\newline pp(f \cdot g) = pp(f) \cdot pp(g) $$ # 2.3 同余与中国剩余定理 Hadamard 不等式 令 $B = max \left\lbrace |a_{i,j}|\ \bigm| i,\ j = 1, 2,\cdots,n \right\rbrace $ 则有 $|det(A)| \leq n^{\frac{n}{2}}B^{n}$. ## 2.3.3 插值与中国剩余定理 ### Lagrange 插值 $k[x]$ 上的多项式 $f(x)$ $$ f(x) \in k[x],\ f(x) = a_0 + a_1x + \cdots + a_{n-2}x^{n-2} + a_{n-1}x^{n-1} $$ 有一元素 $u \in k$ $$ f(u) = a_0 + a_1u + \cdots + a_{n-2}u^{n-2} + a_{n-1}u^{n-1} $$ $f(u)$ 可表示为: $$ \begin{equation} (1,\ u,\ \cdots,\ u^{n-2},\ u^{n-1}) \left( \begin{array}{c} a_0\newline a_1\newline \vdots\newline a_{n-2}\newline a_{n-1} \end{array} \right) \end{equation} $$ 若给定 $n$ 个不同值 $u_0,\ u_1,\ \cdots,\ u_{n-2},\ u_{n-1}\ \in k$, 并令 $v_i = f(u_i)$, 则 $$ \begin{equation} \left( \begin{array}{c} v_0\newline v_1\newline \vdots\newline v_{n-2}\newline v_{n-1} \end{array} \right)= \left( \begin{array}{ccccc} 1 & u_0 & \cdots & u_{0}^{n-2} & u_{0}^{n-1}\newline 1 & u_0 & \cdots & u_{0}^{n-2} & u_{0}^{n-1}\newline \vdots & \vdots & & \vdots & \vdots\newline 1 & u_0 & \cdots & u_{0}^{n-2} & u_{0}^{n-1}\newline 1 & u_0 & \cdots & u_{0}^{n-2} & u_{0}^{n-1}\newline \end{array} \right) \left( \begin{array}{c} a_0\newline a_1\newline \vdots\newline a_{n-2}\newline a_{n-1} \end{array} \right) \end{equation} $$ 由于各 $u_i$ 都不相同,所以上式中的范德蒙矩阵可逆,所以两边的向量可以相互确定. 求多项式 $f(x)$ 也可以通过构造如下的方程组 $$ l_0 = \frac{(x-u_1)(x-u_2)\cdots(x-u_{n-1})} {(u_0-u_1)(u_0-u_2)\cdots(u_0-u_{n-1})}\newline l_1 = \frac{(x-u_0)(x-u_2)\cdots(x-u_{n-1})} {(u_1-u_0)(u_1-u_2)\cdots(u_1-u_{n-1})}\newline \vdots\newline l_{n-1} = \frac{(x-u_0)(x-u_{1})\cdots(x-u_{n-2})} {(u_{n-1}-u_0)(u_{n-1}-u_1)\cdots(u_{n-1}-u_{n-2})} $$ 一般地, $$ l_{i} = \frac{(x-u_0)\cdots(x-u_{i-1})(x-u_{i+1})\cdots(x-u_{n-1})} {(u_i-u_0)\cdots(u_i-u_{i-1})(u_i-u_{i+1})\cdots(u_i-u_{n-1})} $$ 则 $f(x)$ 可表示为 $$ f(x) = v_{0}l_{0}(x) + v_{1}l_{1}(x) + \cdots + v_{n-1}l_{n-1}(x) $$ ### Newton 插值 由 CRT 可以知道, 求解同余问题的一个解可以表示为: $$ r = c_1m'_1 + c_2m'_2 + \cdots + c_nm'_n $$ 其中 $m'_i = \frac{M}{m_i},\ M = m_1m_2\cdots m_n$, 称为基底(均匀基), 迭代算法求解 同余问题也可以由混合基求解 $1,\ m_1,\ m_1m_2,\ \cdots,\ m_1m_2\cdots m_{n-1}$, 递归求解 $$ r = d_0m_0'' + d_1m_1'' + \cdots + d_{n-1}m_{n-1}'' $$ Newton 插值 $$ f(x) = d_0 + d_1(x-x_1) + d_2(x-x_1)(x-x_2) + \cdots + d_{n-1}(x-x_1)(x-x_2)\cdots(x-x_{n-1}) $$ $$ \begin{equation} \left\lbrace \begin{array}{l} d_0=v_0\newline d_i = \cfrac{v_{i+1} - d_0 - d_1(x_{i+1}-x_1) -\ \cdots\ - d_{i-1}(x_{i+1}-x_1)\cdots(x_{i+1}-x_{i-1})}{(x_{i+1}-x_1)\cdots(x_{i+1}-x_i)}\newline i\ \ = 1, \cdots, n-1 \end{array} \right. \end{equation} $$ # 2.4 环与理想 ## 2.4.1 环的定义 环是赋予两个运算(一个称为加法 $+$, 一个称为乘法 $ \cdot $)的集合, 记作 $(R,\ +,\ \cdot)$, 满足以下条件: (i) 乘法和加法运算封闭, 即 $R$ 中的每个元素经过这样的运算得到的仍是 $R$ 中的元素. (ii) 乘法和加法运算都满足结合律; 加法满足交换律, 而且乘法对加法有分配率. (iii) $R$ 中有零元 $0$, 使得 $\forall a \in R,\ a + 0 =a$ (iv) $R$ 中每个元都在 $R$ 中有负元, 即 $a \in R,\ \exists\ b \in R$, 使得 $ a+b=0$ 关于乘法满足交换律的环称为交换环, 环 $R$ 的零元一般记作 $0$. 若环 $R$ 中有元素 $e$ 满足 (v) 对 $R$ 的每个元素 $a$ 都有 $ ae = ea = a $, 则说 $e$ 是环 $R$ 的单位元(通常写作1). 若环 $R$ 满足 (vi) $a \neq 0,\ b \neq 0 \Longrightarrow ab \neq 0$, 则说 $R$ 是无零因子环 在有单位元的环中, 单位元一般记作 $1$. 有单位元、无零因子的交换环称为整环. 对于有单位元的环, 关于乘法有逆元的元素称为可逆元, 每个非零元都有逆元的交换环称为域. ## 2.4.2 环与理想 假定本节中所有的环都是有单位元的交换环 如果环 $R$ 的一个非空子集 $I$ 满足以下两个条件: (i) $\forall a, b \in I$, 有 $b - a \in I$; (ii) $\forall a \in I, r \in R$, 有 $ra \in I $. 则说 $I$, 是 $R$ 的一个理想. 一般地, 设 $a_1,\ a_2,\ \cdots ,\ a_k$ 是环 $R$ 的一组元素, 则$I = \left\lbrace \sum\limits_{i=1}^kr_ia_i \bigm| r_i \in R \right\rbrace$ 是 $R$ 的一个理想, 称为 $a_1,\ a_2,\ \cdots ,\ a_k$ 生成的理想, 记作 $\left<a_1,\ a_2,\ \cdots ,\ a_k\right>$. 可由一个元素生成的理想称为主理想; 如果环 $R$ 的每个理想都是主理想, 则环 $R$ 称为主理想环. ### 环的同态 环 $R$ 到环 $R'$ 的映射 $\phi:\ R \rightarrow R'$ 称为环同态, 如果 $$ (\forall a, b \in R) \left[ [\varphi(a + b) = \varphi(a) + \varphi(b)] \land [\varphi(a\cdot b) = \varphi(a) \cdot \varphi(b)] \right] $$ 同态映射 $\phi:\ R \rightarrow R'$ 的核是集合 $Ker\ \phi = \lbrace a \in R \bigm| \phi(a) = 0 \rbrace$ ### 环同态的基本定理 设 $\phi:\ R \rightarrow R'$ 是同态满射, 则 (1) 如果 $I$ 是环 $R$ 的理想, 则 $\phi(I) = \lbrace\phi(a) \in R' \bigm| a \in R\rbrace$ 是环 $R'$ 的一个理想; (2) 如果 $I'$ 是环 $R'$ 的理想, 则 $\phi^{-1}(I') = \lbrace a \in R \bigm| (\exists a'\in I')\ [\phi(a) = a']\rbrace$ 是环 $R$ 的一个理想 (3) $Ker \phi$ 是环 $R$ 的理想, $R/Ker\phi$是一个环, 且同构于 $R'$; (4) 用 $I_{R'}$ 表示 $R'$ 的全体理想, $I_R(\phi)$ 表示 $R$ 中包含 $Ker\phi$ 的全体理想. 则 $$ \psi: I \mapsto \phi(I),\ \forall I \in I_R(\phi) $$ 是集合 $I_R(\phi)$ 到 $I_{R'}$ 的一一映射, 而且具有下述的性质: $$ \phi^{-1}(\phi(I)) = I,\ I/Ker\phi \cong \phi(I),\ R/I \cong R'/\phi(I) $$ 多项式环 $\mathbb{Z}[x]$ 到 $\mathbb{Z}_m[x]$ 的模同态是指 $$ \phi:\ a_0 + a_1x + \cdots + a_nx^n \mapsto [a_0] + [a_1]x + \cdots + [a_n]x^n $$ ### 环 $R$ 的理想的几种运算 (1) 和: $I + J = \lbrace a + b \bigm| a \in I 且 b \in J\rbrace$; (2) 交: $I \cap J = \lbrace a \bigm| a \in I 且 a \in J\rbrace$; (3) 积: $IJ = \left\lbrace \sum_i^n\limits a_ib_i|a_i \in I,\ b_i\in J 且 n\in \mathbb{N} \right\rbrace$; (4) 商: $I: J = \lbrace a \in R \bigm| aJ \in J \rbrace$ (5) 根: $\sqrt{I} = \lbrace a \in R \bigm| (\exists n \in \mathbb{N}^+)[a^n \in I]\rbrace$ ### 理想运算的性质: 挖坑后补 ## 2.4.3 唯一分解环 相伴元: 如果 $R$ 中元素 $a,b$ 满足: $a=b\epsilon$, 其中 $\epsilon$ 是$R$ 中的可逆元, 则说 $a$ 与 $b$ 相伴. 对于任何一个非零元素 $r$, $R$ 中相伴元都是 $r$ 的因子, 这些因子称为 $r$ 的平凡因子. $r$ 的其他因子(如果还有的话)称为非平凡因子. 如果 $r$ 既不是零元也不是可逆元, 而且 $r$ 只有平凡因子, 则说 $r$ 是不可约的(或叫既约的). $R$中元素 $p$ 称为素元, 如果 $p$ 既不是零元又不是可逆元, 而且 $p | ab \Rightarrow p|a$ 或 $p|b,\ \forall a, b \in R$. 可知素元一定是不可约元. 整环 $R$ 称为唯一分解环, 如果下免得两条同时满足 (i) $R$ 中任何一个非零、非可逆的元素 $a$ 都能够分解成有限个不同不可约元素的乘积 $$ a = p_1p_2\cdots p_k $$ (ii) 如果 $a$ 还有另外的分解 $a = q_1q_2\cdots q_l$, 则 $l = k$, 且存在一个置换 $\sigma$, 使得 $p_i$ 与 $q_{\sigma (i)}$ 相伴, $i=1,\cdots ,k$ 对于唯一分解环, 不可约元与素元是相同的. 事实上 (ii) 可替换为 (ii') 不可约元一定是素元 主理想环是唯一分解环 ### Euclid 环 设 $R$ 是 整环, 如果存在映射 $\phi : R^{*}\rightarrow \mathbb{N}$, 使得对于 $\forall a, b\in R, b\neq 0$, 都有满足 $$ a = qb + r,\ r = 0 or \varphi(r) \lt \varphi(b) $$ 则说 $R$ 是 Euclid 环. $q, r$ 分别称为 $a$ 除以 $b$ 的商和余式, 记作 $quo(a, b),\ rem(a, b)$. Euclid 环一定是主理想环, 因而是唯一分解环. 规范集与规范元 Euclid 环 $R$ 的子集 $N$ 称为规范集, 如果满足下述两个条件 (i) $R$ 中的每个元 $a$ 都可以唯一表示成 $a=\epsilon \cdot n$, 其中 $n \in N$, $\epsilon$ 是 $R$ 中可逆元; (ii) $\forall n_1, n_2 \in N$ 有 $n_1n_2 \in N$. 规范集中的元素称为规范元. ## 2.4.4 扩张定理 设 $\mathbb{E}$ 是域 $\mathbb{k}$ 的扩域, $\mathbb{E} \supset \mathbb{k}$. 如果 $\mathbb{E}$ 中的每个元素都满足以域 $\mathbb{k}$ 中元素为系数的某个一元多项式, 则称 $\mathbb{E}$ 为 域 $\mathbb{k}$ 的代数扩域. 代数基本定理: 次数大于或等于 $1$ 的一元实系数多项式至少有一个复根. 代数基本定理可以推广为: 扩张定理: 域 $\mathbb{k}$ 上次数大于或等于 $1$ 的一元多项式, 一定在 $\mathbb{k}$ 的某个代数扩域中有零点. 即: 设 $f(x)\in \mathbb{k}[x]$, 是 $\mathbb{k}$ 上不可约多项式, 则一定存在代数扩域 $\mathbb{E}$, 使得 $f(x)$ 在 $\mathbb{E}$ 中有零点.