> 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/yuan-gen-yu-zhi-biao/n-ci-tong-yu-shi.md).

# n次同余式

## **定义**

设$$m>1$$为整数，$$a$$是与$$m$$互素的正整数，若$$x^n\equiv a\left(\mod m\right)$$有解，则$$a$$为对模$$m$$的$$n$$次剩余

## **求解**$$x^n\equiv a\left(\mod m\right)$$

> * **STEP1: 验证有解**
>
>   $$\left(n,\varphi{\left (m\right)}\right)\mid \mathrm{ind}\_{g}{a}$$，$$g$$为模$$m$$的原根
>
>   解数为$$\left(n,\varphi{\left (m\right)}\right)$$
> * **STEP2: 等价同余式**
>
>   等价于$$n{\mathrm{ind}}*{g}{x}\equiv \mathrm{ind}*{g}{a}\left(\mod \varphi{\left (m\right)}\right)$$
> * **STEP3: 查指标表解出**$$n{\mathrm{ind}}\_{g}{x}$$**，解出**$$x\left(\mod m\right)$$

## **求解**$$n^x\equiv a\left(\mod m\right)$$

> * **STEP1: 等价同余式**
>
>   等价于$$x{\mathrm{ind}}*{g}{n}\equiv \mathrm{ind}*{g}{a}\left(\mod \varphi{\left (m\right)}\right)$$
> * **STEP2: 查指标表解出**$$x\left(\mod \varphi{\left (m\right)}\right)$$