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

[[分类:同余方程]]
{{InfoBox
|name=二次剩余
|eng_name=quadratic residue
}}
{{InfoBox
|name=二次非剩余
|eng_name=quadratic nonresidue
}}
一个数是一个模数下的'''二次剩余'''('''quadratic residue''')指这个数与任意[[完全平方数]]在该模数下[[同余]]。
相反地，若一个数不与任何完全平方数同余，称其为'''二次非剩余'''('''quadratic nonresidue''')。

简单地说，“相等意义下，整数的平方”就叫做“完全平方数”的话，“同余意义下，整数的平方”就叫做“二次剩余”。

== 定义 ==

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

注：有的定义不要求互质。

使用[[模 n 剩余类乘法群]]的集合记号 <math>(\mathbb{Z}/n\mathbb{Z})^*</math> 表达所有与 <math>n</math> 互质的剩余类的集合，记号 <math>((\mathbb{Z}/n\mathbb{Z})^*)^2</math> 表达其中全体元素平方后所得元素的集合。由于乘法封闭，有 <math>(\mathbb{Z}/n\mathbb{Z})^* \supseteq ((\mathbb{Z}/n\mathbb{Z})^*)^2</math> 。因此，可以对应二次剩余所在剩余类的集合为 <math>((\mathbb{Z}/n\mathbb{Z})^*)^2</math> ，二次非剩余所在剩余类的集合为 <math>(\mathbb{Z}/n\mathbb{Z})^* \setminus ((\mathbb{Z}/n\mathbb{Z})^*)^2</math> 

== 意义 ==

一般的二次同余方程 <math>a x^2 + b x + c \equiv 0 \pmod n , n \not\mid a</math> ，可在保持解不变的前提下，全式同乘以 <math>4a</math> 再两侧加上 <math>b^2</math> ，直接配方为 <math>(2ax + b)^2 \equiv b^2 -4ac \pmod{4an}</math> ，因此有解问题等价于 <math>y^2 \equiv \Delta \pmod {4an}</math> 是否有解。

通过研究 <math>\Delta = b^2-4ac</math> 是否是 <math>4an</math> 的二次剩余，即可知道原同余方程的解的情况。

== 性质 ==

在任意大于 1 的整数模下， 1 都是二次剩余，至少有 1 这个解。

首先模数为 2 的情况，所有的数都和 0 或 1 同余， 1 本身就是二次剩余。

对更大的数，同余关系中全体的二次剩余可以通过 <math>0^2, 1^2, 2^2, \dots, (n-1)^2</math> 得到，甚至因为 <math>a^2\equiv (n-a)^2 \pmod n</math> ，只需要考虑其中的一半。

=== 模数为奇质数 ===

==== <ins>欧拉</ins>准则 ====

对质数 <math>p</math> ，以及任意整数 <math>a</math> ，且 <math>p \not\mid a</math> ，有
<math>a ^ {\frac{p-1}{2}} \equiv 
\begin{cases}
+1 &, \text{是二次剩余} \\
-1 &, \text{是二次非剩余} \\
\end{cases} \pmod p
</math>

==== 推论 ====

由<ins>欧拉</ins>准则可知，

* <math>1, 2, \dots, p-1</math> 中，二次剩余和二次非剩余必各占一半。
* 任意两个二次剩余相乘都是二次剩余，任意两个二次非剩余相乘也是二次剩余，只有一个二次剩余和一个二次非剩余相乘时，得到二次非剩余。
** 如果把 <math>1, 2, \dots, p-1</math> 分成两个非[[空集|空]][[集合]] <math>C_1, C_2</math> ，使得任意 <math>C_1 C_1 \subseteq C_1</math> 、 <math>C_2 C_2 \subseteq C_2</math> 、 <math>C_1 C_2 \subseteq C_2</math> ，则有唯一解 <math>C_1</math> 取二次剩余集合、 <math>C_2</math> 取二次非剩余集合。
* 考虑模逆的话，二次剩余的模逆都是二次剩余，非二次剩余的模逆都是非二次剩余。

且对 -1 计算 <math>\tfrac{p-1}{2}</math> 可知，

