高次剩余
定义：
- 高次剩余：设 m 是大于 1 的整数，a 是与 m 互素的整数，若 $$n (n \ge 2)$$ 次同余方程 $$x^n \equiv a \pmod{m}$$ 有解，则 a 叫做模 m 的 n 次剩余。否则，a 叫做模 m 的 n 次非剩余。
定理：
- g 是 m 的一个原根，a 是与 m 互素的整数。
- 则同余方程 $$x^n \equiv a \pmod{m}$$ 有解的充要条件是 $$gcd(n, \phi(m)) | ind_g a$$，并且如果有解，其解的个数恰好为 $$gcd(n, \phi(m))$$
定理：
- g 是 m 的一个原根，a 是与 m 互素的整数。
- 则 a 是模 m 的 n 次剩余的充要条件是 $$\displaystyle a^{\frac{\phi(m)}{d}} \equiv 1 \pmod{m}, d = gcd(n, \phi(m))$$
二次剩余
定义：
- 设 m 是大于 1 的整数，a 是与 m 互素的整数，若 $$x^2 \equiv a \pmod{m}$$ 有解，则 a 叫做模 m 的二次剩余，或平方剩余；否则，a 叫做模 m 的二次非剩余。
定理（二次剩余的欧拉判别条件）：
- 设 p 是奇素数，$$gcd(a, p) = 1$$，则对于同余方程 $$x^2 \equiv a \pmod{p}$$
- a 是模 p 的二次剩余的充要条件是 $$a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$$
- a 是模 p 的二次非剩余的充要条件是 $$a^{\frac{p-1}{2}} \equiv -1\pmod{p}$$
- 并且当 a 是模 p 的二次剩余时，同余方程恰有两个解。
定理：
- 设 p 是奇素数，则模 p 的缩系中二次剩余与非二次剩余的个数各为 $$\displaystyle \frac{p - 1}{2}$$，且 $$\displaystyle \frac{p - 1}{2}$$ 个二次剩余分别与序列 $$\displaystyle 1^2, 2^2, \cdots, (\frac{p - 1}{2})^2$$ 中的一个数同余，且仅与一个数同余。
勒让德符号
定义：
- 设 p 是奇素数，$$gcd(a, p) = 1$$，定义勒让德符号如下：
- $$\displaystyle (\frac{a}{p}) = \begin{cases} 1 & \text{若 a 是模 p 的二次剩余} \ -1 & \text{若 a 是模 p 的二次非剩余} \end{cases}$$
定理：
- 设 p 是奇素数，a 是与 p 互素的整数。
- 则：$$\displaystyle (\frac{a}{p}) \equiv a^{\frac{p-1}{2}} \pmod{p}$$
定理：
- 设 p 是奇素数，a 是与 p 互素的整数。则：
- 若 $$a \equiv b \pmod{p}$$，则：$$\displaystyle (\frac{a}{p}) = (\frac{b}{p})$$
- $$\displaystyle (\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$$
- $$\displaystyle \frac{a^2}{p} = 1$$
定理：
- 若 p 是奇素数，我们有 $$\displaystyle (\frac{-1}{p}) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 & \text{若 } p \equiv 1 \pmod{4} \ -1 & \text{若 } p \equiv 3\pmod{4}\end{cases}$$
定理（高斯引理）：
- 设 p 是奇素数，a 是与 p 互素的整数
- 如果下列 $$\displaystyle \frac{p-1}{2}$$ 个整数：$$\displaystyle a \cdot 1, a \cdot 2, a \cdot 3, \cdots, a \cdot \frac{p-1}{2}$$，模 p 后得到最小的正剩余中大于 $$\displaystyle \frac{p}{2}$$ 的个数是 m
- 则：$$\displaystyle (\frac{a}{p}) = (-1)^m$$
定理：
- 设 p 是奇素数，则有：
- $$\displaystyle (\frac{2}{p}) = (-1)^{\frac{p^2 -1}{8}} = \begin{cases} 1 & \text{若 } p \equiv \pm 1 \pmod{8} \ -1 & \text{若 } p \equiv \pm 3 \pmod{8}\end{cases}$$
定理（二次互反律）：
- 设 p, q 是奇素数，$$p \not= q$$，则：$$\displaystyle (\frac{p}{q})(\frac{q}{p}) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$
雅可比符号
定义：
- 设奇正数 $$m = p_1 p_2 \cdots p_r$$ 是奇素数 $$p_i (i = 1, 2, \cdots, r)$$ 的乘积，定义雅可比（Jacobi）符号如下：
- $$\displaystyle (\frac{a}{m}) = (\frac{a}{p_1})(\frac{a}{p_2})\cdots(\frac{a}{p_r})$$