注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.8 进一步的应用 的旁注。
P110 什么是逆元“配对”
看这里的时候我十分困惑。但是没有关系，这里的配对还是很好理解的。首先我们要意识到，根据裴蜀定理与扩展欧几里得算法，对于每一个 $1 \leq n \leq p - 1$，我们都找得到 $n$ 对于 $p$ 的乘法逆元。记作 $n^{-1}$，即
$$
n^{-1}n\equiv 1 \pmod p
$$
我们会发现一下重要结论：
- $n^{-1}$ 为 $n$ 关于 $p$ 的乘法逆元
- $n$ 也为 $n^{-1}$ 关于 $p$ 的乘法逆元
- 如果存在另外一个逆元 ${n^{-1}}'$，那么 $n^{-1}$ 与 ${n^{-1}}'$ 必定同余，因为有：
$$
n^{-1}n \equiv {n^{-1}}'n \pmod p, n \perp p \Leftrightarrow n^{-1} \equiv {n^{-1}}' \pmod p
$$
所以如果我们令 $n^{-1} := n^{-1} \bmod p$，即将逆元的范围限定在 $[1, p-1]$ 中时（逆元不可能为 $0$），我们就能得到如下结论：
对于 $\forall n \in [1,p-1] \cap \mathbb Z$，除了 $n^2 \equiv 1 \pmod p$ 的数以外，剩余的数中必然有一半为另一半的逆元，或者说，这两半数互为对方的逆元。因为不会有一个数同时为两个数的逆元。
其实要证明这个结论也不难，只不过我们需要换一种表达方式。
$$
M = \{ n \mid 1 \leq n \leq p - 1, n^2 \bmod p \neq 1, n\in\mathbb Z \}
$$
我们想要证明：任意 $a \in M$，有 $a^{-1} \in M$，且 $a \neq a^{-1}$。而这个就很简单了，因为完全就是定义。
由此，我们解释了什么是“配对”。
那配对有什么用？由于我们已经知道了 $nn^{-1}\equiv 1$，所以我们不妨记已经完成配对的集合为 $M$，为匹配的集合为 $T$：
$$
(p-1)! \equiv \prod_{n\in M} n \prod_{n \in T} n \equiv \prod _{n \in T} n
$$
而根据我们在上一节中所证明的结论：在 $p>2$ 时，$T = \{1, p-1\}$，$p=2$ 情况复杂，不过数据很小很容易验证。
最后我们就能得到
$$
(p-1)! \equiv -1 \pmod p
$$
关于书上证明的讨论
其实书上一开始说明的是充分性，之后证明的则是必要性。
为什么一开始是充分性？看他的表述：
若 $n>1$ 不是素数，则 $(n-1)!$ 不可能与 $-1$ 同余。
逆否命题为：
若 $(n-1)!$ 与 $-1$ 同余，$n>1$ 是素数。
充分性证明的补充
书上用了反证。这里扩充一下推导细节。
若 $n$ 不是素数，且
$$
(n-1)! \equiv -1 \pmod n
$$
则根据 $(4.40)$
$$
\Rightarrow (n-1)! \equiv -1 \pmod p, p = dn, d\in \mathbb Z
$$
但是，由于 $n$ 不是素数，则其有素因子 $p<n$，
$$
p < n, p \mid n \Rightarrow (n-1)! \equiv 0 \pmod p
$$
矛盾。
