【数论与组合数学 4】平方剩余、二次互反律

平方剩余、二次互反律

一、平方剩余

  1. 定义:设 p 为奇素数且 \(\mathsf{a \neq 0\ mod\ p}\) ,如果 a 在模 p 下是另一个数的平方,即 \(\mathsf{a \equiv b^{2}\ mod\ p}\) ,则称 a 为模 p 下的平方剩余,否则称 a 为平方非剩余。而二次同余式 \(\mathsf{x^{2}\equiv a\ mod\ p}\) 可能有 0—2 个解
  • 例子:

    \(\mathsf{p=5}\) 时,因为

    \(\mathsf{1^{2}\equiv 1\ mod\ 5 \qquad 2^{2}\equiv 4\ mod\ 5 \qquad 3^{2}\equiv 4\ mod\ 5 \qquad 4^{2}\equiv 1\ mod\ 5}\)

    则 1,4 是模 5 下的平方剩余,而 2,3 是模 5 下的平方非剩余

    \(\mathsf{p=7}\) 时,因为

    \(\mathsf{1^{2}\equiv 1\ mod\ 7 \qquad 2^{2}\equiv 4\ mod\ 7 \qquad 3^{2}\equiv 2\ mod\ 7 \qquad 4^{2}\equiv 2\ mod\ 7 \qquad 5^{2}\equiv 4\ mod\ 7 \qquad 6^{2}\equiv 1\ mod\ 7}\)

    则 1,2,4 为模 7 下的平方剩余,而 3,5,6 是模 7 下的平方非剩余

  1. 引理:令 \(\mathsf{a\neq0\ mod\ p}\) ,如果 \(\mathsf{a^{\frac{p-1}{2}}\equiv1\ mod\ p}\) ,则 a 是模 p 下的平方剩余
  • 例子:

    15 是模 17 下的平方剩余,因为 \(\mathsf{15^{\frac{17-1}{2}}\equiv 1\ mod\ 17}\)

    12 是模 17 下的平方非剩余,因为 \(\mathsf{12^{\frac{17-1}{2}}\equiv -1\ mod\ 17}\)

  • 证明:

    p 是奇数,所以根据欧拉定理:\(\mathsf{a^{p-1}\equiv 1\ mod\ p \qquad (a^{\frac{p-1}{2}})^{2}\equiv 1\ mod\ p \qquad a^{\frac{p-1}{2}}\equiv \pm1\ mod\ p}\)

    设 g 为模 p 下的原根,则 \(\mathsf{\{1,\ g,\ g^{2},\ \cdots,\ g^{p-2}\}=1,\ 2,\ \cdots,\ p-1\ mod\ p}\)

    对应某些 k ,设 \(\mathsf{a \equiv g^{k}\ mod\ p}\) ,所以 \(\mathsf{a \equiv g^{k+(p-1)m}\ mod\ p}\)

    当 k 是偶数时,a 是模 p 下的平方剩余

    如果 \(\mathsf{k=2l}\) ,那么 \(\mathsf{a \equiv g^{2l} \equiv (g^{l})^{2}}\)

    相反,如果\(\mathsf{a \equiv b^{2}\ mod\ p}\) 并且假设 \(\mathsf{b=g^{l}\ mod\ p}\) ,那么 \(\mathsf{a \equiv g^{2l}\ mod\ p}\) ,所以 k 是偶数。

  1. 注:在模 p 的剩余系统当中,有一半的数是平方剩余,另一半是平方非剩余。