<math>
\begin{aligned}
p\equiv 1 \pmod 4 &\Rightarrow -1 \text{ 是模 } p \text{ 二次剩余 } \\
p\equiv 3 \pmod 4 &\Rightarrow -1 \text{ 是模 } p \text{ 二次非剩余 } \\
\end{aligned}
</math>

因此，

<math>
\begin{aligned}
p\equiv 1 \pmod 4 &\Rightarrow d \text{ 是模 } p \text{ 二次剩余 } \leftrightarrow -d \text{ 是模 } p \text{ 二次剩余 } \\
p\equiv 3 \pmod 4 &\Rightarrow d \text{ 是模 } p \text{ 二次剩余 } \leftrightarrow -d \text{ 是模 } p \text{ 二次非剩余 } \\
\end{aligned}
</math>

且如果 -1 是模奇质数 <math>p</math> 的二次剩余，其平方根一定是任意二次非剩余 <math>c</math> 的 <math>c^\tfrac{p-1}{4}</math> 。

=== 模数为奇质数幂 ===

对奇质数幂 <math>p^k</math> 仍有 <math>b \equiv 1 \pmod{p^k} \rightarrow b \equiv 1 \pmod{p^k} \lor b \equiv -1 \pmod{p^k}</math> 。因此可以推出 <math>b \equiv c \pmod{p^k} \rightarrow b \equiv c \pmod{p^k} \lor b \equiv -c \pmod{p^k}</math> ，也就是说平方根也会有且仅有两个一组地存在。

因此可以推测平方映射把含有 <math>\varphi(p^k)</math> 个元素的 <math>(\mathbb{Z}/n\mathbb{Z})^*</math> 两个一组地映射到 <math>((\mathbb{Z}/n\mathbb{Z})^*)^2</math> 中，后者的元素个数是 <math>\tfrac{\varphi(p^k)}{2}</math> 。换句话说，奇质数幂时，二次剩余有 <math>\tfrac{\varphi(p^k)}{2}</math> 个，相应地二次非剩余也有 <math>\tfrac{\varphi(p^k)}{2}</math> 个。

类似于<ins>欧拉</ins>准则，我们可以得到：

对质数 <math>p</math> 及正整数 <math>k</math>，以及任意整数 <math>a</math> ，且 <math>p \not\mid a</math> ，有
<math>a ^ {\frac{\varphi(p^k)}{2}} \equiv 
\begin{cases}
+1 &, \text{是二次剩余} \\
-1 &, \text{是二次非剩余} \\
\end{cases} \pmod p
</math>
其中 <math>\varphi(p^k) = (p-1) p^{k-1}</math> 是<ins>欧拉</ins>函数。

可以推出 <math>a</math> 是模 <math>p^k</math> 的二次剩余，当且仅当 <math>a</math> 是模 <math>p</math> 的二次剩余。

=== 模数为奇数 ===

对模数为一般合数的同余方程，根据[[中国剩余映射]]，一定可以将其拆解为多个质数幂下分别的同余方程，并分别求出多个解，最终通过解的组合进行逆映射得到原方程的解。因此可记 <math>n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m}</math> ，同余方程可以分解成模 <math>p_1^{\alpha_1}, p_2^{\alpha_2}, \dots, p_m^{\alpha_m}</math> 的 <math>k</math> 个小模数的同余方程。

如果 <math>n</math> 是奇数（即没有因子 2 ，全部质因子都是奇质数），则由上一节可知：

这 <math>m</math> 个小模数的同余方程中，解都是成对出现的，二次剩余有 <math>\tfrac{\varphi(p^\alpha)}{2}</math> 个。
因此如果每个小模数同余方程都有解，大模数的同余方程中，解是 <math>2^m</math> 一组出现的，二次剩余有 <math>\tfrac{\varphi(p_1^{\alpha_1})}{2} \cdot \tfrac{\varphi(p_2^{\alpha_2})}{2} \cdot\cdots\cdot \tfrac{\varphi(p_m^{\alpha_m})}{2} = \tfrac{\varphi(n)}{2^m}</math> 个。

同时，二次非剩余的数量就有剩下的 <math>(1-\tfrac{1}{2^m}) \varphi(n)</math> 个。

每个二次剩余的平方根有 <math>2^m</math> 个。


{{同余理论}}