二次剩余

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

一、定义（Quadratic_residue）

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

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

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

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

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

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

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

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

我们注意到 $x^2\ \%\ n≡(n-x)^2\ \%\ n$x2 % n≡(n−x)2 % n

可以证明：

$(n-x)^2=n^2+x^2-2 * n * x=x^2\ \% n$(n−x)2=n2+x2−2∗n∗x=x2 %n

eg. $3^2\ \%10=7^2\ \%10$32 %10=72 %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$02,12,...,(2p−1​−1)2,(2p−1​)2

eg. p=7时有 $0^2≡0(mod\ 7),1^2≡1(mod\ 7),2^2≡4(mod\ 7),3^2≡2/9(mod\ 7)$02≡0(mod 7),12≡1(mod 7),22≡4(mod 7),32≡2/9(mod 7)

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

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

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

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

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

若方程有解，恰好是两个解，且这两个解的和为p，回到了上面的 $x^2\ \%\ n≡(n-x)^2\ \%\ n$x2 % n≡(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{cases} \text{0 如果}a\equiv 0\left( mod\,\,p \right)\\ +\text{1 如果}a\not \equiv 0\left( mod\,\,p \right) ,\text{且对于某个整数}x,x^2\equiv a\left( mod\,\,p \right) \,\,\\ -\text{1 如果不存在整数}x,\text{使得}x^2\equiv a\left( mod\,\,p \right)\\\end{cases}$(pa​)=⎩⎪⎨⎪⎧​0 如果a≡0(modp)+1 如果a​≡0(modp),且对于某个整数x,x2≡a(modp)−1 如果不存在整数x,使得x2≡a(modp)​

1.性质

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

• 如果$a ≡ b (mod\ p)$a≡b(mod p) ,则 $\left(\frac{a}{p} \right) =\left( \frac{b}{p} \right)$(pa​)=(pb​)

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

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

  $\left( \frac{-1}{p} \right) =\left( -1\right) ^{\frac{p-1}{2}}=\begin{cases} +\text{1 }if\,\,p\equiv 1\left( mod\,\,4 \right)\\ -\text{1 }if\,\, p=3\left( mod\,\,4 \right)\\\end{cases}$(p−1​)=(−1)2p−1​={+1 ifp≡1(mod4)−1 ifp=3(mod4)​

  第二补充：

  $\left( \frac{2}{p} \right) =\left( -1\right) ^{\frac{p^2-1}{8}}=\begin{cases} +\text{1 }if\,\,p\equiv \text{1 }or\,\,\text{7 }\left(mod\,\,8 \right)\\ -\text{1 }if\,\,p\equiv \text{3 }or\,\,\text{5 }\left( mod\,\,8 \right)\\\end{cases}$(p2​)=(−1)8p2−1​={+1 ifp≡1 or7 (mod8)−1 ifp≡3 or5 (mod8)​

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

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

参考链接

Cipolla’s algorithm