多项式环

定义

$R$为整环，$x$为变量，$R$上的多项式记作$R\left[x\right]=\left\{f\left(x\right)=a_nx^n+\cdots+a_1x+a_0\mid a_i\in R,0\leq i\leq n,n\in R\right\}$ 对于多项式加法和乘法，$R\left[x\right]$为整环

多项式整除和不可约多项式

• $g\left(x\right)\mid f\left(x\right)$：$\exists q\left(x\right),f\left(x\right)\mid q\left(x\right)\cdot g\left(x\right)$

• $g\left(x\right),h\left(x\right)\neq 0,g\left(x\right)\mid f\left(x\right),h\left(x\right)\mid g\left(x\right)\Longrightarrow h\left(x\right)\mid f\left(x\right)$

  • $g\left(x\right),h\left(x\right)\neq 0,g\left(x\right)\mid f\left(x\right),h\left(x\right)\mid g\left(x\right)\Longrightarrow \forall s\left(x\right),t\left(x\right),h\left(x\right)\mid s\left(x\right)\cdot f\left(x\right)+t\left(x\right)\cdot g\left(x\right)$

  • 不可约多项式：除$1$和$f\left(x\right)$外，$f\left(x\right)$没有其他非常数因式，否则$f\left(x\right)$为合式

• 设$f\left(x\right)$是域$K$上的$n$次可约多项式，$p\left(x\right)$是$f\left(x\right)$的次数最小的非常数饮食，则$p\left(x\right)$一定是不可约多项式，且$\deg{p}\leq \frac{1}{2}\deg{f}$

• 设$f\left(x\right)$是域$K$上的$n$次可约多项式，若$\forall$不可约多项式$p\left(x\right),\deg{p}\leq \frac{1}{2}\deg{f},p\left(x\right)\not\mid f\left(x\right)$，则$f\left(x\right)$为不可约多项式

多项式欧几里得除法

• 设整环$R$上两个多项式$f\left(x\right)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,g\left(x\right)=x^m+\cdots+b_1x+b_0$，则存在$q\left(x\right),r\left(x\right),f\left(x\right)=q\left(x\right)\cdot g\left(x\right)+r\left(x\right)$

  $q\left(x\right)$为不完全商，$r\left(x\right)$为余式

  • 对于$f\left(x\right)$有$a\in R$，存在$q\left(x\right)$和常数$c=f\left(a\right),f\left(x\right)=q\left(x\right)\left(x-a\right)+f\left(a\right)$

  • 对于$f\left(x\right)$有$a\in R$，$x-a\mid f\left(x\right)\Longleftrightarrow f\left(a\right)=0$

  • $g\left(x\right)\mid f\left(x\right)\Longleftrightarrow r\left(x\right)=0$

• 最大公因式：$f\left(x\right),g\left(x\right),d\left(x\right)\in R\left[x\right]$

  • $d\left(x\right)\mid f\left(x\right),d\left(x\right)\mid g\left(x\right)$

  • $h\left(x\right)\mid f\left(x\right),h\left(x\right)\mid g\left(x\right)\Longrightarrow h\left(x\right)\mid d\left(x\right)$

    则$d\left(x\right)$为最大公因式，记作$\left(f\left(x\right),g\left(x\right)\right)$

    若$\left(f\left(x\right),g\left(x\right)\right)=1$，则$f\left(x\right)$和$g\left(x\right)$互质

求最大公因式（广义欧几里得除法） 假设$\deg f<\deg g$

$j$	$r_j$	$r_{j+1}$	$q_{j+1}$	$r_{j+2}$
$0$

• 设域$K$上两个多项式$f\left(x\right),g\left(x\right)$，则存在$q\left(x\right),h\left(x\right)\in K\left[x\right],f\left(x\right)=q\left(x\right)\cdot g\left(x\right)+h\left(x\right),\deg{h}<\deg{g}$

  • $\left(f\left(x\right),g\left(x\right)\right)=\left(g\left(x\right),h\left(x\right)\right)$

