二次剩余

高次剩余

定义：

• 高次剩余：设 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}$$
  1. a 是模 p 的二次剩余的充要条件是 $$a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$$
  2. 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 互素的整数。则：
  1. 若 $$a \equiv b \pmod{p}$$，则：$$\displaystyle (\frac{a}{p}) = (\frac{b}{p})$$
  2. $$\displaystyle (\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$$
  3. $$\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})$$