N 次剩余
| n次剩余 | |
|---|---|
| 术语名称 | n次剩余 |
| 英语名称 | power residue |
| n次非剩余 | |
|---|---|
| 术语名称 | n次非剩余 |
| 英语名称 | power nonresidue |
| 三次剩余 | |
|---|---|
| 术语名称 | 三次剩余 |
| 英语名称 | cubic residue |
| 三次非剩余 | |
|---|---|
| 术语名称 | 三次非剩余 |
| 英语名称 | cubic nonresidue |
| 四次剩余 | |
|---|---|
| 术语名称 | 四次剩余 |
| 英语名称 | biquadratic residue |
| 别名 | quartic residue |
| 四次非剩余 | |
|---|---|
| 术语名称 | 四次非剩余 |
| 英语名称 | biquadratic nonresidue |
| 别名 | quartic nonresidue |
| n次剩余 | |
|---|---|
| 术语名称 | n次剩余 |
| 英语名称 | residue of degree n |
| n次非剩余 | |
|---|---|
| 术语名称 | n次非剩余 |
| 英语名称 | nonresidue of degree n |
一个数是一个模数下的 [math]\displaystyle{ n }[/math] 次剩余(residue of degree [math]\displaystyle{ n }[/math])指这个数与任意 [math]\displaystyle{ n }[/math] 次方数在该模数下同余，是二次剩余的推广。 比如三次剩余(cubic nonresidue)、四次剩余(biquadratic/quartic nonresidue)等等。 也将非具体次数的直接统称为 [math]\displaystyle{ n }[/math] 次剩余/[math]\displaystyle{ m }[/math] 次剩余(power residue)。
由于模数和次数都常取正整数，通常会用 [math]\displaystyle{ m }[/math] 和 [math]\displaystyle{ n }[/math] 表示，具体上下文中次数使用其中哪一个字母决定了会叫做 [math]\displaystyle{ n }[/math] 次剩余还是 [math]\displaystyle{ m }[/math] 次剩余。
相反地，若一个数不与任何 [math]\displaystyle{ n }[/math] 次方数同余，称其为 [math]\displaystyle{ n }[/math] 次非剩余(nonresidue of degree [math]\displaystyle{ n }[/math] )， 并统称为 [math]\displaystyle{ n }[/math] 次非剩余/[math]\displaystyle{ m }[/math] 次非剩余(power nonresidue )。
由于技术原因，标题首字母会被大写。这一术语通常应当以小写字母开头。
定义
对整数 [math]\displaystyle{ a }[/math] ，以及大于 1 的正整数 [math]\displaystyle{ m }[/math] ， [math]\displaystyle{ \operatorname{gcd}(a, m) = 1 }[/math] ，若 [math]\displaystyle{ (\exists x \in \mathbb{Z})(x^n \equiv a \pmod m) }[/math] ，则称 [math]\displaystyle{ a }[/math] 是一个模 [math]\displaystyle{ m }[/math] 的 [math]\displaystyle{ n }[/math] 次剩余(residue of degree [math]\displaystyle{ n }[/math] modulo [math]\displaystyle{ m }[/math])，并称 [math]\displaystyle{ x }[/math] 是 [math]\displaystyle{ a }[/math] 在模 [math]\displaystyle{ m }[/math] 下的 [math]\displaystyle{ n }[/math] 次方根([math]\displaystyle{ n }[/math]-th root of [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math])；否则，称 [math]\displaystyle{ a }[/math] 是一个模 [math]\displaystyle{ m }[/math] 的 [math]\displaystyle{ n }[/math] 次非剩余(nonresidue of degree [math]\displaystyle{ n }[/math] modulo [math]\displaystyle{ m }[/math])。
性质
模数有原根
若 [math]\displaystyle{ m\geq 2, \operatorname{gcd}(a,m)=1 }[/math] ，且模 [math]\displaystyle{ m }[/math] 下有原根 [math]\displaystyle{ g }[/math] ，则：
可以把同余方程 [math]\displaystyle{ x^n \equiv a \pmod m }[/math] 表示成 [math]\displaystyle{ x^n \equiv g^{ny} \equiv a \pmod m }[/math] ，根据原根及对应指标表示的性质，其中 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 一一对应，因此也就一一对应于
[math]\displaystyle{ ny \equiv \gamma_{m,g}(a) \pmod{\varphi(m)} }[/math]
关于 [math]\displaystyle{ y }[/math] 的解。考虑这个一次同余方程的解的结构，有解条件是 [math]\displaystyle{ \operatorname{gcd}(n, \varphi(m)) \mid \gamma_{m,g}(a) }[/math] ，解数是 [math]\displaystyle{ \operatorname{gcd}(n, \varphi(m)) }[/math] 。
因此，同余方程 [math]\displaystyle{ x^n \equiv a \pmod m }[/math] 有解，或者说 [math]\displaystyle{ a }[/math] 是模 [math]\displaystyle{ m }[/math] 的 [math]\displaystyle{ n }[/math] 次剩余，当且仅当：
[math]\displaystyle{ \operatorname{gcd}(n, \varphi(m)) \mid \gamma_{m,g}(a) }[/math]
且此时同余方程恰有 [math]\displaystyle{ \operatorname{gcd}(n, \varphi(m)) }[/math] 个解。
对每个有解的 [math]\displaystyle{ a }[/math] ，解的个数都仅取决于 [math]\displaystyle{ n,m }[/math] 的，因此可以知道模 [math]\displaystyle{ m }[/math] 的简化剩余系中， [math]\displaystyle{ n }[/math] 次剩余有 [math]\displaystyle{ \tfrac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m))} }[/math] 个， [math]\displaystyle{ n }[/math] 次非剩余有 [math]\displaystyle{ \varphi(m) - \tfrac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m))} }[/math] 个。
考虑有原根时， [math]\displaystyle{ \varphi(m) = \operatorname{gcd}(\varphi(m), \gamma(a)) \cdot \operatorname{ind}_m (a) }[/math] ，也就是 [math]\displaystyle{ \operatorname{ind}_m (a) \mid \frac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m))} }[/math] ，这也当且仅当 [math]\displaystyle{ a^{\frac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m)}} }[/math] 。
模数为 2 的幂
若 [math]\displaystyle{ m = 2^k, k\geq 3, \operatorname{gcd}(a,m)=1 }[/math] 即 [math]\displaystyle{ 2\not\mid a }[/math] ，且模 [math]\displaystyle{ m }[/math] 下有原根 [math]\displaystyle{ g }[/math] ，则：
可以把同余方程 [math]\displaystyle{ x^n \equiv a \pmod n }[/math] 用指标组表示成 [math]\displaystyle{ x^n \equiv (-1)^{nu} 5^{nv} \equiv a \pmod m }[/math] ，也就是说 [math]\displaystyle{ x }[/math] 的解一一对应于 [math]\displaystyle{ x }[/math] 的以 -1 、 5 为底的指标组 [math]\displaystyle{ u,v }[/math] ，此时有
[math]\displaystyle{ \begin{cases} nu \equiv \gamma^{(-1)}_{m,5} (a) \pmod 2 \\ nv \equiv \gamma^{(0)}_{m,5} (a) \pmod{2^{k-2}} \end{cases} }[/math]
因此同余方程有解，当且仅当：
[math]\displaystyle{ \begin{cases} \operatorname{gcd}(n,2) \mid \gamma^{(-1)}_{m,5}(a) \\ \operatorname{gcd}(n,2^{k-2}) \mid \gamma^{(0)}_{m,5}(a) \end{cases} }[/math]
且此时同余方程刚好有 [math]\displaystyle{ \operatorname{gcd}(n,2) \cdot \operatorname{gcd}(n,2^{k-2}) }[/math] 个解。
因此，若 [math]\displaystyle{ 2\not\mid n }[/math] ，模 [math]\displaystyle{ 2^k }[/math] 的简化剩余系中每个元素都是模 [math]\displaystyle{ 2^k }[/math] 的 [math]\displaystyle{ n }[/math] 次剩余，且分别有一个 [math]\displaystyle{ n }[/math] 次方根；若 [math]\displaystyle{ 2\not\mid n }[/math] ，模 [math]\displaystyle{ 2^k }[/math] 的简化剩余系中有 [math]\displaystyle{ \tfrac{2^{k-2}}{\operatorname{gcd}(n,2^{k-2})} }[/math] 个元素是模 [math]\displaystyle{ 2^k }[/math] 的 [math]\displaystyle{ n }[/math] 次剩余，且分别有 [math]\displaystyle{ 2 \operatorname{gcd}(n,2^{k-2}) }[/math] 个 [math]\displaystyle{ n }[/math] 次方根。
进一步地，当 [math]\displaystyle{ 2\mid n }[/math] 时，记 [math]\displaystyle{ 2^{\lambda} = \operatorname{gcd}(n,2^{k-2}) }[/math] ，同余方程有解当且仅当 [math]\displaystyle{ a \equiv 1 \pmod{2^{\lambda + 2}} }[/math] 。
因此整体来说，二项同余方程有解，或者说是 [math]\displaystyle{ n }[/math] 次剩余的充分条件是
[math]\displaystyle{ \begin{cases} \operatorname{gcd}(n, 2) \mid \frac{a-1}{2} \\ \operatorname{ind}_{2^k}(a) \mid {\frac{2^{k-2}}{\operatorname{gcd}(n, 2^{k-2})}} \end{cases} }[/math]
或者写成
[math]\displaystyle{ \begin{cases} \operatorname{gcd}(n, 2) \mid \frac{a-1}{2} \\ a^{\frac{2^{k-2}}{\operatorname{gcd}(n, 2^{k-2})}} \equiv 1 \pmod{2^k} \end{cases} }[/math]
模数为一般合数
可以将模数进行质因子分解，通过中国剩余映射得到模质数幂的多个方程，根据以上两条得到各个子方程上分别的解，然后这些解之间的每个组合都能得到原模数下的一组解。