二、Legendre 符号

  1. 定义:\(\mathsf{(\frac{a}{p})= \begin{cases}1 \qquad a\ 是\ mod\ p\ 的平方剩余 \\ -1 \qquad a\ 是\ mod\ p\ 的平方非剩余 \\ 0 \qquad a\ 为\ p\ 等整数倍 \end{cases} \qquad}\),也可写作 \(\mathsf{(a \mid p)}\) 。满足 \(\mathsf{(\frac{a}{p})=a^{\frac{p-1}{2}}\ mod\ p}\)
  2. 定理:\(\mathsf{(a \mid p)(b \mid p)=(ab \mid p)}\)
  • 证明:

    \(\mathsf{a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv (ab)^{\frac{p-1}{2}}\ mod\ p \qquad (a^{2} \mid p)=(a \mid p)^{2}=1}\)

  • 例子:

    \(\mathsf{(-9 \mid 71)=(-1 \times 3^{2} \mid 71)=(-1 \mid 71)(3^{2} \mid 71)=(-1 \mid 71)=(-1)^{35}\ mod\ 71=-1}\)

    \(\mathsf{(-9 \mid 53)=(-1 \times 3^{2} \mid 53)=(-1 \mid 53)(3^{2} \mid 53)=(-1 \mid 53)=(-1)^{26}\ mod\ 53=1}\)

