第四章 二次剩余

第四章 二次剩余

4.1 二次剩余

• 引入：

  • 线性同余式：$ax+b\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 有解 $⟺(a,m)=1$

  • 二次同余式：
    $$\begin{array}{rl}& a{x}^2+bx+c\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)\\ ⟹& x_0^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}m)\\ ⟹& x_0^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}{p}^2),其中p^2\mid \mid m\\ ⟹& x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}p)(由Hensel引理)\end{array}$$

• 定义：设 $m>1$，若 $x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}m),(n,m)=1$ 有解，则 $n$ 叫做模数 $m$ 的二次剩余；若无解，则 $n$ 叫做模数 $m$ 的二次非剩余。

• 定理一：设 $p$ 为奇素数，则在模 $p$ 的任一个缩系 $1,2,...,p-1$ 中，二次剩余与二次非剩余的个数各有 $\frac{p-1}{2}$ 个。特别地，
  $$1={⟨1^2⟩}_p,{⟨2^2⟩}_p,...,{⟨{\left(\frac{p-1}{2}\right)}^2⟩}_p$$
  为模数 $p$ 的缩系中的全部二次剩余。

• 定理二：

  • 若 $n$ 为 $p$ 的二次剩余，则充要条件为

  $$n^{\frac{p-1}{2}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

  • 若 $n$ 为 $p$ 的二次非剩余，则充要条件为

  $$n^{\frac{p-1}{2}}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

4.2 勒让德符号

引入易于计算的判别二次剩余方法

• 定义：设 $p$ 为奇素数，$(p,n)=1$，则令勒让德符号 $\left(\frac{n}{p}\right)$
  $$\left(\frac{n}{p}\right)=\{\begin{array}{r}\begin{array}{rl}1,& n是p的二次剩余\\ -1,& n是p的二次非剩余\end{array}\end{array}$$

  • 推论一：设 $p$ 是一个奇素数，$p\nmid n$，则
    $$\left(\frac{n}{p}\right)\equiv n^{\frac{p-1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$
    显然 $\left(\frac{1}{p}\right)\equiv 1=1$，可额外定义 $\left(\frac{0}{p}\right)=0$

  • 推论二：设 $n\equiv n^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 时，有 $\left(\frac{n}{p}\right)=\left(\frac{n^{\prime }}{p}\right)$

• 定理一：设给定 $p$ 为奇素数，则勒让德符号 $\left(\frac{n}{p}\right)$ 是一个完全积性函数

  • 故当 $n=\pm 2^m{q}_1^{l_1}...q_s^{l_s}$ 时，其中 $2<q_1<...<q_s$ 是素数时，有
    $$\left(\frac{n}{p}\right)=\left(\frac{\pm 1}{p}\right){\left(\frac{2}{p}\right)}^m{\left(\frac{q_1}{p}\right)}^{l_1}...{\left(\frac{q_s}{p}\right)}^{l_s}$$

• 定理二：设 $p$ 为奇素数，有
  $$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{l}\begin{array}{rl}1,& 若p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)\\ -1,& 若p\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)\end{array}\end{array}$$

• 定理三：设 $p$​ 为奇素数，有
  $$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{l}\begin{array}{rl}1,& 若p\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}8)\\ -1,& 若p\equiv \pm 3(\mathrm{m}\mathrm{o}\mathrm{d}8)\end{array}\end{array}$$

4.3 高斯引理

• 定理一(高斯引理)：设 $p$ 为奇素数，$(p,n)=1$，且 $\frac{p-1}{2}$ 个数
  $${⟨n⟩}_p,{⟨2n⟩}_p,...,{⟨\frac{(p-1)n}{2}⟩}_p$$
  中有 $m$ 个大于 $\frac{p}{2}$，则有
  $$\left(\frac{n}{p}\right)=(-1{)}^m$$

• 定义：。。。

• 定理二：。。。

4.4 二次互反律

• 定理(二次互反律)：设 $p,q>2$ 是两个素数，$p\ne q$，则
  $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{(p-1)(q-1)}{4}}$$

  • 推论：$\left(\frac{p}{q}\right)=(-1{)}^{\frac{(p-1)(q-1)}{4}}\cdot \left(\frac{q}{p}\right)$
  • 应用：可计算 $\left(\frac{n}{p}\right)$ 或确定给定 $n$ 是哪些素数 $p$ 的二次(非)剩余。

  $例题$：计算 $\left(\frac{438}{593}\right)$，其中 $593$ 为素数

  解：
  $$\begin{gathered} \because 438=2\times 3\times 73,故\left(\frac{438}{593}\right)=\left(\frac{2}{593}\right)\left(\frac{3}{593}\right)\left(\frac{73}{593}\right) \\ \because 593\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)\therefore \left(\frac{2}{593}\right)=1 \\ \because \left(\frac{3}{593}\right)=(-1{)}^{\frac{(3-1)(593-1)}{4}}\left(\frac{593}{3}\right)=\left(\frac{2}{3}\right) \\ \because \left(\frac{73}{593}\right)=(-1{)}^{\frac{(73-1)(593-1)}{4}}\left(\frac{593}{73}\right)=\left(\frac{9}{73}\right) \\ \therefore \left(\frac{438}{593}\right)=\left(\frac{2}{3}\right)\left(\frac{9}{73}\right)=-1\cdot 1=-1 \end{gathered}$$
  故 $438$ 是模数 $593$ 的二次非剩余

