二次剩余

前言

本篇文章将讲解初等数论中一个重要的东西,二次剩余,需要阅读本文的读者至少拥有高中代数基础和一些初等数论的基础。

QR 与 NR

我们可以用一些数学符号来表示$n$ 是不是关于模 $p$ 的二次剩余。

$$x^2 \equiv n \ (mod\ p)$$

若对于奇素数p和满足 $n \nmid p$ 的整数 $n$,该方程的 $x$ 有整数解,则我们称 $n$ 是关于模 $p$ 的二次剩余,记做 $QR$ 。而对于无整数解的称呼其为模 $p$ 的二次非剩余。记做 $NR$。

而当 $n \equiv 0 \pmod{p}$的情况,也就是 $n \mid p$ ,这种情况下n既不是 $QR$ 也不是 $NR$ 。

定理 1.1

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

定理 1.1 证明

二次剩余是非零数,它们是模$p$平方剩余,因此它们是如下这些数:

$$1^2,2^2, \cdots , (p-1)^2 \pmod{p}$$

因为 $(p-b)^2=p^2-2pb+b^2 \equiv b^2 \pmod{p}$,所以对于数$b$的平方剩余和数$(p-b)$的平方剩余是模$p$相同的。

因此如果要列出模$p$的所有(非零)平方剩余,只需计算出其中的一半:

$$1^2,2^2, \cdots , \left(\frac{p-1}{2} \right)^2 \pmod{p}$$

因此,如果计算出余下的平方剩余

$$\left(\frac{p+1}{2} \right)^2, \cdots ,(p-2)^2,(p-1)^2 \pmod{p}$$

则会出现与前面顺序颠倒的相同的数,因此要证明恰好有$\frac{p-1}{2}$个二次剩余,只需验证 $1^2,2^2, \cdots , \left(\frac{p-1}{2} \right)^2$模p是两两不同的。

假设$b_1$与$b_2$都是$1$到$\frac{p-1}{2}$之间的数,且满足${b_1}^2 \equiv {b_2}^2$. 我们要证明 $b_1=b_2$. 条件${b_1}^2 \equiv {b_2}^2$则说明

$$p \mid ({b_1}^2 – {b_2}^2)$$

所以就有

$$p \mid (b_1 – b_2)(b_1+b_2)$$

然而,$b_1+b_2$是$2$到$p-1$之间的数,因此不可能被$p$整除,故要使得$p \mid (b_1 – b_2)(b_1+b_2)$成立,必须满足$p \mid (b_1+b_2)$,但是 $\left| b_1-b_2 \right|< \frac{p-1}{2}$, 所以要使$p \mid (b_1+b_2)$成立的唯一方法只能是$b_1=b_2$,这就证明了$1^2,2^2, \cdots , \left(\frac{p-1}{2} \right)^2$模p是两两不同的,因此恰好有$\frac{p-1}{2}$个模$p$的二次剩余,而$1$到$p-1$之间有$p-1$个数,如果他们中的一半是二次剩余,则剩下的另一半必是二次非剩余.

$Q.E.D$

二次剩余乘法法则

  1. $QR \times QR = QR$
  2. $QR \times NR = NR$
  3. $NR \times NR = QR$

QR × QR = QR 证明

假定$a_1,a_2$都是模$p$的二次剩余 $(QR)$,即存在数$b_1,b_2$,使得$a_1 \equiv {b_1}^2\ (mod\ p)$,$a_2 \equiv {b_2}^2 \pmod{p}$. 将这两个同余式相乘,得到$a_1a_2 \equiv (b_1b_2)^2 \pmod{p}$,则证明了$a_1a_2$是一个$QR$,也就是 $QR \times QR = QR$.

$Q.E.D$

QR × NR = NR 证明

上文中已经证明了$QR \times QR = QR$,下面假设$a_1$是一个$QR$,比如$a_1 \equiv {b_1}^2\ (mod\ p)$,且设$a_2$是一个$NR$,我们假设$a_1a_2$是一个$QR$并由此到出矛盾,利用反证法来证明$QR \times NR = NR$.

$a_1a_2$是$QR$这一假设意味着

$$\exists b,b^2 \equiv a_1a_2 \equiv {b_1}^2a_2 \pmod{p}$$

我们将这个数记为$b_3$,因为$p \nmid a_1$ 且 $a_1={b_1}^2$,所以$gcd(b_1,p)=1$,由线性同余定理知,我们可以找出$b_1 \pmod{p}$的逆元,也就是找出某个数$c_1$使得$c_1b_1 \equiv 1 \pmod{p}$成立. 将上面的同余式两边同时乘${c_1}^2$可得

