二次剩余

Quadratic Residue

我们说Bob如何来决定一个给定的数a是一个模p的二次剩余？
我们说Alice计算$1222^2 (mod\ 1223)$可以只计算$611^2(mod\ 1223)$因为$a^2 \equiv (p-a)^2 (mod\ p)$
所以，对于大于模数一半的数，我们都可以通过先前的$(p-a)^2(mod\ p)$来得到，这样就节省了一半时间。

::: Proposition
Proposition 1. 设p是一个奇素数，则有： (a)
两个模p的二次剩余的积还是模p的二次剩余。 (b)
两个模p的非二次剩余的积是模p的二次剩余。 (c)
模p的二次剩余和模p的非二次剩余的积是模p的非二次剩余。
:::

::: proof
Proof.
我们其实可以很简单的证明(a)，(b)但是我们这里用了一个非常巧妙的办法同时证明三个条件。
假设g是模p的原根。这也就意味着g的幂$1,g,g^2,\cdots,g^{p-2}$都是互不相同的。
那么g的多少次幂可以生成一个二次剩余呢？显然当$m = 2k$时，m是偶数，所以$g^m \equiv (g^k)^2$是一个
平方数，可以生成二次剩余。
另一方面，设m是一个奇数，$m = 2k + 1$，并且假设$g^m$是一个二次剩余，即$g^m \equiv c^2(mod\ p)$
由费马小定理， $\begin{aligned} &c^{p-1} \equiv 1\ (mod\ p) \\ &c^{p-1} \equiv c^{2\frac{p-1}{2}}\ (mod\ p) \\ &c^{2\frac{p-1}{2}} \equiv g^{m\frac{p-1}{2}} \equiv (g^{m})^{\frac{p-1}{2}}\ (mod\ p) \\ &(g^{m})^{\frac{p-1}{2}} \equiv g^{(2k + 1)\frac{p-1}{2}} \equiv g^{k(p-1)}g^{\frac{p-1}{2}}\ (mod\ p) \\ &g^{k(p-1)} \equiv 1\ (mod\ p) \\ &g^{\frac{p-1}{2}} \equiv 1\ (mod\ p) \\ \end{aligned}$
这显然产生了矛盾，因为g是原根，在$g^{p-1}$之前，不可能有g的幂x使得$g^x \equiv 1\ (mod\ p)$
所以也就证明了，此时g是一个二次非剩余。 0◻ ◻
:::

通过上面的证明，我们得到以下结论：如果g是模p的一个原根，那么

$$g^m is\ a\ \begin{cases} quadratic\ residue \ \ \ if\ m\ is\ even \\ quadratic\ nonresidue \ \ \ if\ m\ is\ odd \\ \end{cases}$$ 所以我们要想证明刚才的(a), (b)我们可以设a, b都是模p的原根g的幂。 (a)a, b都是二次剩余，可以写成$a = g^{2i}$, $b = g^{2j}$所以$ab = g^{2(i + j)}$显然幂指数 为偶数，所以ab也是二次剩余。 其余(b), (c)类似，显然易证。 ::: Lemma **Lemma 2**. *当素数$p \leq 3$时并且有整数$a = a_1a_2a_3\cdots a_n$时，我们有 $$(\frac{a}{p}) = (\frac{a_1}{p}) \cdot (\frac{a_2}{p}) \cdot (\frac{a_3}{p}) \cdot \cdots \cdot (\frac{a_n}{p})$$* ::: ::: Proof **Proof 1**. *我们知道由欧拉判别准则，$(\frac{a}{p}) \equiv a^{\frac{p-1}{2}}\ (mod\ p)$, 所以有 $$(\frac{a}{p}) \equiv a^{\frac{p-1}{2}} \equiv a_1^{\frac{p-1}{2}}a_2^{\frac{p-1}{2}} \cdots a_n^{\frac{p-1}{2}}\ (mod\ p) \equiv (\frac{a_1}{p})(\frac{a_2}{p})\cdots (\frac{a_n}{p})\ (mod\ p)$$

下面要证明等号成立，而不是同余号。 由上式得到 $\begin{aligned} &(\frac{a}{p}) - (\frac{a_1}{p})(\frac{a_2}{p})\cdots(\frac{a_n}{p}) \equiv 0\ (mod\ p) \\ \end{aligned}$ 但是显然有 $\begin{aligned} & \lvert (\frac{a}{p}) - (\frac{a_1}{p})(\frac{a_2}{p})\cdots(\frac{a_n}{p}) \rvert \geq 2 \\ \end{aligned}$ 而我们知道$p \geq 3$，所以必须有 $\begin{aligned} &(\frac{a}{p}) = (\frac{a_1}{p})(\frac{a_2}{p})\cdots (\frac{a_n}{p}) \\ \end{aligned}$ 0◻*
:::

