> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/tong-yu-shi/gao-ci-tong-yu-shi.md).

# 高次同余式

## **高次同余式解数**

若$$m=m\_1\cdots m\_k$$，则同余式$$f\left(x\right)\equiv0\left(\mod m\right)$$与同余式组

$$\left{ \begin{array}{**lr**} f\left(x\right)\equiv 0\left(\mod m\_1\right) &\ \vdots &\ f\left(x\right)\equiv 0\left(\mod m\_k\right) \end{array} \right.$$

等价。若$$T\_i$$为同余式$$f\left(x\right)\equiv 0\left(\mod m\_i\right)$$的解数，则同余式解数$$T=T\_1\cdots T\_k$$

## **高次同余式求解**

$$f\left(x\right)\equiv0\left(\mod p^\alpha\right)$$

> * **STEP1: 验证有解**
>
>   $$x=x\_1\left(\mod p\right)$$为$$f\left(x\right)\equiv0\left(\mod p\right)$$的一个解，$$\left(f^\prime\left(x\_1\right),p\right)=1$$
> * **STEP2: 递推**
>
>   $$x\equiv x\_\alpha\left(\mod p^\alpha\right)$$
>
>   $$\left{ \begin{array}{**lr**} t\_{i-1}\equiv-\frac{f\left(x\_{i-1}\right)}{p^{i-1}}\cdot\left({f^\prime\left(x\_1\right)}^{-1}\left(\mod p\right)\right)\left(\mod p\right) &\ x\_i\equiv x\_{i-1}+t\_{i-1}\cdot p^{i-1}\left(\mod p^i\right) &\ i=2,\cdots,a \end{array} \right.$$