二次非剩余 首先，我们来定义什么是二次非剩余。在一个模运算的系统中，比如模一个奇素数 \( p \)，我们之前已经了解了二次剩余的概念。如果一个整数 \( a \) 在模 \( p \) 下与某个整数的平方同余，即存在整数 \( x \) 使得 \( x^2 \equiv a \pmod{p} \)，那么 \( a \) 就被称为模 \( p \) 的二次剩余。 那么，很自然地，二次非剩余就是那些不是二次剩余的整数。具体来说，对于一个与 \( p \) 互质的整数 \( a \)（即 \( \gcd(a, p) = 1 \)），如果同余方程 \( x^2 \equiv a \pmod{p} \) 在模 \( p \) 下 没有 解，那么 \( a \) 就被称为模 \( p \) 的二次非剩余。 接下来，我们探讨如何判断一个数是二次剩余还是二次非剩余。这里，勒让德符号（Legendre Symbol）是一个非常强大的工具。对于奇素数 \( p \) 和整数 \( a \)，勒让德符号 \( \left( \frac{a}{p} \right) \) 定义如下： \[ \left( \frac{a}{p} \right) = \begin{cases} 1 & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1 & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \\ 0 & \text{如果 } p \mid a \end{cases} \] 因此，判断 \( a \) 是否为二次非剩余，就等价于判断其勒让德符号是否等于 -1。 那么，如何计算勒让德符号呢？一个核心的结论是欧拉判别准则（Euler's Criterion）。它指出： \[ a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod{p} \] 这个准则为我们提供了一个直接的计算方法：计算 \( a^{(p-1)/2} \mod p \)，如果结果是 1，则 \( a \) 是二次剩余；如果结果是 -1（即 \( p-1 \)），则 \( a \) 是二次非剩余。 举例说明 ：我们取模数 \( p = 7 \)，这是一个奇素数。我们检查整数 3 是否是二次非剩余。 计算 \( (p-1)/2 = (7-1)/2 = 3 \)。 计算 \( 3^3 = 27 \)。 计算 \( 27 \mod 7 = 6 \)。 因为 6 在模 7 下等于 -1，所以 \( \left( \frac{3}{7} \right) = -1 \)。 因此，3 是模 7 的二次非剩余。我们可以验证，在模 7 下，平方数只有 \( 1^2=1, 2^2=4, 3^2=9\equiv2 \)，确实没有哪个数的平方等于 3。 最后，我们来讨论二次剩余和二次非剩余在模 \( p \) 的简化剩余系中的分布情况。模 \( p \) 的简化剩余系是指所有与 \( p \) 互质的、模 \( p \) 不同余的整数构成的集合，总共有 \( p-1 \) 个数。 一个非常重要的定理是：在模 \( p \) 的简化剩余系中， 恰好有一半是二次剩余，另一半是二次非剩余 。 具体来说： 二次剩余的个数是 \( (p-1)/2 \)。 二次非剩余的个数也是 \( (p-1)/2 \)。 这个结论可以通过考虑平方函数 \( f(x) = x^2 \mod p \) 来理解。在集合 \( \{1, 2, ..., p-1\} \) 中，每个二次剩余都恰好由两个不同的数（\( x \) 和 \( p-x \)）平方得到。因此，平方根是成对出现的，所以二次剩余的个数正好是总数 \( p-1 \) 的一半，即 \( (p-1)/2 \)。那么剩下的 \( (p-1)/2 \) 个数自然就是二次非剩余了。 再次举例 ：模 \( p = 7 \)，简化剩余系是 \( \{1, 2, 3, 4, 5, 6\} \)。 计算平方：\( 1^2=1, 2^2=4, 3^2=9\equiv2, 4^2=16\equiv2, 5^2=25\equiv4, 6^2=36\equiv1 \)。 所以，不同的二次剩余是 \( \{1, 2, 4\} \)，共 \( (7-1)/2 = 3 \) 个。 那么，二次非剩余就是剩下的 \( \{3, 5, 6\} \)，也是 3 个。