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)$