三、高斯引理

  1. 高斯引理:设 p 为奇素数并且 \(\mathsf{a \neq 0\ mod\ p}\) ,对于任意整数 x ,令 \(\mathsf{x_{p}}\) 为模 p 下关于 x 的同余,且具有最小的绝对值。将 x 除以 p ,余数为 b ,则 \(\mathsf{0 \leq b < p}\) 。如果 \(\mathsf{b<\frac{p}{2}}\) ,令 \(\mathsf{x_{p}=b}\) ,如果 \(\mathsf{b> \frac{p}{2}}\) ,令 \(\mathsf{x_{p}=b-p}\) ,则 \(\mathsf{-p/2 < x_{p} < p/2}\) 。令 n 为 \(\mathsf{(a)_{p},\ (2a)_{p},\ (3a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}}\) 中负数的个数,则 \(\mathsf{(a \mid p)=(-1)^{n}}\)
  • 例子:

    \(\mathsf{p=13 \qquad a=5 \qquad \{a,\ 2a,\ \cdots,\ (\frac{p-1}{2})a\}=\{5,\ 10,\ 15,\ 20,\ 25,\ 30 \}}\)

    \(\mathsf{\{(a)_{p},\ (2a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}\}=\{5,\ -3,\ 2,\ -6,\ -1,\ 4\}}\)

    其中有 3 个负数,所以 \(\mathsf{(5 \mid 13)=(-1)^{3}=-1}\)

    \(\mathsf{p=13 \qquad a=10 \qquad \{a,\ 2a,\ \cdots,\ (\frac{p-1}{2})a\}=\{10,\ 20,\ 30,\ 40,\ 50,\ 60\}}\)

    \(\mathsf{\{(a)_{p},\ (2a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}\}=\{-3,\ -6,\ 4,\ 1,\ -2,\ -5\}}\)

    其中有 4 个负数,所以 \(\mathsf{(10 \mid 13)=(-1)^{4}=1}\)

  • 证明:

    首先证明:如果 \(\mathsf{1 \leq k \neq l \leq (p-1)/2}\) ,那么 \(\mathsf{(ka)_{p} \neq \pm (la)_{p}}\)

    假设 \(\mathsf{(ka)_{p}= \pm(la)_{p}}\) 不正确,那么有 \(\mathsf{ka \equiv \pm\ la\ mod\ p \Rightarrow (k \pm l)a \equiv 0\ mod\ p \Rightarrow k \pm l \equiv 0\ mod\ p}\)

    这是不可能的,因为 \(\mathsf{2 \leq k+l \leq p-1\ ,\ -p/2 < k-l < p/2\ ,\ k-l \neq 0}\)

    所以在模 p 下数 \(\mathsf{\mid (ka)_{p} \mid\ \qquad k=1,\ 2,\ \cdots,\ \frac{p-1}{2}}\) 全部是不同的 (它们有 \(\mathsf{\frac{p-1}{2}}\) 个) 并且必须是整数 \(\mathsf{\{1,\ 2,\ \cdots,\ \frac{p-1}{2} \}}\) 且按照某种顺序排列。

    \(\mathsf{1 \cdot 2 \cdots(\frac{p-1}{2})\equiv \prod\limits_{k=1}^{\frac{p-1}{2}}\mid (ka)_{p} \mid\ mod\ p}\) ,恰好是 n 个数字 \(\mathsf{(ka)_{p}<0}\)\(\mathsf{\equiv(-1)^{n}\prod\limits_{k=1}^{\frac{p-1}{2}}(ka)_{p}\ mod\ p}\)

    \(\mathsf{\equiv (-1)^{n} \prod\limits_{k=1}^{\frac{p-1}{2}}ka\ mod\ p \equiv a^{\frac{p-1}{2}}(-1)^{n}(1\cdot 2 \cdots (\frac{p-1}{2}))\ mod\ p}\)

    \(\mathsf{\Rightarrow 1 \equiv a^{\frac{p-1}{2}}(-1)^{n}\ mod\ p \quad \Rightarrow \quad a^{\frac{p-1}{2}}\equiv (-1)^{n}\ mod\ p \quad \Rightarrow \quad (a \mid p)\equiv (-1)^{n}\ mod\ p}\)

  1. 定理:如果 p 为奇素数且 \(\mathsf{gcd(a,\ p)=1}\) ,如果 a 是奇数,\(\mathsf{(a \mid p)=(-1)^{t}}\)\(\mathsf{t=\sum\limits_{j=1}^{\frac{p-1}{2}} \lfloor \frac{ja}{p} \rfloor}\)\(\mathsf{(a \mid p)=(-1)^{\frac{(p^{2}-1)}{8}}}\)
  • 证明:

    使用高斯引理,主要关注 \(\mathsf{(-1)^{n}}\)\(\mathsf{n\ mod\ 2}\) 的情况。

    对于 1 到 \(\mathsf{\frac{p-1}{2}}\) 之间的每个数 k ,\(\mathsf{ka=p\lfloor \frac{ka}{p} \rfloor +ka\ mod\ p}\)

    \(\mathsf{ka=p \lfloor \frac{ka}{p} \rfloor +(ka)_{p}+ \begin{cases}0 \qquad 如果 (ka)_{p}>0 \\p \qquad 如果 (ka)_{p}<0 \end{cases}}\)

    \(\mathsf{ka= \lfloor \frac{ka}{p} \rfloor + \mid (ka)_{p} \mid + \begin{cases}0 \qquad 如果 (ka)_{p}>0 \\1 \qquad 如果 (ka)_{p}<0 \end{cases}\ mod\ 2}\)

    \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}ka \equiv \sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor+\sum\limits_{k=1}^{\frac{p-1}{2}}\mid(ka)_{p}\mid+n\ (mod\ 2)}\)

    \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}ka=a\sum\limits_{k=1}^{\frac{p-1}{2}}k=\frac{a}{2}(\frac{p-1}{2})(\frac{p-1}{2}+1)=\frac{a(p^{2}-1)}{8}}\)

    由于 \(\mathsf{\{\mid a\mid_{p},\ \cdots,\ \mid \frac{p-1}{2} a \mid _{p}\}}\)\(\mathsf{\{1,\ \cdots,\ \frac{p-1}{2} \}}\)

    \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}\mid (ka)_{p} \mid = \sum\limits_{k=1}^{\frac{p-1}{2}}k=\frac{1}{2}(\frac{p-1}{2})(\frac{p-1}{2}+1)=\frac{(p^{2}-1)}{8}}\)

    所以,\(\mathsf{n\equiv \frac{a(p^{2}-1)}{8}-\frac{p^{2}-1}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor\ (mod\ 2)}\)

    \(\mathsf{n\equiv \frac{(a-1)(p^{2}-1)}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}}\lfloor \frac{ka}{p} \rfloor\ mod\ 2}\)

    \(\mathsf{n\equiv \sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor \equiv t\ mod\ 2}\)

    由于 a 是奇数,所以 \(\mathsf{(a\mid p)=(-1)^{t}}\)

    如果 \(\mathsf{a=2}\)\(\mathsf{n\equiv \frac{(p^{2}-1)}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{2k}{p} \rfloor\ mod\ 2 \qquad k \in \{1,\ 2,\ \cdots,\ \frac{p-1}{2}\}}\)

    所以 \(\mathsf{\lfloor \frac{2k}{p} \rfloor=0}\) ,则 \(\mathsf{n \equiv \frac{(p^{2}-1)}{8}\ mod\ 2}\) ,也就是说:

    \(\mathsf{(2 \mid p)=(-1)^{(p^{2}-1)/8}=\begin{cases}1 \qquad 如果\ p=1,7\ mod\ 8 \\-1 \qquad 如果\ p=3,5\ mod\ 8 \end{cases}}\)

    \(\mathsf{(-1 \mid p)=(-1)^{\frac{p-1}{2}}= \begin{cases}1 \qquad 如果\ p=1\ mod\ 4 \\-1 \qquad 如果\ p=3\ mod\ 4 \end{cases}}\)

