title: 二次剩余
date: 2019-08-27 00:10:46
tags: 数论

一、定义（Quadratic_residue）

一个整数X对另一个整数p的二次剩余 d

注意这边的取模是 $X^2$ 和 d 都要对p取模噢 eg. $3^2\equiv 2(mod7)$,我们称 2是7的二次剩余

当存在某个 $X^2\equiv d(modp)$ 成立时，称"d是模p的二次剩余"

注意：二次剩余 指的是 d，是$X^2$除以p得到的余数

当对任意不成立时，称"d是模p的二次非剩余"

通俗一点 就是在模p情况下 d能不能开方(带模），能 那就是p的二次剩余

就是 d在模p的情况下 会不会是某个数的平方

二、关于n的所有二次剩余

我们注意到 $x^2\%n\equiv (n-x{)}^2\%n$

可以证明：

$(n-x{)}^2=n^2+x^2-2\ast n\ast x=x^2\%n$

eg. $3^2\%10=7^2\%10$

所以 关于整数n的二次剩余的个数不可能超过 n/2+1

两个二次剩余的乘积必然还是二次剩余

为了得到关于一个整数p的所有二次剩余，我们可以直接计算 1，2，…，p-1的平方 模p的余数

三、性质

1.质数的二次剩余

对于质数2，每个整数都是它的二次剩余

因为任意整数a 对2取模要么时0 要么是1，而 0和1都是可开方的 就存在这样的X满足条件啦

对于奇质数p：能满足"d是模p的二次剩余"的d共有 (p+1)/2 （包括0）,此外是(p-1)/2个二次非剩余

分别为 $0^2,1^2,...,(\frac{p-1}{2}-1{)}^2,(\frac{p-1}{2}{)}^2$

eg. p=7时有 $0^2\equiv 0(mod7),1^2\equiv 1(mod7),2^2\equiv 4(mod7),3^2\equiv 2/9(mod7)$

证明：不是，为啥 $p\nmid (u-v)$ ？？？

大概是 素数p整除两个数的乘积，必整除其中的一个，u-v不可能是p的倍数（否则 u=v）

不对…唔…先等等 ————————————————————分割线

对于所有的 $x^2$ ,假设有 u≠v ,且 $u^2\equiv v^2(modp)$ 则 $p|(u^2-v^2)$ ,即 $p|(u-v)(u+v)$ ,容易知道， $p\nmid (u-v)$ , $p|(u+v)$ ,所以由 $u+v\equiv 0(modp)$ ,反之也成立，所以共有(p-1)/2中互不相同的平方，就可以对应所有有解的x，且同一个d还一定存在两个互为相反数的解

其实就我的理解来看：使方程有解的d 是有(p-1)/2 个的

若方程有解，恰好是两个解，且这两个解的和为p，回到了上面的 $x^2\%n\equiv (n-x{)}^2\%n$

当我们不把0考虑进去时，只考虑乘法群，则有：每个二次剩余的乘法逆元仍然是二次剩余；二次非剩余的乘法逆元仍然是二次非剩余

另外规定如果 a 是模 p 的二次剩余/二次非剩余，那么与 a 模 p 同余的数也是模 p 的二次剩余/二次非剩余。

对于 p 的倍数，规定它既不是模 p 的二次剩余，也不是模 p 的二次非剩余。

应用二次互反律可以知道，当p模4余1时，-1是p的二次剩余；如果p模4余3，那么，-1是p的二次非剩余。

1.二次剩余乘以二次剩余的结果是二次剩余(两个平方数的乘积仍然是平方数)

2.二次非剩余乘以二次非剩余的结果是二次剩余

3.二次剩余乘以二次非剩余的结果是二次非剩余

2.证明如下：

我们随意取7的一个二次剩余（0，1，2，4），例如我们取2，与1，…，p-1序列相乘

&1 * 2 = 2 （mod 7) → 2 &（二次剩余 *二次剩余 = 二次剩余）

&2 * 2 = 4 （mod 7) → 4 &

3 * 2 = 6 （mod 7) → 6 (二次剩余 * 二次非剩余 = 二次非剩余)

&4 * 2 = 8 （mod 7) → 1 &

5 * 2 = 10 （mod 7) → 3

6 * 2 = 12 （mod 7) → 5

左右两边的二次剩余个数相同，均为3个

3.的证明如下：

取7的二次非剩余3

&1 * 3 = 3 （mod 7) → 3

&2 * 3 = 6 （mod 7) → 6

3 * 3 = 9 （mod 7) → 2&

&4 * 3 = 12 （mod 7) → 5 (二次剩余 * 二次非剩余 = 二次非剩余)

5 * 3 = 15 （mod 7) → 1&

6 * 3 = 18 （mod 7) → 4& （二次非剩余 * 二次非剩余 =二次剩余）

我们可以由此引出勒让德符号(Legendre symbol)

四、勒让德符号

$\left(\frac{a}{p}\right)=\{\begin{array}{l}\text{0 如果}a\equiv 0\left(modp\right)\\ +\text{1 如果}a\not\equiv 0\left(modp\right),\text{且对于某个整数}x,x^2\equiv a\left(modp\right)\\ -\text{1 如果不存在整数}x,\text{使得}{x}^2\equiv a\left(modp\right)\end{array}$

1.性质

• 是一个完全积性函数， $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ （即可以进一步理解为 上面1.2.3. 便于记忆，可记作 正正得正，负负得正）

• 如果$a\equiv b(modp)$ ,则 $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$

• $\left(\frac{a^2}{p}\right)=1$ (既然它已经是平方了 那么自然就是二次剩余咯)

• 二次互反律的第一补充：

  $\left(\frac{-1}{p}\right)={\left(-1\right)}^{\frac{p-1}{2}}=\{\begin{array}{l}+\text{1 }ifp\equiv 1\left(mod4\right)\\ -\text{1 }ifp=3\left(mod4\right)\end{array}$

  第二补充：

  $\left(\frac{2}{p}\right)={\left(-1\right)}^{\frac{p^2-1}{8}}=\{\begin{array}{l}+\text{1 }ifp\equiv \text{1 }or\text{7 }\left(mod8\right)\\ -\text{1 }ifp\equiv \text{3 }or\text{5 }\left(mod8\right)\end{array}$

五、欧拉判别法(欧拉准则)

二次剩余的一个帅气的结论

参考链接

Cipolla’s algorithm