查看“︁N 次剩余”︁的源代码

[[分类:同余方程]]
{{InfoBox
|name=n次剩余
|eng_name=power residue
}}
{{InfoBox
|name=n次非剩余
|eng_name=power nonresidue
}}
{{InfoBox
|name=三次剩余
|eng_name=cubic residue
}}
{{InfoBox
|name=三次非剩余
|eng_name=cubic nonresidue
}}
{{InfoBox
|name=四次剩余
|eng_name=biquadratic residue
|aliases=quartic residue
}}
{{InfoBox
|name=四次非剩余
|eng_name=biquadratic nonresidue
|aliases=quartic nonresidue
}}
{{InfoBox
|name=n次剩余
|eng_name=residue of degree n
}}
{{InfoBox
|name=n次非剩余
|eng_name=nonresidue of degree n
}}
一个数是一个模数下的 '''<math>n</math> 次剩余'''('''residue of degree <math>n</math>''')指这个数与任意 <math>n</math> [[乘方|次方]]数在该模数下[[同余]]，是[[二次剩余]]的推广。
比如'''三次剩余'''('''cubic nonresidue''')、'''四次剩余'''('''biquadratic/quartic nonresidue''')等等。
也将非具体次数的直接统称为 '''<math>n</math> 次剩余'''/'''<math>m</math> 次剩余'''('''power residue''')。

由于模数和次数都常取正整数，通常会用 <math>m</math> 和 <math>n</math> 表示，具体上下文中次数使用其中哪一个字母决定了会叫做 <math>n</math> 次剩余还是 <math>m</math> 次剩余。

相反地，若一个数不与任何 <math>n</math> 次方数同余，称其为 '''<math>n</math> 次非剩余'''('''nonresidue of degree <math>n</math>''' )，
并统称为 '''<math>n</math> 次非剩余'''/'''<math>m</math> 次非剩余'''('''power nonresidue''' )。

{{小写字母开头}}

== 定义 ==

对整数 <math>a</math> ，以及大于 1 的正整数 <math>m</math> ， <math>\operatorname{gcd}(a, m) = 1</math> ，若 <math>(\exists x \in \mathbb{Z})(x^n \equiv a \pmod m)</math> ，则称 <math>a</math> 是一个'''模 <math>m</math> 的 <math>n</math> 次剩余'''('''residue of degree <math>n</math> modulo <math>m</math>''')，并称 <math>x</math> 是 <math>a</math> 在模 <math>m</math> 下的 '''<math>n</math> 次方根'''('''<math>n</math>-th root''' of <math>a</math> modulo <math>n</math>)；否则，称 <math>a</math> 是一个'''模 <math>m</math> 的 <math>n</math> 次非剩余'''('''nonresidue of degree <math>n</math> modulo <math>m</math>''')。

== 性质 ==

=== 模数有原根 ===

若 <math>m\geq 2, \operatorname{gcd}(a,m)=1</math> ，且模 <math>m</math> 下有[[原根]] <math>g</math> ，则：

可以把同余方程 <math>x^n \equiv a \pmod m</math> 表示成 <math>x^n \equiv g^{ny} \equiv a \pmod m</math> ，根据原根及对应[[指标]]表示的性质，其中 <math>x</math> 和 <math>y</math> 一一对应，因此也就一一对应于

<math>ny \equiv \gamma_{m,g}(a) \pmod{\varphi(m)}</math>

关于 <math>y</math> 的解。考虑这个[[一次同余方程]]的解的结构，有解条件是 <math>\operatorname{gcd}(n, \varphi(m)) \mid \gamma_{m,g}(a)</math> ，解数是 <math>\operatorname{gcd}(n, \varphi(m))</math> 。

因此，同余方程 <math>x^n \equiv a \pmod m</math> 有解，或者说 <math>a</math> 是模 <math>m</math> 的 <math>n</math> 次剩余，当且仅当：

<math>\operatorname{gcd}(n, \varphi(m)) \mid \gamma_{m,g}(a)</math>

且此时同余方程恰有 <math>\operatorname{gcd}(n, \varphi(m))</math> 个解。

对每个有解的 <math>a</math> ，解的个数都仅取决于 <math>n,m</math> 的，因此可以知道模 <math>m</math> 的[[简化剩余系]]中， <math>n</math> 次剩余有 <math>\tfrac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m))}</math> 个， <math>n</math> 次非剩余有 <math>\varphi(m) - \tfrac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m))}</math> 个。

考虑有原根时， <math>\varphi(m) = \operatorname{gcd}(\varphi(m), \gamma(a)) \cdot \operatorname{ind}_m (a)</math> ，也就是 <math>\operatorname{ind}_m (a) \mid \frac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m))}</math> ，这也当且仅当 <math>a^{\frac{\varphi(m)}{\operatorname{gcd}(n, \varphi(m)}}</math> 。

=== 模数为 2 的幂 ===

若 <math>m = 2^k, k\geq 3, \operatorname{gcd}(a,m)=1</math> 即 <math>2\not\mid a</math> ，且模 <math>m</math> 下有[[原根]] <math>g</math> ，则：

可以把同余方程 <math>x^n \equiv a \pmod n</math> 用指标组表示成 <math>x^n \equiv (-1)^{nu} 5^{nv} \equiv a \pmod m</math> ，也就是说 <math>x</math> 的解一一对应于 <math>x</math> 的以 -1 、 5 为底的指标组 <math>u,v</math> ，此时有

<math>\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>\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>\operatorname{gcd}(n,2) \cdot \operatorname{gcd}(n,2^{k-2})</math> 个解。

因此，若 <math>2\not\mid n</math> ，模 <math>2^k</math> 的简化剩余系中每个元素都是模 <math>2^k</math> 的 <math>n</math> 次剩余，且分别有一个 <math>n</math> 次方根；若 <math>2\not\mid n</math> ，模 <math>2^k</math> 的简化剩余系中有 <math>\tfrac{2^{k-2}}{\operatorname{gcd}(n,2^{k-2})}</math> 个元素是模 <math>2^k</math> 的 <math>n</math> 次剩余，且分别有 <math>2 \operatorname{gcd}(n,2^{k-2})</math> 个 <math>n</math> 次方根。

进一步地，当 <math>2\mid n</math> 时，记 <math>2^{\lambda} = \operatorname{gcd}(n,2^{k-2})</math> ，同余方程有解当且仅当 <math>a \equiv 1 \pmod{2^{\lambda + 2}}</math> 。

因此整体来说，二项同余方程有解，或者说是 <math>n</math> 次剩余的充分条件是

<math>\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>\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>

=== 模数为一般合数 ===

可以将模数进行质因子分解，通过[[中国剩余映射]]得到模质数幂的多个方程，根据以上两条得到各个子方程上分别的解，然后这些解之间的每个组合都能得到原模数下的一组解。


{{同余理论}}