高次剩余 首先，我们来理解什么是高次剩余。在模运算中，我们经常关心一个数在模某个正整数下是否是另一个数的幂次。具体来说，设 \( m \) 是一个正整数，\( a \) 是一个与 \( m \) 互素的整数，\( k \ge 2 \) 是一个整数。如果同余方程 \[ x^k \equiv a \pmod{m} \] 有解，即存在某个整数 \( x \) 满足这个同余式，那么我们就称 \( a \) 是模 \( m \) 的一个 \( k \) 次剩余。如果这个方程没有解，我们就称 \( a \) 是模 \( m \) 的一个 \( k \) 次非剩余。 接下来，我们来看一个具体的例子。考虑模 \( m = 7 \) 的情况。我们想找出模 7 的二次剩余，也就是 \( k = 2 \) 的情况。我们计算从 1 到 6 的平方模 7： \[ 1^2 = 1 \equiv 1 \pmod{7}, \quad 2^2 = 4 \equiv 4 \pmod{7}, \quad 3^2 = 9 \equiv 2 \pmod{7}, \] \[ 4^2 = 16 \equiv 2 \pmod{7}, \quad 5^2 = 25 \equiv 4 \pmod{7}, \quad 6^2 = 36 \equiv 1 \pmod{7}. \] 所以，模 7 的二次剩余是 1, 2, 4。而 3, 5, 6 是模 7 的二次非剩余。注意，这里我们只考虑与 7 互素的数，即 1 到 6。 现在，我们推广到一般的 \( k \) 次剩余。判断一个数是否是模 \( m \) 的 \( k \) 次剩余，通常依赖于模 \( m \) 的简化剩余系的性质。设 \( \phi(m) \) 是欧拉函数，表示模 \( m \) 的简化剩余系中元素的个数。那么，在模 \( m \) 的简化剩余系中，一个数 \( a \) 是 \( k \) 次剩余的充分必要条件是 \[ a^{\frac{\phi(m)}{\gcd(k, \phi(m))}} \equiv 1 \pmod{m}. \] 这个条件可以通过原根理论来理解。如果模 \( m \) 有原根 \( g \)，那么每个与 \( m \) 互素的数 \( a \) 都可以写成 \( a \equiv g^u \pmod{m} \)，其中 \( u \) 是某个整数。那么，方程 \( x^k \equiv a \pmod{m} \) 有解当且仅当存在整数 \( v \) 使得 \( (g^v)^k = g^{kv} \equiv g^u \pmod{m} \)，这等价于同余方程 \[ k v \equiv u \pmod{\phi(m)} \] 有解。而这个线性同余方程有解当且仅当 \( \gcd(k, \phi(m)) \mid u \)。由于 \( a \equiv g^u \pmod{m} \)，并且 \( g \) 的阶是 \( \phi(m) \)，所以 \( a^{\frac{\phi(m)}{\gcd(k, \phi(m))}} \equiv g^{u \cdot \frac{\phi(m)}{\gcd(k, \phi(m))}} \pmod{m} \)。如果 \( \gcd(k, \phi(m)) \mid u \)，那么 \( u \cdot \frac{\phi(m)}{\gcd(k, \phi(m))} \) 是 \( \phi(m) \) 的倍数，所以 \( a^{\frac{\phi(m)}{\gcd(k, \phi(m))}} \equiv 1 \pmod{m} \)。反之，如果这个等式成立，那么 \( \phi(m) \mid u \cdot \frac{\phi(m)}{\gcd(k, \phi(m))} \)，即 \( \gcd(k, \phi(m)) \mid u \)。因此，上述条件成立。 最后，我们讨论高次剩余符号。类似于二次剩余的勒让德符号，对于高次剩余，也有相应的符号。例如，对于奇素数 \( p \) 和整数 \( a \) 满足 \( p \nmid a \)，我们可以定义 \( k \) 次剩余符号。当 \( k \) 整除 \( p-1 \) 时，这个符号是一个 \( k \) 次单位根。具体地，设 \( \omega \) 是一个本原 \( k \) 次单位根，那么高次剩余符号 \( \left( \frac{a}{p} \right)_ k \) 定义为满足 \[ a^{\frac{p-1}{k}} \equiv \left( \frac{a}{p} \right)_ k \pmod{p} \] 的 \( k \) 次单位根。这个符号具有乘性： \[ \left( \frac{ab}{p} \right)_ k = \left( \frac{a}{p} \right)_ k \left( \frac{b}{p} \right)_ k. \] 并且，\( a \) 是模 \( p \) 的 \( k \) 次剩余当且仅当 \( \left( \frac{a}{p} \right)_ k = 1 \)。 高次剩余理论在数论中有着广泛的应用，特别是在研究高次互反律和代数数论中的分圆域时非常重要。