问题的提出

前一阵有不太有数论基础的同学问我如下的问题，花了时间敲了敲，遂直接传上来。

请尝试证明，对于双向平方试探法，若散列表长 $M$ 为模4余3的素数，则在前 $M$ 次试探必可遍历 $M$ 中的所有桶。

我们只需要证明

\[\begin{equation*} \{m^2, -n^2| 0 \leqslant m \leqslant \frac{M-1}{2}, 0 \leqslant n \leqslant \frac{M-1}{2}\} \end{equation*}\]

构成模 $M$ 的一个完全剩余系即可。

一个只需要基本数论知识就能看懂的简要证明

1.首先证明 $m^2$ 之间互不同余：

假设

\[\begin{equation*} m_1^2 \equiv m_2^2 \pmod{M} \end{equation*}\]

那么

\[\begin{equation*} m_1^2 - m_2^2 = (m_1 - m_2)(m_1 + m_2) \equiv 0 \pmod{M} \end{equation*}\]

即

\[\begin{equation*} m_1 \equiv m_2 \pmod{M} \quad \text{或} \quad m_1 \equiv -m_2 \pmod{M} \end{equation*}\]

由于 $0 \leqslant m_1, m_2 \leqslant \frac{M-1}{2}$ ，所以 $m_1 \equiv m_2 \pmod{M}$ ，等价于 $m_1 = m_2$ ，矛盾。

而 $m_1 \equiv -m_2 \pmod{M}$ ，等价于 $m_1 + m_2 \equiv 0 \pmod{M}$ ，即 $m_1 + m_2 = M$ ，矛盾。所以 $m_1^2 \not\equiv m_2^2 \pmod{M}$ 。

2.同理可证 $-n^2$ 之间互不同余。

3.最后证明 $m^2$ 与 $-n^2$ 之间互不同余：

假设

\[\begin{equation*} m^2 \equiv -n^2 \pmod{M} \end{equation*}\]

即

\[\begin{equation*} m^2 + n^2 \equiv 0 \pmod{M} \end{equation*}\]

在这里，我们要用到二次剩余：

二次剩余：设 $p$ 是一个奇素数， $a$ 是一个整数，如果存在整数 $x$ ，使得 $a \equiv x^2 \pmod{p}$ ，则称 $a$ 是模 $p$ 的一个二次剩余。

引理1(Euler判别法)

$d$ 是 $p$ 的一个二次剩余，等价于 $d^{\frac{p-1}{2}} \equiv 1 \pmod{p}$ ； $d$ 是 $p$ 的一个非二次剩余，等价于 $d^{\frac{p-1}{2}} \equiv -1 \pmod{p}$ 。

引理1的证明：

当 $d$ 是 $p$ 的一个二次剩余时，存在整数 $x$ ，使得 $a \equiv x^2 \pmod{p}$ ，那么

\[\begin{equation*} d^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod{p} \end{equation*}\]

这用到了Fermat小定理。

而若 $d^{\frac{p-1}{2}} \equiv 1 \pmod{p}$ ，若 $d$ 是 $p$ 的一个非二次剩余，那么对于每个 $a_i\in {1,…,p-1}$ 都存在唯一的 $b_i \neq a_1$ ，使得 $a_i b_i^2 \equiv d \pmod{p}$ (数论逆的存在)，这样可以将 $p-1$ 个数配对成 $\frac{p-1}{2}$ 组，那么将所有的 $(a_i,b_i)$ 相乘，有

\[\begin{equation*} (p-1)! \equiv d^{\frac{p-1}{2}} \equiv 1 \pmod{p} \end{equation*}\]

而Wilson定理告诉我们

\[\begin{equation*} (p-1)! \equiv -1 \pmod{p} \end{equation*}\]

矛盾，所以 $d$ 是 $p$ 的一个二次剩余。

这样就证明了第一个命题的等价性；而奇素数除了模4余1的素数外，其余的素数都是模4余3的素数，所以第二个命题的等价性也成立。

这样就证完了第一个引理。

引理2

$-1$ 是模 $p$ 的一个二次剩余，当且仅当 $p \equiv 1 \pmod{4}$ ； $-1$ 是模 $p$ 的一个非二次剩余，当且仅当 $p \equiv 3 \pmod{4}$ 。

引理2的证明：

利用引理1， $-1$ 是模 $p$ 的一个二次剩余，等价于

\[\begin{equation*} (-1)^{\frac{p-1}{2}} \equiv 1 \pmod{p} \end{equation*}\]