四、二次互反律

  1. 定理 (二次互反律):如果 p,q 是不同的奇素数,那么 \(\mathsf{(\frac{p}{q})(\frac{q}{p})=(-1)^{(\frac{p-1}{2})(\frac{q-1}{2})}}\) ,或其他版本:\(\mathsf{(\frac{p}{q})=\begin{cases}+(\frac{q}{p}) \qquad 如果\ p\equiv 1\ mod\ 4\ 或者\ q \equiv 1\ mod\ 4 \\-(\frac{q}{p}) \qquad 如果\ p\equiv q \equiv 3\ mod\ 4 \end{cases}}\)
  • 例子:

    \(\mathsf{(\frac{37}{73}) \leftarrow (\frac{73}{37}) \leftarrow (\frac{-1}{37})}\)

    \(\mathsf{(7 \mid 11)=-(11 \mid 7)=-(4 \mid 7)=-1}\)

    \(\mathsf{(10 \mid 13)=(2 \mid 13)(5 \mid 13)=(-1)(13 \mid 5)=-(3 \mid 5)=-(5 \mid 3)=-(2 \mid 3)=-(-1)=1}\)

    \(\mathsf{p=11,\ x=\pm 1,\ \pm2,\ \pm3,\ \pm4,\ \pm5,\ \Rightarrow x^{2}=1,\ 3,\ 4,\ 5,\ 9}\)

    \(\mathsf{p=13,\ x=\pm1,\ \pm2,\ \pm3,\ \pm4,\ \pm,5\ \pm6 \Rightarrow x^{2}=1,\ 3,\ 4,\ 9,\ 10,\ 12}\)

  1. 雅克比符号(n 不一定只是奇素数):对于任意整数 a 和任意正奇数 n ,雅克比符号被定义为对应于 n 的素因子的 Legendre 符号的乘积。即:\(\mathsf{(\frac{a}{n})=(\frac{a}{p_{1}})^{\alpha_{1}}(\frac{a}{p_{2}})^{\alpha_{2}}\cdots(\frac{a}{p_{k}})^{\alpha_{k}}}\) ,其中 \(\mathsf{n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}}\)
  • 注意:

    如果 \(\mathsf{(\frac{a}{n})=-1}\) 那么 a 是模 n 下的平方剩余。如果 a 是模 n 下的平方剩余并且 \(\mathsf{gcd(a,\ n)=1}\),则 \(\mathsf{(\frac{a}{n})=1}\)

    但是,不同于 Legendre 符号:如果 \(\mathsf{(\frac{a}{n})=1}\) 那么 a 可能是也可能不是模 n 下的平方剩余。如:\(\mathsf{(\frac{-1}{77})=1}\) ,但是 -1 是平方非剩余

  • 例子:

    \(\mathsf{(\frac{1001}{9907})=(\frac{7}{9907})(\frac{11}{9907})(\frac{13}{9907})}\)

    \(\mathsf{ (\frac{7}{9907})=-(\frac{9907}{11})=-(\frac{2}{7})=-1 \qquad (\frac{11}{9907})=-(\frac{9907}{11})=-(\frac{7}{11})=(\frac{11}{7})=(\frac{4}{7})=1 \qquad (\frac{13}{9907})=(\frac{9907}{13})=(\frac{1}{3})=1}\)

    \(\mathsf{(\frac{1001}{9907})=(\frac{9907}{1001})=(\frac{898}{1001})=(\frac{2}{1001})(\frac{449}{1001})=(\frac{449}{1001})=(\frac{1001}{449})=(\frac{103}{449})=(\frac{449}{103})=(\frac{37}{103})=(\frac{103}{37})=(\frac{29}{37})=(\frac{37}{29})=(\frac{8}{29})=(\frac{2}{29})^{3}=-1}\)

