还没写好，可能这几天补好

二次剩余

二次剩余，常被称为模意义开根，是求满足$n\equiv x^2(mod\ m)$的$x$的值。

首先需要注意，并不是对每个$n$而言上面的方程都有解。如果上面的方程有非零解，我们称$n$是模$m$的二次剩余。如果方程无解，则称$n$是模$m$的二次非剩余。

为了方便讨论，我们引入勒让德符号：

$ ()={ \[\begin{aligned} 1 & \, 如果a是p的二次剩余\\ 0 & \, 如果a\ mod\ p=0\\ {-1} & \, 如果a是p的二次非剩余 \end{aligned}\]

. $

接下来讨论如何求解二次剩余，一般只考虑奇素数的情况。

欧拉准则

当模数是奇素数$p$且与$a$互质时，由费马小定理，$a^{p-1}\equiv1\ (mod\ p)$，设$p=2q+1$，

则有$a^{2q}\equiv 1\ (mod\ p)$，于是$(a^q-1)(a^q+1)\equiv 0\ (mod\ p)$，故$a^q\equiv \pm1 (mod\ p)$，即$a^{\frac{p-1}{2}}\equiv\pm1\ (mod\ p)$。

所以只要$a、p$互质，$a^{\frac{p-1}{2}}$在模$p$意义下就只可能等于$1$或${-1}$。到底是$1$还是${-1}$，这与二次剩余紧密相关，实际上，有以下公式：

$(\frac{a}{p})\equiv a^{\frac{p-1}{2}}(mod\ p)$

以上公式被称为欧拉准则，我们只需要计算$a^{\frac{p-1}{2}}$即可判断$a$是否为$p$的二次剩余。

这里实际上有一个证明：“$a$是模$p$的二次剩余”是"$a^{\frac{p-1}{2}}\equiv 1(mod\ p)$"的充要条件。

但是目前没时间写，可能过两天再写。咕咕咕

由此可以有一个推论：当$\frac{p-1}{2}$是奇数时，如果$a$是模$p$的二次剩余，则${-a}$是mo$p$的二次非剩余。相反，当$\frac{p-1}{2}$是偶数时，如果$a$是模$p$的二次剩余，则${-a}$也是模$p$的二次剩余。