::: Lemma
Lemma 3. 对素数$p \geq 3$, 我们有 $\begin{aligned} &(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}} \end{aligned}$
:::

::: Proof
Proof 2. 由欧拉判别准则我们有 $\begin{aligned} &(\frac{-1}{p}) \equiv (-1)^{\frac{p-1}{2}}\ (mod\ p) \\ \mbox{又明显有} \\ &\lvert (\frac{-1}{p}) - (-1)^{\frac{p-1}{2}} \rvert \leq 2 \ (mod\ p) \\ \mbox{由$p \geq 3$可以得到} \\ &(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}} \end{aligned}$
所以我们知道当$p \equiv 1\ (mod\ 4)$时，-1是模p的二次剩余，而当$p \equiv 3\ (mod\ 4)$时，-1是
模p的非二次剩余。也就是 $\begin{aligned} (\frac{-1}{p}) = \begin{cases} 1\ if\ p \equiv 1\ (mod\ 4) \\ -1\ if\ p \equiv 3\ (mod\ 4) \\ \end{cases} \end{aligned}$ 0◻
:::

我们再来看一种新方法。 由欧拉标准可知， $\begin{aligned} (\frac{-1}{p}) \equiv (-1)^{\frac{p-1}{2}}\ (mod\ p) \\ \end{aligned}$
那么假设$p \equiv 1\ (mod\ 4)$，也就是令$p = 4k + 1$，于是

$$\begin{aligned} &(-1)^{\frac{p-1}{2}} = (-1)^{2k} = 1 \\ &so\ 1 \equiv (-1)^{\frac{p-1}{2}}\ (mod\ p)，\\ \end{aligned}$$ 既然勒让德符号只能为1或-1 那么就可以直接把同余号写为等号。 再令$p = 4k + 3$，证明同理。\ 下面我们用这个定理来证明一个有趣的定理\ ::: Theorem **Theorem 4**. *有无穷多个质数模$p \equiv 1\ (mod\ 4)$。\ * ::: ::: Proof **Proof 3**. *我们先给出一列模4余一的素数$p_1, p_2, \cdots, p_r$，我们要找到一个不在此列中的新素数，并且也模4余1 并且此列素数已经包含了所有的模4余1的素数，这样就可以得出矛盾。 考虑数 $$A = (2p_1p_2\cdots p_r)^2 + 1 \\ $$ 我们知道A可以分解质因数 $$A = q_1q_2\cdots q_s \\ $$ 很明显这一列素数并不在我们上面的素数列之中，因为没有$p_i$可以整除A。 所以我们要验证是否每个素数都是模4余1。 我们先注意到A是奇数，并且$q_i$都整除A $$(2p_1p_2\cdots p_r)^2 + 1 = A \equiv 0\ (mod\ q_i)$$

我们令$x = (2p_1p_2\cdots p_r)^2$所以x就是方程

$$x^2 \equiv -1\ (mod\ q_i) \\$$

的解。所以-1是模$q_i$的二次剩余！所以根据刚才的定理，$q_i \equiv 1\ (mod\ 4)$。
0◻*
:::

我们刚才验证了-1是否为二次剩余，现在可以验证一下2，最小的素数，看模数p为多少时，2为模p的二次剩余。
我们可以通过计算得到，2为模p的二次剩余，$p = 7, 17, 23, 31, 41, 47$。2为模p的非二次剩余，
$p = 3, 5, 11, 13, 19, 29$。刚才的问题，我们验证了-1是否为模p的二次剩余，而p需要模4余1。
那么我们现在也把这个p列表进行模4

$$7, 17, 23, 31, 41, 47 \equiv 3, 1, 3, 3, 1, 3\ (mod\ 4)$$ $$3, 5, 11, 13, 19, 29 \equiv 3, 1, 3, 1, 3, 1\ (mod\ 4)$$

然而这并不能区分导致二次剩余的p和导致二次非剩余的p。因为他们模4的结果都为3和1，不好辨别。
于是我们尝试不同的模数，直到模8 $\begin{aligned} 7,17,23,31,41,47 \equiv 7, 1, 7, 7, 1, 7\ (mod\ 8) \\ 3,5,11,13,19,29 \equiv 3, 5, 3, 5, 3, 5\ (mod\ 8) \end{aligned}$
这样就能区分了，也就是模数p再模8的时候，余数如果为3，5，则2是模p的二次非剩余，如果为7，1，则2是模p的二次剩余。
所以也就归纳出了 $(\frac{p}{2}) = \begin{cases} 1\ if\ p\equiv 1\ or\ 7\ (mod\ 8), \\ -1\ if\ p\equiv 3\ or\ 5\ (mod\ 8). \\ \end{cases}$

