二次剩余
定义
令整数 $a$，$p$ 满足 $(a,p)=1$，若存在整数 $x$ 使得
$$
x^2\equiv a\pmod p
$$
则称 $a$ 为模 $p$ 的二次剩余，否则称 $a$ 为模 $p$ 的二次非剩余。并称$x$为$a$在模$p$下的平方根。
通俗一些，可以认为是求模意义下的 开平方 运算。对于更高次方的开方可参见 k 次剩余。
模$p$下的二次剩余
设$p$是奇素数
设$b \in {Z_p}$，则
$$
b^2 = 1 \iff b = \pm 1 (1,p-1)
$$
证明：
必要性：如果$b=\pm1$，必有$b^2=1$。
充分性：如果$b^2=1$，必有$b^2 \equiv 1 \pmod p$。
所以，$p \mid (b^2-1)$
$\implies p \mid(b-1)(b+1)$
$\implies p \mid(b-1)或p \mid (b+1)$
故而，$b \equiv \pm1 \pmod p$。即$b=\pm 1$。
设$b,c \in {Z_p^}$，则
$$
\begin{aligned}
b^2 = c^2 \iff b = \pm c \
\mid({Z_p^})^2\mid = (p - 1)/2
\end{aligned}
$$
Euler 判别法
对奇素数 $p$ 和满足 $(a,p)=1$ 的整数 $a$，
$$
a^{\frac{p-1}{2}}\equiv\begin{cases}
1 \pmod p, & (\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p,\
-1 \pmod p, & \text{otherwise}.\
\end{cases}
$$
即对上述的 $p$ 和 $a$，
- $a$ 是 $p$ 的二次剩余当且仅当 $a^{\frac{p-1}{2}}\equiv 1 \pmod p$.
- $a$ 是 $p$ 的二次非剩余当且仅当 $a^{\frac{p-1}{2}}\equiv -1 \pmod p$.
证明：
首先由 Fermat 小定理，有 $a^{p-1}\equiv 1\pmod p$，故
$$
\left(a^{\frac{p-1}{2}}+1\right)\left(a^{\frac{p-1}{2}}-1\right)\equiv 0\pmod p
$$
从而对任意满足 $(a,p)=1$ 的 $a$ 均有 $a^{(p-1)/2}\equiv \pm 1\pmod p$
另外由 $p$ 是奇素数，我们有：
$$
x^{p-1}-a^{\frac{p-1}{2}}={\left(x^2\right)}^{\frac{p-1}{2}}-a^{\frac{p-1}{2}}=(x^2-a)P(x)
$$
其中 $P(x)$ 是某个整系数多项式，进而：
$$
\begin{aligned}
x^p-x&=x\left(x^{p-1}-a^{\frac{p-1}{2}}\right)+x\left(a^{\frac{p-1}{2}}-1\right)\
&=(x^2-a)xP(x)+\left(a^{\frac{p-1}{2}}-1\right)x\
\end{aligned}
$$
由 同余方程的定理 5 可知，$a$ 是模 $p$ 的二次剩余当且仅当 $a^{(p-1)/2}\equiv 1\pmod p$. 进而 $a$ 是模 $p$ 的非二次剩余当且仅当 $a^{(p-1)/2}\equiv -1\pmod p$.
简易证明：
设$t=a^{\frac{p-1}{2}}$，则$t^2=a^{p-1}$。根据Fermat 小定理有，
$$
t^2=a^{\varphi(p)}=1，
$$
所以，$t=\pm 1$，即$a^{\frac{p-1}{2}}=\pm 1$
模$p^k$下的二次剩余
设$p$是奇素数，k是正整数
设$b \in {Z_{p^k}}$，则
$$
b^2 = 1 \iff b = \pm 1 (1,p-1)
$$
证明：
必要性：如果$b=\pm1$，必有$b^2=1$。
充分性：如果$b^2=1$，必有$b^2 \equiv 1 \pmod {p^k}$。
所以，${p^k} \mid (b^2-1)$
$\implies {p^k} \mid(b-1)(b+1)$
$\implies p \mid(b-1)(b+1)$
$\implies p \mid(b-1)或p \mid (b+1)$
$\implies {p^k} \mid(b-1)或{p^k} \mid (b+1)$
故而，$b \equiv \pm1 \pmod {p^k}$。即$b=\pm 1$。
设$b,c \in {Z_{p^k}^}$，则
$$
\begin{aligned}
b^2 = c^2 \iff b = \pm c \
\mid({Z_{p^k}^})^2\mid = \varphi(p^k)/2
\end{aligned}
$$
E.g：
$$
\begin{aligned}
&\mid({Z^_9}^2) \mid = \frac{\varphi(9)}{2}=\frac{3\varphi(3)}{2}=\frac{3 \times2}{2}=3 \
&\mid({Z^_{25}}^2) \mid = \frac{\varphi(25)}{2}=\frac{5\varphi(5)}{2}=\frac{5 \times4}{2}=10
\end{aligned}
$$
判别方法
设$p$是奇素数，$a \in {Z^_{p^k}}$，则
$$
\begin{aligned}
&①a^{\frac{\varphi(p^k)}{2}} = \pm 1 \
&②a \in (Z^{p^})^2 \implies a^{\frac{\varphi(p^k)}{2}} = 1 \
&③a \notin (Z^{p^*})^2 \implies a^{\frac{\varphi(p^k)}{2}} = -1
\end{aligned}
$$
- $a$是模$p^k$下二次剩余 $\iff a$是模$p$下二次剩余
证明：
充分性：如果$a \in (Z^_{p^})^2$，则$a \in {Z^*_{p^k}}$，所以$\gcd(a,p)=1$。
且存在$b \in {Z^*_{p^k}}$，使得$b^2 \equiv a \pmod {p^k}$
所以。$b^2 \equiv a \pmod p$
故而，$a \in (Z^*_p)^2$
必要性：若$a \in (Z^_{p^})^2$，假设$a$是模$p^k$下二次非剩余，则
$a^{\frac{\varphi(p^k)}{2}} \equiv -1 \pmod {p^k}$
所以，$a^{\frac{\varphi(p^k)}{2}} \equiv -1 \pmod {p}$
$a^{\frac{p^{k-1}\varphi(p^k)}{2}} \equiv -1 \pmod p$
根据费马小定理，
$a^{\frac{p-1}{2}} \equiv -1 \pmod p$。故而，$a \notin (Z^*_p)^2$，矛盾！
模$n$下的二次剩余
中国剩余映射（Chinese Remainder Mapping）
定义：
中国剩余映射是一种从整数集合Z到多个小模数组成的笛卡尔积Z/n₁Z × Z/n₂Z × … × Z/nkZ的环同态映射。其前提条件是这些模数$n_1, n_2, \dots, n_k$两两互质，即任意两个不同模数之间的最大公约数为1。
结构：
中国剩余映射通常写作CRT(n₁, n₂, …, nk)，它通过将整数a分别取模于每个ni，得到一个元组(a mod n₁, a mod n₂, …, a mod nk)。当n = n₁×n₂×…×nk时，由于模数两两互质，根据中国剩余定理，这种映射是可逆的，即存在唯一的一个整数a在模n意义下与该元组对应。
数学表达：
对于一个整数a，有：
$$
CRT: a \implies (a \mod n_1, a \mod n_2, \dots, a \mod n_k)
$$
反之，当给定一个元组(a₁, a₂, …, ak)，其中每个ai满足0 ≤ ai < ni，且n = ∏ni，则存在唯一的整数a mod n使得对于所有i，有$a \equiv a_i \pmod {n_i}$。
设$n>1$是奇数，且$n=p_1^{k_1} \times \dots \times p_m^{k_m}$
$$
\begin{aligned}
&a \in (Z_n^)^2 \iff a_i \in (Z_{p_i^{k_i}}^)^2,i = 1, \dots,m \
\end{aligned}
$$
证明：
充分性：
如果$a \in (Z_n^)^2$，设$a=b^2,b \in Z_n^$。
根据中国剩余映射$\tau (b)= (b_1,\dots,b_m)$，则$\tau(b^2)=(b_1^2,\dots,b_m^2)$
于是有，$(a_1,\dots,a_m)=\tau(a)=\tau(b^2)=(b_1^2,\dots,b_m^2)$。
所以，$a_i = b_i^2,i=1,\dots,m$，即$a_i$是模$p_i^{k_i}$下的二次剩余：$a_i \in (Z^*_{p^{k_i}_i})^2$
必要性：
若$a_i \in (Z^_{p^{k_i}i})^2，i=1,\dots,m$，设$a_i = b_i^2，b_i \in Z{p_i^{k_i}}^$。
设$b:= \tau^{-1}(b_i,\dots,b_m)$，则$\tau(b^2)=(b_1^2,\dots,b_m^2)=(a_1,\dots,a_m)=\tau(a)$。
故而，$\tau(b^2)=\tau(a)$
因为中国剩余映射是双射，所以$a=b^2$
故而$a$是模$n$下的二次剩余：$a \in (Z_n^*)^2$
$$
\begin{aligned}
&\mid (Z_n^)^2 \mid = \frac{\varphi(n)}{2^m} \
&设a \in (Z_n^)^2,则 a恰好有2^m个平方根
\end{aligned}
$$
E.g：
$Z^_{45}$里的二次剩余数量
$$
\begin{aligned}
45 = 3^2\times 5，&此时m=2。二次剩余的数量为\
&\mid(Z^_{45})^2\mid = \frac{\varphi(45)}{2^2}=6
\end{aligned}
$$
模$p$下$-1$的平方根
| 二次剩余数量 | 二次剩余平方根 | |
|---|---|---|
| $p$ | $\frac{\varphi(p)}{2}$（集合大小的一半） | 2个 |
| $p^k$ | $\frac{\varphi(p^k)}{2}$（集合大小的一半） | 2个 |
| $n$ | $\frac{\varphi(n)}{2^m}$（集合大小的$\frac{1}{2^m}$） | $2^m$个 |
判断-1（p-1）是模$p$的二次剩余
- $p \equiv 1 \pmod 4 \iff -1 \in (Z_p^*)^2$
E.g:
$p=13$，$-1 \in (Z_{13}^*)^2$，因为$13 \equiv 1 \pmod 4$
证明：
$$
\begin{aligned}
p \equiv 1 \pmod 4 &\iff 4\mid(p-1) \
&\iff 2\mid \frac{p-1}{2} \
&\iff \frac{p-1}{2}是偶数 \
&\iff (-1)^{\frac{p-1}{2}} \equiv 1 \pmod p \
&\iff -1 \in (Z_p^*)^2
\end{aligned}
$$
$(-1)^{\frac{13-1}{2}} \equiv 1 \pmod {13}$（欧拉公式验证）
证明：
$$
\begin{aligned}
p \equiv 3 \pmod 4 &\iff p=4q+3 \
&\iff p-1 = 4q+2 \
&\iff \frac{p-1}{2}=2q+1 是个奇数 \
&\iff (-1)^{\frac{p-1}{2}} \equiv -1 \pmod p \
&\iff -1 \in Z^_p / (Z_p^)^2
\end{aligned}
$$
模$p$下构造-1的平方根
$$
\begin{aligned}
&设p \equiv 1 \pmod 4 , c \in Z^_p / (Z_p^)^2 \
&令 b:= c^{\frac{p-1}{4}} \pmod p，则 b^2 \equiv -1 \pmod p \
\
& b^2 \equiv (c^{\frac{p-1}{4}})^2 \equiv c^{\frac{p-1}{2}} \equiv -1 \pmod p
\end{aligned}
$$
E.g: $p=13，c=2 \in Z^_p / (Z_p^)^2$
$$
\begin{aligned}
&b:= c^{\frac{13-1}{4}} \equiv 2^{\frac{13-1}{3}} \equiv 2^3 \equiv 8 \pmod {13} \
& 8^2 \equiv 64 \equiv 12 \equiv -1 \pmod {13}
\end{aligned}
$$
费马二平方定理（Fermat’s two squares theorem）
设$p$是奇素数，则
$p \equiv 1 \pmod 4 \iff p=s^2+t^2 ,s,t \in Z$
E.g:
$13 = 2^2 + 3^2$
$5=1^2+2^2$
$17=1^2+4^2$