这要求 $\frac{p-1}{2}$ 为偶数，即 $p \equiv 1 \pmod{4}$ ；而 $-1$ 是模 $p$ 的一个非二次剩余，等价于

\[\begin{equation*} (-1)^{\frac{p-1}{2}} \equiv -1 \pmod{p} \end{equation*}\]

这要求 $\frac{p-1}{2}$ 为奇数，即 $p \equiv 3 \pmod{4}$ 。

这样就证完了第二个引理。

引理3(Fermat平方和定理)

若 $p$ 是模4余3的素数，若 $ p|a^2 + b^2 $ ，则 $ p|a $ 且 $ p|b $ 。

引理3的证明：

若存在这样的素数，那么

\[\begin{equation*} a^2 \equiv - b^2 \pmod{p} \end{equation*}\]

存在 $b$ 模 $p$ 的逆元 $b^{-1}$ ，那么

\[\begin{equation*} a^2 b^{-2} \equiv -1 \pmod{p} \end{equation*}\]

这说明 $-1$ 是模 $p$ 的一个二次剩余，而 $p$ 是模4余3的素数，所以根据引理2， $p \equiv 1 \pmod{4}$ ，矛盾。

这样就证完了第三个引理。

回到原题：

直接利用引理3，若存在这样的 $m$ 和 $n$ ，使得

\[\begin{equation*} m^2 + n^2 \equiv 0 \pmod{M} \end{equation*}\]

那么

\[\begin{equation*} m \equiv n \equiv 0 \pmod{M} \end{equation*}\]

矛盾。

从而集合：

\[\begin{equation*} \{m^2, -n^2| 0 \leqslant m \leqslant \frac{M-1}{2}, 0 \leqslant n \leqslant \frac{M-1}{2}\} \end{equation*}\]

中的数互不同余，构成模 $M$ 的一个完全剩余系。

这样就证完了原题。

补充

完全剩余系

设 $m$ 是一个正整数， $a_1,a_2,…,a_m$ 是 $m$ 个整数，如果它们两两不同余，且对于任意的整数 $a$ ，都存在一个整数 $i$ ，使得 $a \equiv a_i \pmod{m}$ ，则称 $a_1,a_2,…,a_m$ 是模 $m$ 的一个完全剩余系。

若 $p$ 是一个素数，那么模 $p$ 的简化剩余系就是模 $p$ 的一个完全剩余系减去 $0$ 的剩余类。

Fermat小定理

若 $p$ 是一个素数， $a$ 是一个整数，那么

\[\begin{equation*} a^p \equiv a \pmod{p} \end{equation*}\]

证明：

$1,2,…,p-1$ 是模 $p$ 的一个简化剩余系，所以

\[\begin{equation*} a \times 1, a \times 2, ..., a \times (p-1) \end{equation*}\]

所以

\[\begin{equation*} a^{p-1} (p-1)! \equiv (p-1)! \pmod{p} \end{equation*}\]

由于 $p$ 是素数，所以 $(p-1)!$ 与 $p$ 互素，可以约去，得到

\[\begin{equation*} a^{p-1} \equiv 1 \pmod{p} \end{equation*}\]

数论逆的存在

若 $p$ 是一个素数， $a$ 是一个整数，那么存在一个整数 $b$ ，使得

\[\begin{equation*} ab \equiv 1 \pmod{p} \end{equation*}\]

证明：

若 $a$ 是模 $p$ 的一个非零剩余，考虑到 $a, 2a, …, (p-1)a$ 是模 $p$ 的一个简化剩余系，所以存在一个整数 $b$ ，使得

\[\begin{equation*} ab \equiv 1 \pmod{p} \end{equation*}\]

且，这样的 $b$ 是唯一的。

Wilson定理

若 $p$ 是一个素数，那么

\[\begin{equation*} (p-1)! \equiv -1 \pmod{p} \end{equation*}\]

证明：

若 $p=2$ ，结论显然成立；若 $p$ 是一个奇素数，那么 $1,2,…,p-1$ 是模 $p$ 的一个简化剩余系，所以

\[\begin{equation*} (p-1)! \equiv 1 \times 2 \times ... \times (p-1) \pmod{p} \end{equation*}\]

将里面的每个数配对成 $\frac{p-3}{2}$ 组，每组的乘积都是 $1$ （数论逆的存在），只有 $1,-1(p-1)$ 没有参与配对，其余配对都是1，所以

\[\begin{equation*} (p-1)! \equiv -1 \pmod{p} \end{equation*}\]