五、Tonelli-Shanks 算法

  1. Tonelli-Shanks 算法用于求解形如:\(\mathsf{x^{2} \equiv n\ mod\ p}\) 的二次同余方程。

    输入:p ,一个奇素数。n 是一个整数,其中 n 是模 p 下的平方剩余。意味着 Legendre 符号\(\mathsf{(n/p)=1}\)

    输出:R ,一个整数满足\(\mathsf{R^{2} \equiv n}\)

    (1) 从 p-1 开始,对 p-1 进行因式分解,分解为\(\mathsf{p-1=Q2^{S}}\) ,其中 Q 为奇数。如果 \(\mathsf{S=1\ (p \equiv 3\ mod\ 4)}\) ,则由 \(\mathsf{R \equiv \pm n^{\frac{p+1}{4}}}\) 直接给出解。

    (2) 选择一个 Z 为模 p 下的平方非剩余,令\(\mathsf{c \equiv z^{Q}}\)

    (3) 令\(\mathsf{R \equiv n^{\frac{Q+1}{2}},t \equiv n^{Q},M=S}\)

    (4) 循环:

    <1> 如果\(\mathsf{t \equiv 1}\) ,返回 R

    <2> 否则,找一个最小的 i ,\(\mathsf{0<i<M}\) ,使得 \(\mathsf{t^{2^{i}} \equiv 1}\) (重复平方)

    <3> 令\(\mathsf{b\equiv c^{2^{(M-i-1)}}}\) 并且令 \(\mathsf{R \equiv Rb,\ t \equiv tb^{2},\ c \equiv b^{2}}\)\(\mathsf{M=i}\) (mod p 条件下)

    如果 R 是一个解,那么第二个解就是\(\mathsf{p-R}\)

  • 证明:

    已知 \(\mathsf{p-1=Q2^{S} \qquad r \equiv n^{\frac{Q+1}{2}}\ mod\ p \qquad t \equiv n^{Q}\ mod\ p}\)

    所以 \(\mathsf{r^{2}\equiv nt\ mod\ p}\) 对于每次迭代都为真

    如果 \(\mathsf{t \equiv 1\ mod\ p}\) ,那么 \(\mathsf{r^{2} \equiv n\ mod\ p}\) 并且该算法以 \(\mathsf{R \equiv \pm r\ mod\ p}\) 结束

    如果 \(\mathsf{t \neq 1\ mod\ p}\) ,那么认为 z 为模 p 下的平方非剩余

    \(\mathsf{c \equiv z^{Q}\ mod\ p}\) ,那么 \(\mathsf{c^{2^{S}} \equiv (z^{Q})^{2^{S}} \equiv z^{2^{S}Q} \equiv z^{p-1} \equiv 1\ mod\ p}\) 并且 \(\mathsf{c^{2^{S-1}} \equiv z^{\frac{p-1}{2}} \equiv -1\ mod\ p}\) 这表明 c 的阶数是 \(\mathsf{2^{S}}\)

    同理,有 \(\mathsf{t^{2^{S}} \equiv 1\ mod\ p}\) ,所以 t 的阶数整除 \(\mathsf{2^{S}}\)

    假设 t 的阶数是 \(\mathsf{2^{S^{'}}}\) 。由于 n 是模 p 的平方,\(\mathsf{t \equiv n^{Q}\ mod\ p}\) 也是一个平方,因此 \(\mathsf{S^{'} \leq S-1}\)

    之后令 \(\mathsf{b \equiv c^{2^{S-S^{'}-1}}\ mod\ p \qquad r^{'} \equiv br\ mod\ p \qquad c^{'} \equiv b^{2}\ mod\ p \qquad t^{'} \equiv c^{'}t\ mod\ p}\) 则和上述一致,\(\mathsf{(r^{'})^{2} \equiv nt^{'}\ mod\ p}\) 成立

    然而 t 和 \(\mathsf{c^{'}}\) 的阶都是 \(\mathsf{2^{s^{'}}}\) 。这表明 \(\mathsf{t^{'}}\) 的阶数为 \(\mathsf{2^{S^{''}}}\)满足 \(\mathsf{S^{''}<S{'}}\)

    如果 \(\mathsf{S^{''}=0}\) 那么 \(\mathsf{t^{'} \equiv 1\ mod\ p}\) 并且该算法在 \(\mathsf{R \equiv \pm r^{'}\ mod\ p}\) 终止

    否则,用 \(\mathsf{b^{'},\ r^{''},\ c^{''},\ t^{''}}\) 相似的定义重新开始循环直到 \(\mathsf{S^{' \cdots '}}\) 等于 0

    因此,一系列的 S 是属于严格逐渐减少的算法,一定会终止

  • 例子:

    求解二次同余方程 \(\mathsf{x^{2} \equiv 10\ mod\ 13}\) ,明显 13 是奇素数。由于 \(\mathsf{10^{\frac{13-1}{2}}=10^{6}\equiv 1\ mod\ 13}\) ,10 是平方剩余

    (1) 已知 \(\mathsf{p-1=12=3 \cdot 2^{2}}\) ,令 \(\mathsf{Q=3,\ S=2}\)

    (2) 令 \(\mathsf{Z=2}\) 为平方剩余,因为 \(\mathsf{2^{\frac{13-1}{2}}=-1\ mod\ 13}\) ,令 \(\mathsf{c=2^{3} \equiv 8\ mod\ 13}\)

    (3)\(\mathsf{R=10^{2} \equiv -4\ ,\ t \equiv 10^{3} \equiv-1\ mod\ 13 \qquad M=2}\)

    (4) 开始循环:\(\mathsf{t \neq 1\ mod\ 13}\) ,所以 \(\mathsf{0<i<2}\) ,则 \(\mathsf{i=1}\)

    \(\mathsf{b \equiv 8^{2^{2-1-1}}\equiv 8\ mod\ 13 \qquad c=b^{2}\equiv 8^{2} \equiv -1\ mod\ 13}\)

    \(\mathsf{R=Rb=-4 \cdot 8 \equiv 7\ mod\ 13 \qquad t=tb^{2} \equiv -1 \cdot -1 \equiv 1\ mod\ 13 \qquad M=i=1}\)

    返回开始,因为 \(\mathsf{t \equiv 1\ mod\ 13}\) 。返回 \(\mathsf{R \equiv 7\ mod\ 13}\)

    验证:\(\mathsf{7^{2}=49 \equiv 10\ mod\ 13}\)\(\mathsf{(-7)^{2} \equiv 6^{2} \equiv 10\ mod\ 13}\)

  1. 引理:如果 a,b 都与 p 互素,且 a,b 的阶都为 \(\mathsf{2^{j}\ mod\ p\ (j>0)}\) ,则对于某些 \(\mathsf{k<j}\) 时 ab 的阶表示为 \(\mathsf{2^{k}}\)
  • 证明:

    a 的阶数为 \(\mathsf{2^{j}\ mod\ p}\) ,则 \(\mathsf{a^{2^{j-1}} \equiv -1\ mod\ p}\) 。同理 \(\mathsf{b^{2^{j-1}} \equiv -1\ mod\ p}\)

    所以,\(\mathsf{(ab)^{2^{j-1}} \equiv 1\ mod\ p}\) ,也就是说 ab 的阶数整除 \(\mathsf{2^{j-1}}\) ,因此,\(\mathsf{k<j}\)

热门相关:骑士归来   别那么骄傲   第一神算:纨绔大小姐   霸皇纪   薄先生,情不由己