# 多项式环

## **定义**

 $$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$$   | $$g\left(x\right)$$ |          $$f\left(x\right)$$          | $$g\left(x\right)/f\left(x\right)$$ | $$g\left(x\right)\mod f\left(x\right)$$ |
| $$\cdots$$ |      $$\cdots$$     |               $$\cdots$$              |              $$\cdots$$             |                $$\cdots$$               |
|    $$n$$   |      $$\cdots$$     | $$(g\left(x\right),f\left(x\right))$$ |              $$\cdots$$             |                  $$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$$次本原多项式