下面开始引入最精彩的二次互反定律 我们先来据一些例子 $\begin{aligned} 9 \equiv 2\ (mod\ 7), 18\equiv 4 \equiv -3\ (mod\ 7), 27\equiv 6 \equiv -1\ (mod\ 7) \\ \end{aligned}$
我们平时把余数一般写为正数，它也就有一个名字，叫做，最小非负剩余，范围在$[0,p-1]$
而如果我们把大于$\frac{p-1}{2}$的数再取模一次，让其为负值，我们可以知道，最小的数为$\frac{p-1}{2} + 1 - p$
此时余数的范围就改变为$(-\frac{p}{2}, \frac{p}{2})$我们称这些余数为模p的最小剩余。
现在我们看上面我取的一列数，被除数是倍数关系，而且最大数为$27 = 3*9$，而3并不超过$\frac{p-1}{2} = 3$
并且我让最小倍数9满足$9 \nmid 7$
如上这样取可以让获得的最小剩余的绝对值互不相同，则其绝对值构成$(0, \frac{p-1}{2}]$所有数的一个排列！
我们来证明一下为何最小剩余的绝对值互不相同

::: Proof
Proof 4. *设我们取的一列数为 $n, 2n, \cdots, \frac{p-1}{2}n$
两个整数a, b，$a \in [1, \frac{p-1}{2}]$， $b \in [1,\frac{p-1}{2}]$，且

$$an \equiv r_i\ (mod\ p), bn \equiv -r_j\ (mod\ p)$$

并且我们知道$p \nmid n$于是 $p \mid (a + b)$
而$(a+b) \in [2, p-1]$显然不能被p整除，矛盾。
拿我们举的例子来说，我们比如取$a = 1$，则$an = 9 \equiv 2\ (mod\ 7)$，我们要找一个模7余-2的数。
最小值为54。然而$54 = 96$则$b = 6$然而b的范围为$[1, \frac{p-1}{2}]$显然超出了范围，矛盾了。
:::

我们把这个排列中的正余数用$r1, r_2 \cdots r\lambda$表示，把负余数用$m_1, \cdots m_u$表示并且全部乘起来，就得

$$n \cdot 2n \cdot \cdots \cdot \frac{p-1}{2}n \equiv (-1)^{u} r_1r_2\cdots r_\lambda m_1m_2 \cdots m_u \equiv (-1)^{u}1\cdot 2\cdots\frac{p-1}{2} (mod\ p)$$

其实u的值就是大于$\frac{p-1}{2}$的余数的个数！所以-1的幂指数，就取决于大于$\frac{p-1}{2}$的余数的个数！
并且我们知道$p \nmid (\frac{p-1}{2})!$所以消掉两边相同项，即得

$$n^{\frac{p-1}{2}} \equiv (-1)^{u} (mod\ p)$$ 再由欧拉准则，可知 $$(\frac{n}{p}) \equiv n^{\frac{p-1}{2}} \equiv (-1)^{u} (mod\ p)$$

然后我们来正式证明$(\frac{p}{2})$的性质

::: Theorem
Theorem 5. $(\frac{p}{2}) = \begin{cases} 1\ if\ p\equiv 1\ or\ 7\ (mod\ 8), \\ -1\ if\ p\equiv 3\ or\ 5\ (mod\ 8). \\ \end{cases}$
:::

::: Proof
Proof 5.
*我们先来考虑$p \equiv 3\ (mod\ 8)$的情况，设$p = 8k + 3$，则$\frac{p-1}{2}$为$4k + 1$。
我们知道n取2，所以余数应该为$2, 4, 6, \cdots, [\frac{p-1}{2}]$，那么从$\frac{p+1}{2}$一直到p-1的余数，经过模p
都是负余数，所以，带入$p = 8k + 3$,
负余数的范围是$4k + 2, 4k + 4, \cdots, 8k + 2$一共$2k + 1$个数。
所以由欧拉准则

$$(\frac{2}{p}) \equiv 2^{\frac{p-1}{2}} \equiv (-1)^{2k + 1}\ (mod\ p) = -1$$

所以我们证明出2是模$p = 8k + 3$的二次非剩余！
下面我们可以以相同的方式考虑$p = 8k + 7$，$p = 8k + 1$， $p = 8k + 5$。
0◻*
:::