$${c_1}^2{b_3}^2 \equiv {c_1}^2a_1a_2 \equiv (c_1b_1)^2a_2 \equiv a_2 \pmod{p}$$

于是$a_2 \equiv (c_1b_3)^2 \pmod{p}$是一个$QR$,与$a_2$是$NR$矛盾,利用反证法就证明了 $QR \times NR = NR$.

$Q.E.D$

NR × NR = QR 证明

设$a$是一个$NR$,考虑下述数的集合:

$$a,2a,3a,\cdots , (p-2)a,(p-1)a \pmod{p}$$

我们知道,对于素数$p$,以及满足$a \not \equiv 0\pmod{p}$的整数$a$,则数$a,2a,3a,\cdots , (p-2)a,(p-1)a \pmod{p}$与数$1,2,3,\cdots , (p-2),(p-1) \pmod{p}$相同,尽管它们的次序不同.

所以上面这些数恰好是 $1,2,3,\cdots,p-1$ 以某种不同顺序的重排.而由 定理 1.1 知,这些数中包含$\frac{p-1}{2}$个$QR$和$\frac{p-1}{2}$个$NR$.而由上文知$QR \times NR = NR$,也就是每次将$a$乘$QR$便得到一个$NR$,所以$\frac{p-1}{2}$个积$a \times QR$已经给出了表中的$\frac{p-1}{2}$个$NR$,因此 $a \times NR$的结果只能是表中个一个$QR$. 也就证明了 $NR \times NR = QR$.

$Q.E.D$

legendre 符号

我们发现,$QR$和$NR$之间的规则如同$+1$和$-1$一样,尝试用$+1$代替$QR$,$-1$代替$NR$.

勒让德 (Adrien-Marie Legendre)引入了legendre 符号来表示$QR$和$NR$

$$\left(\frac{n}{p} \right)=\begin{cases} 0 & {n \equiv 0 \pmod{p}}\\+1& \text{n 是模p的二次剩余}\\ -1& \text{n 是模p的二次非剩余} \end{cases}$$

于是我们可以重新描述二次剩余乘法法则,设$p$为奇素数,则

$$\left(\frac{a}{p} \right)\left(\frac{b}{p} \right) = \left(\frac{ab}{p} \right)$$

欧拉准则

legendre符号还有另一个定义

$$\left(\frac{n}{p} \right)=\pm 1 \equiv a^{\frac{p-1}{2}} \pmod{p}$$

这叫做欧拉准则,设$p$为奇素数,则

$$a^{\frac{p-1}{2}} \equiv \left(\frac{n}{p} \right) \pmod{p}$$

欧拉准则证明

证明分为两部分

  1. 证明对于QR成立
  2. 证明对于NR成立

首先假设$a$是一个$QR$,比如$a \equiv b^2 \pmod{p}$,则由费马小定理

$$a^{\frac{p-1}{2}} \equiv (b^2)^{\frac{p-1}{2}} \equiv b^{p-1} \equiv \pmod{p}$$

这就证明了a是$QR$的时候的欧拉准则,下面考虑同余式

$$X^{\frac{p-1}{2}} – 1 \equiv 0 \pmod{p}$$

我们刚刚已经证明,每个QR都是这个同余式的解,并且由 定理 1.1 知,恰有 $\frac{p-1}{2}$个QR,由模p多项式定理可知,这个多项式同余式至多有$\frac{p-1}{2}$个不同的解,因此有如下命题成立.

$$\{X^{\frac{p-1}{2}} – 1 \equiv 0 \pmod{p}\text{的解}\}=\{\text{模p的QR}\}$$

设$a$是一个$NR$,由费马小定理可知$a^{p-1} \equiv 1 \pmod{p}$,所以

$$0 \equiv a^{p-1}-1 \equiv (a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1) \pmod{p}$$

第一个因子模$p$不等于零,因为$X^{\frac{p-1}{2}} – 1 \equiv 0 \pmod{p}$的解都是QR,因此第二个因子比模$p$为零,从而有

$$a^{\frac{p-1}{2}} \equiv -1 = \left(\frac{a}{p} \right) \pmod{p}$$

这就证明了欧拉准则对于$a$是NR的时候也成立.

$Q.E.D$

结语

二次互反律待等… (咕咕咕~)

本文《二次剩余》由 RM Olive (rmolives@gmail.com) 发布,如有版权纠纷及其他问题可以与我取得联系进行解决。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