• 设域$K$上两个多项式$f\left(x\right),g\left(x\right)$，$\deg{g}\geq1,\left(f\left(x\right),g\left(x\right)\right)=r_{k}{\left(x\right)},r_{k}{\left(x\right)}$为广义欧几里得除法中最后一个非零余式

  $s_k\left(x\right)\cdot f\left(x\right)+t_k\left(x\right)\cdot g\left(x\right)=\left(f\left(x\right),g\left(x\right)\right)$ \left\{\begin{array}{**lr**} s_{-2}\left(x\right)=1\\ s_{-1}\left(x\right)=0\\ t_{-2}\left(x\right)=0\\ t_{-1}\left(x\right)=1\\ s_j\left(x\right)=\left(-q_j\left(x\right)\right)s_{j-1}\left(x\right)+s_{j-2}\left(x\right)\\ t_j\left(x\right)=\left(-q_j\left(x\right)\right)t_{j-1}\left(x\right)+t_{j-2}\left(x\right)\end{array} \right.

多项式同余

• 给定$K\left[x\right]$中一个首一多项式$m\left(x\right)$，若$m\left(x\right)\mid f\left(x\right)-g\left(x\right)$，则$f\left(x\right)\equiv g\left(x\right)\left(\mod m\left(x\right)\right)$

  • $\forall a\left(x\right),a\left(x\right)\equiv a\left(x\right)\left(\mod m\left(x\right)\right)$

  • $a\left(x\right)\equiv b\left(x\right)\left(\mod m\left(x\right)\right)\Longrightarrow b\left(x\right)\equiv a\left(x\right)\left(\mod m\left(x\right)\right)$

  • $a\left(x\right)\equiv b\left(x\right),b\left(x\right)\equiv c\left(x\right)\left(\mod m\left(x\right)\right)\Longrightarrow a\left(x\right)\equiv c\left(x\right)\left(\mod m\left(x\right)\right)$

  • $a_1\left(x\right)\equiv b_1\left(x\right),a_2\left(x\right)\equiv b_2\left(x\right)\left(\mod m\left(x\right)\right)\Longrightarrow a_1\left(x\right)+a_2\left(x\right)\equiv b_1\left(x\right)+b_2\left(x\right),a_1\left(x\right)\cdot a_2\left(x\right)\equiv b_1\left(x\right)\cdot b_2\left(x\right)\left(\mod m\left(x\right)\right)$

• $a\left(x\right)\equiv b\left(x\right)\left(\mod m\left(x\right)\right)\Longleftrightarrow a\left(x\right)=b\left(x\right)+s\left(x\right)\cdot m\left(x\right)$

• $r\left(x\right)$为$f\left(x\right)$模$m\left(x\right)$的最小余式

• 构造有限域：设$K$为一个域，$p\left(x\right)$为$K\left[x\right]$中的不可约多项式，则商环$K\left[x\right]/p\left(x\right)$对于加法式和乘法式构成一个域

本原多项式

• 设$p$为素数，$p\left(x\right)$是$F_p\left[x\right]$中的$n$次不可约多项式，则$F_p\left[x\right]/p\left(x\right)=\left\{a_{n-1}x^{n-1}+\cdots+a_1x+a_0\mid a_i\in F_p\right\}$记作$F_{p^n}$，这个域元素个数为$p^n$

• 设$p$为素数，$f\left(x\right)$为$f_p\left[x\right]$中的$n$次多项式，则使得$x^e\equiv1\left(\mod f\left(x\right)\right)$成立的最小正整数$e$叫做$f\left(x\right)$在$F_p$上的指数，记作$\mathrm{ord}_p\left(f\left(x\right)\right)$

  • 整数$d$使得$x^d\equiv1\left(\mod f\left(x\right)\right)$,则$\mathrm{ord}_p\left(f\left(x\right)\right)\mid d$

  • $g\left(x\right)\mid f\left(x\right)\Longrightarrow \mathrm{ord}_p\left(f\left(x\right)\right)\mid d$

  • $\left(f\left(x\right),g\left(x\right)\right)=1\Longrightarrow \mathrm{ord}_p\left(f\left(x\right)\cdot g\left(x\right)\right)=\left[\mathrm{ord}_p\left(f\left(x\right)\right),\mathrm{ord}_p\left(g\left(x\right)\right)\right]$

  • $f\left(x\right)$为$F_p\left[x\right]$上的$n$次不可约多项式，则$\mathrm{ord}_p\left(f\left(x\right)\right)\mid p^n-1$

• 若$\mathrm{ord}_p\left(f\left(x\right)\right)=p^n-1$，则称$f\left(x\right)$为$F_p$上的本原多项式

• 设$p$为素数，$f\left(x\right)$为$F_p\left[x\right]$上的本原多项式，则$f\left(x\right)$是$F_p\left[x\right]$上的不可约多项式

判别本原多项式

设$p$为素数，$n$为正整数，$f\left(x\right)$是$F_p\left[x\right]$中的$n$次多项式，若$x^{p^n-1}\equiv 1\left(\mod f\left(x\right)\right)$，对于$p^n-1$的所有不同素因数$q_1,\cdots,q_s$，$x^{\frac{p^n-1}{q_i}}\not \equiv1\left(\mod f\left(x\right)\right),i=1,\cdots,s$，则$f\left(x\right)$是$n$次本原多项式