4.5 二次剩余理论应用举例

4.6 二次同余式的解法和解数

当 $p$ 太大时，求解 $\left(\frac{n}{p}\right)$

• 定理一：对于奇素数 $p$，设 $\left(\frac{n}{p}\right)=1$，则有

  1. 当 $p\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$ 时，二次剩余 $n$ 的解为 $\pm n^{\frac{p+1}{4}}$
  2. 当 $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)$ 时，二次剩余 $n$ 的解为 $\{\begin{array}{l}\begin{array}{rlrl}& \pm n^{\frac{p+3}{8}},& & 若n^{\frac{p-1}{4}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)\\ & \pm \left(\frac{p-1}{2}\right)!\cdot n^{\frac{p+3}{8}},& & 若n^{\frac{p-1}{4}}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)\end{array}\end{array}$

• 定理二：设 $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)$，$\left(\frac{n}{p}\right)=1$，$\left(\frac{m}{p}\right)=-1$，则二次剩余 $n$ 有解
  $$\pm n^{\frac{h+1}{2}}{m}^{s_k}$$
  其中 $h$ 满足 $p=2^{k}h+1$，$2\nmid h$，$s_k\ge 0$ 是某个数。

• 定理三(关于解数)：设素数 $p$，$p\nmid n$，对于二次同余式
  $$x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}{p}^l),l>0$$
  在 $p>2$ 时，有 $1+\left(\frac{n}{p}\right)$ 个解。在 $p=2$ 是，有三种情况

  1. 当 $l=1$ 时，有一个解
  2. 当 $l=2$ 时，解数为 $\{\begin{array}{l}\begin{array}{rl}2,& 若n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)\\ 0,& 若n\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)\end{array}\end{array}$
  3. 当 $l>2$ 时，解数为 $\{\begin{array}{l}\begin{array}{rl}4,& 若n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)\\ 0,& 若n\not\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)\end{array}\end{array}$

4.7 雅可比符号

避开勒让德符号分解 $n$ 的缺点

• 定义：设 $m$ 为一个正奇数，$m=p_1{p}_2...p_s(i=1,...,s)$ 是素数，$(m,n)=1$，则雅可比符号为
  $$\left(\frac{n}{m}\right)=\prod _{i=1}^s\left(\frac{n}{p_i}\right)$$

• 定理一：设 $m_1.m_2$ 为正奇数

  1. 若 $n\equiv n^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 且 $(n,n^{\prime })=1$，则 $\left(\frac{n}{m}\right)=\left(\frac{n^{\prime }}{m}\right)$
  2. 若 $(n,m_1)=(n,m_2)=1$，则 $\left(\frac{n}{m_1}\right)\left(\frac{n}{m_2}\right)=\left(\frac{n}{m_1{m}_2}\right)$
  3. 若 $(n,m)=(n^{\prime },m)=1$，则 $\left(\frac{n}{m}\right)\left(\frac{n^{\prime }}{m}\right)=\left(\frac{n{n}^{\prime }}{m}\right)$

• 定理二：$\left(\frac{-1}{m}\right)=(-1{)}^{\frac{m-1}{2}}$

• 定理三：$\left(\frac{2}{m}\right)=(-1{)}^{\frac{m^2-1}{8}}$

• 定理四：设 $m,n$ 是两个奇素数，且 $(n,m)=1$，则
  $$\left(\frac{n}{m}\right)\left(\frac{m}{n}\right)=(-1{)}^{\frac{(m-1)(n-1)}{4}}$$

  注意当 $s>1$ 时，$\left(\frac{n}{m}\right)=1$ 时，$x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 不一定有解。

4.8 表素数为平方和

• 定义：设整合 $n$ 可表示成 $n=x^2+y^2$，若 $(x,y)=1$，则称 $n$ 能本原的表成二个平方和。
• 定理一：设 $p$ 是 $m$ 的一个奇素因子，$p$ 能表成二个平方和，$m$ 能本原的表成二个平方和，则 $\frac{m}{p}$ 也能本原的表成二个平方和。
• 定理二：$n^2+1$ 的每一个素因子都能表成二个平方的和。
• 定理三：每个形如 $4k+1$ 的素数都能表成二个平方的和，且表法唯一。

4.9 表正整数为平方和

一个奇素因子，$p$ 能表成二个平方和，$m$ 能本原的表成二个平方和，则 $\frac{m}{p}$ 也能本原的表成二个平方和。

• 定理二：$n^2+1$ 的每一个素因子都能表成二个平方的和。
• 定理三：每个形如 $4k+1$ 的素数都能表成二个平方的和，且表法唯一。

4.9 表正整数为平方和

• 定理：每一个正整数都能表成四个整数的平方和