二次剩余
| 二次剩余 | |
|---|---|
| 术语名称 | 二次剩余 |
| 英语名称 | quadratic residue |
| 二次非剩余 | |
|---|---|
| 术语名称 | 二次非剩余 |
| 英语名称 | quadratic nonresidue |
一个数是一个模数下的二次剩余(quadratic residue)指这个数与任意完全平方数在该模数下同余。 相反地，若一个数不与任何完全平方数同余，称其为二次非剩余(quadratic nonresidue)。
简单地说，“相等意义下，整数的平方”就叫做“完全平方数”的话，“同余意义下，整数的平方”就叫做“二次剩余”。
定义
对整数 [math]\displaystyle{ a }[/math] ，以及大于 1 的正整数 [math]\displaystyle{ n }[/math] ， [math]\displaystyle{ \operatorname{gcd}(a, n) = 1 }[/math] ，若 [math]\displaystyle{ (\exists x \in \mathbb{Z})(x^2 \equiv a \pmod n) }[/math] ，则称 [math]\displaystyle{ a }[/math] 是一个模 [math]\displaystyle{ n }[/math] 的二次剩余(quadratic residue modulo [math]\displaystyle{ n }[/math])，并称 [math]\displaystyle{ x }[/math] 是 [math]\displaystyle{ a }[/math] 在模 [math]\displaystyle{ n }[/math] 下的平方根(square root of [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math])；否则，称 [math]\displaystyle{ a }[/math] 是一个模 [math]\displaystyle{ n }[/math] 的二次非剩余(nonquadratic residue modulo [math]\displaystyle{ n }[/math])。
注：有的定义不要求互质。
使用模 n 剩余类乘法群的集合记号 [math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^* }[/math] 表达所有与 [math]\displaystyle{ n }[/math] 互质的剩余类的集合，记号 [math]\displaystyle{ ((\mathbb{Z}/n\mathbb{Z})^*)^2 }[/math] 表达其中全体元素平方后所得元素的集合。由于乘法封闭，有 [math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^* \supseteq ((\mathbb{Z}/n\mathbb{Z})^*)^2 }[/math] 。因此，可以对应二次剩余所在剩余类的集合为 [math]\displaystyle{ ((\mathbb{Z}/n\mathbb{Z})^*)^2 }[/math] ，二次非剩余所在剩余类的集合为 [math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^* \setminus ((\mathbb{Z}/n\mathbb{Z})^*)^2 }[/math]
意义
一般的二次同余方程 [math]\displaystyle{ a x^2 + b x + c \equiv 0 \pmod n , n \not\mid a }[/math] ，可在保持解不变的前提下，全式同乘以 [math]\displaystyle{ 4a }[/math] 再两侧加上 [math]\displaystyle{ b^2 }[/math] ，直接配方为 [math]\displaystyle{ (2ax + b)^2 \equiv b^2 -4ac \pmod{4an} }[/math] ，因此有解问题等价于 [math]\displaystyle{ y^2 \equiv \Delta \pmod {4an} }[/math] 是否有解。
通过研究 [math]\displaystyle{ \Delta = b^2-4ac }[/math] 是否是 [math]\displaystyle{ 4an }[/math] 的二次剩余，即可知道原同余方程的解的情况。
性质
在任意大于 1 的整数模下， 1 都是二次剩余，至少有 1 这个解。
首先模数为 2 的情况，所有的数都和 0 或 1 同余， 1 本身就是二次剩余。
对更大的数，同余关系中全体的二次剩余可以通过 [math]\displaystyle{ 0^2, 1^2, 2^2, \dots, (n-1)^2 }[/math] 得到，甚至因为 [math]\displaystyle{ a^2\equiv (n-a)^2 \pmod n }[/math] ，只需要考虑其中的一半。
模数为奇质数
欧拉准则
对质数 [math]\displaystyle{ p }[/math] ，以及任意整数 [math]\displaystyle{ a }[/math] ，且 [math]\displaystyle{ p \not\mid a }[/math] ，有 [math]\displaystyle{ a ^ {\frac{p-1}{2}} \equiv \begin{cases} +1 &, \text{是二次剩余} \\ -1 &, \text{是二次非剩余} \\ \end{cases} \pmod p }[/math]
推论
由欧拉准则可知，
- [math]\displaystyle{ 1, 2, \dots, p-1 }[/math] 中，二次剩余和二次非剩余必各占一半。
- 任意两个二次剩余相乘都是二次剩余，任意两个二次非剩余相乘也是二次剩余，只有一个二次剩余和一个二次非剩余相乘时，得到二次非剩余。
- 如果把 [math]\displaystyle{ 1, 2, \dots, p-1 }[/math] 分成两个非空集合 [math]\displaystyle{ C_1, C_2 }[/math] ，使得任意 [math]\displaystyle{ C_1 C_1 \subseteq C_1 }[/math] 、 [math]\displaystyle{ C_2 C_2 \subseteq C_2 }[/math] 、 [math]\displaystyle{ C_1 C_2 \subseteq C_2 }[/math] ，则有唯一解 [math]\displaystyle{ C_1 }[/math] 取二次剩余集合、 [math]\displaystyle{ C_2 }[/math] 取二次非剩余集合。
- 考虑模逆的话，二次剩余的模逆都是二次剩余，非二次剩余的模逆都是非二次剩余。
且对 -1 计算 [math]\displaystyle{ \tfrac{p-1}{2} }[/math] 可知，
[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ p }[/math] 的二次剩余，其平方根一定是任意二次非剩余 [math]\displaystyle{ c }[/math] 的 [math]\displaystyle{ c^\tfrac{p-1}{4} }[/math] 。
模数为奇质数幂
对奇质数幂 [math]\displaystyle{ p^k }[/math] 仍有 [math]\displaystyle{ b \equiv 1 \pmod{p^k} \rightarrow b \equiv 1 \pmod{p^k} \lor b \equiv -1 \pmod{p^k} }[/math] 。因此可以推出 [math]\displaystyle{ b \equiv c \pmod{p^k} \rightarrow b \equiv c \pmod{p^k} \lor b \equiv -c \pmod{p^k} }[/math] ，也就是说平方根也会有且仅有两个一组地存在。
因此可以推测平方映射把含有 [math]\displaystyle{ \varphi(p^k) }[/math] 个元素的 [math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^* }[/math] 两个一组地映射到 [math]\displaystyle{ ((\mathbb{Z}/n\mathbb{Z})^*)^2 }[/math] 中，后者的元素个数是 [math]\displaystyle{ \tfrac{\varphi(p^k)}{2} }[/math] 。换句话说，奇质数幂时，二次剩余有 [math]\displaystyle{ \tfrac{\varphi(p^k)}{2} }[/math] 个，相应地二次非剩余也有 [math]\displaystyle{ \tfrac{\varphi(p^k)}{2} }[/math] 个。
类似于欧拉准则，我们可以得到：
对质数 [math]\displaystyle{ p }[/math] 及正整数 [math]\displaystyle{ k }[/math]，以及任意整数 [math]\displaystyle{ a }[/math] ，且 [math]\displaystyle{ p \not\mid a }[/math] ，有 [math]\displaystyle{ a ^ {\frac{\varphi(p^k)}{2}} \equiv \begin{cases} +1 &, \text{是二次剩余} \\ -1 &, \text{是二次非剩余} \\ \end{cases} \pmod p }[/math] 其中 [math]\displaystyle{ \varphi(p^k) = (p-1) p^{k-1} }[/math] 是欧拉函数。
可以推出 [math]\displaystyle{ a }[/math] 是模 [math]\displaystyle{ p^k }[/math] 的二次剩余，当且仅当 [math]\displaystyle{ a }[/math] 是模 [math]\displaystyle{ p }[/math] 的二次剩余。
模数为奇数
对模数为一般合数的同余方程，根据中国剩余映射，一定可以将其拆解为多个质数幂下分别的同余方程，并分别求出多个解，最终通过解的组合进行逆映射得到原方程的解。因此可记 [math]\displaystyle{ n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m} }[/math] ，同余方程可以分解成模 [math]\displaystyle{ p_1^{\alpha_1}, p_2^{\alpha_2}, \dots, p_m^{\alpha_m} }[/math] 的 [math]\displaystyle{ k }[/math] 个小模数的同余方程。
如果 [math]\displaystyle{ n }[/math] 是奇数（即没有因子 2 ，全部质因子都是奇质数），则由上一节可知：
这 [math]\displaystyle{ m }[/math] 个小模数的同余方程中，解都是成对出现的，二次剩余有 [math]\displaystyle{ \tfrac{\varphi(p^\alpha)}{2} }[/math] 个。 因此如果每个小模数同余方程都有解，大模数的同余方程中，解是 [math]\displaystyle{ 2^m }[/math] 一组出现的，二次剩余有 [math]\displaystyle{ \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]\displaystyle{ (1-\tfrac{1}{2^m}) \varphi(n) }[/math] 个。
每个二次剩余的平方根有 [math]\displaystyle{ 2^m }[/math] 个。