数论概论读书笔记 20.模p平方剩余

模p平方剩余

img

观察上面这张表,可以发现上下的对称性,字符化描述为: $$ p^2+b^2-2pb=(p-b)^2\equiv b^2 \quad (mod \ p) $$ 因此,若要列出模$p$的所有(非零)平方剩余,只需要计算出其中的一半: $$ 1^2\ (mod \ p),2^2\ (mod \ p),...,(\frac{p-1}{2})^2 \ (mod \ p) $$ 我们的目的是发现模式,以便用来区分模$p$的平方剩余非平方剩余

最后将会导出整个数论中最漂亮的定理之一---二次互反律

一些定义:

  • 与一个平方数模$p$同余的非零数称为模$p$的二次剩余
  • 不与任何一个平方数模$p$同余的数称为模$p$的二次非剩余
  • 将二次剩余简记为$QR$,二次非剩余简记为$NR$
  • 与0模$p$同余的数既不是$QR$,也不是$NR$

定理 设$p$为一个奇素数,则恰有$\frac{p-1}{2}$个模$p$的二次剩余,且恰有$\frac{p-1}{2}$个模$p$的二次非剩余。

由前面的结论知道,只要证明$1^2,2^2,...,(\frac{p-1}{2})^2 \ mod \ p$是两两不同的。

假设$b_1,b_2$是$[1,\frac{p-1}{2}]$之间的数

且满足$b_1^2\equiv b_2^2\ (mod \ p)$

我们要证明$b_1=b_2$

由于$b_1^2\equiv b_2^2\ (mod \ p)$,得到$p\ | \ (b_1^2-b_2^2)=(b_1-b_2)(b_1+b_2)$

然而$b1+b2$显然不能被$p$整除

所以$b_1-b_2=0$

证毕。

QR与NR有什么关系呢?

一个不很难想到的结论是$QR*QR=QR$

因为平方数乘平方数仍为平方数。所以两个二次剩余乘积模$p$仍为二次剩余。

那么其他的组合呢?

经过一些小的表观察,可以得到: $$ QRQR=QR ,\quad QRNR=NR ,\quad NR*NR=NR $$ 在验证后面两个关系之前,我们先来看下原根与二次剩余的关系。

设$g$是模$p$的一个原根,辣么$g$的幂: $$ g,g^2,g^3,...,g^{p-1} $$ 可以给出$p$的所有非零剩余。即$[1,p-1]$。其中一半是二次剩余,一半是二次非剩余。

如何确定哪些是$QR$,哪些是$NR$呢?

显然$g$的每个偶次幂是一个$QR$,即$g^{2k}$。

注意到在(4)中恰有一半是偶次幂,所以$g$的偶次幂给出了所有的二次剩余。而剩下的奇次幂必定是二次非剩余。

同时,也可以用指标来描述,二次剩余是指标$I(a)$为偶数的那些数$a$

二次非剩余是指标$I(a)$为奇数的那些数$a$

定理 二次剩余乘法法则---版本1

设$p$为素数,则

  • 两个模$p$的二次剩余的积是二次剩余
  • 二次剩余与二次非剩余的积是二次非剩余
  • 两个二次非剩余的积是二次剩余

即 $$ QRQR=QR ,\quad QRNR=NR ,\quad NR*NR=NR $$ 证明 对与$p$互素的任意两个数$a,b$,由指标的乘积法则知$I(ab)\equiv I(a)+I(b) \quad mod \ p-1$

从而有$I(ab)\equiv I(a)+I(b) \quad mod \ 2$

后面的证明就很自然了。可以讨论$(5)$中的三种情况。

对于$(5)$式,你肯定会想到$+1,-1$这种

许多年前,勒让德也想到了,而且还搞了点东西

$a$模$p$的勒让德符号是 $$ \left(\frac{a}{p}\right)=\left{\begin{matrix} 1 \quad 若a是模p的二次剩余 \
-1 \quad 若a是模p的二次非剩余 \end{matrix}\right. $$

定理 二次剩余乘法法则---版本2(使用勒让德符号)

设$p$为素数,则 $$ \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right) $$ 勒让德符号使计算可以更直观,比如 $$ \left(\frac{75}{97}\right)=\left(\frac{3\cdot5\cdot5}{97}\right)=\left(\frac{3}{97}\right)\left(\frac{5}{97}\right)\left(\frac{5}{97}\right) $$ 而 $$ \left(\frac{5}{97}\right)\left(\frac{5}{97}\right)=1 \quad (总是如此) $$ 所以 $$ \left(\frac{75}{97}\right)=\left(\frac{3}{97}\right)=1 \quad (3是QR) $$





评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)