同余关系
在 基本概念 的部分中，我们已经简单了解了 整除 与 余数
而在这一个部分中，我们将 更复杂的 了解 余数 中的 同余关系
由于 本节内容多在模意义下讨论，故文中可能会出现一些 \(=, \equiv\) 混用的情况，见谅
全文 绝大多数 内容是对 [0] 中讲述的 粗略抄写 和 胡乱加工
1. 费马小定理
\[n ^ {p - 1} \equiv 1 \pmod p, p \in \mathbb P \]在 前面的部分* 中，我们证明了 \(ni \bmod p ~ (i \in [1, p - 1])\) 的值是 \(1 \sim p - 1\) 的 一种排列
* : 欧几里得 \(\to\) 类欧几里得算法 \(\to\) * 当 \(n = c - 1\) 时的 封闭形式
我们证明的是 \(n \perp p,ni \bmod p ~ (i \in [1, p])\) 的情况，但 推广显然
于是我们 把它们全部乘起来，有
\[\begin {aligned} & \prod \limits _ {i = 1} ^ {p - 1} ni \\ \equiv & \prod \limits _ {i = 1} ^ {p - 1} ni \bmod p & \pmod p \\ \equiv & (p - 1) ! & \pmod p \end {aligned} \]显然有
\[\begin {aligned} \prod \limits _ {i = 1} ^ {p - 1} ni =& n ^ {p - 1} (p - 1) ! \end {aligned} \]故
\[\begin {aligned} n ^ {p - 1} (p - 1) ! \equiv& (p - 1) ! \pmod p \end {aligned} \]由于 \((p - 1) ! \perp p\)，故两边可以 同时 \(\div (p - 1) !\)，即得到
\[n ^ {p - 1} \equiv 1 \pmod p \]即得证，上式也可以写作
\[n ^ p \equiv n \pmod p \]证明显然
2. 乘法逆元
其实此处讨论的 乘法逆元 全称应当是 模意义下的乘法逆元，以下直接简称 逆元
考虑到 余数 并不具有 完全的可除性，故在模意义下，我们试图寻找一些东西 代替除法运算
这就是 乘法逆元，其等价于通常意义下的 \(\dfrac 1 n\)，或说 \(n ^ {-1}\)，乘上它 就相当于 除以了 \(n\)
存在性
如果线性同余方程 \(ax \equiv 1 \pmod b\) 有解，则有 \(x\) 为 \(a\) 在模 \(b\) 意义下的逆元，记作 \(a ^ {-1}\)
反之则 \(a\) 没有 模 \(b\) 意义下的逆元
容易得到 \(ax + by \equiv 1 \pmod b\)，显然，当且仅当 \(a \perp b\) 时，方程有解
故当且仅当 \(a \perp b\) 时，\(a\) 存在 模 \(b\) 意义下的逆元
根据在 扩展欧几里得算法 一部分中的讨论
我们可以知道，\(ax + by \equiv 1 \pmod b\) 存在通解 \(x = x_0 + kb'\)
其中 \(x_0\) 是 任意特解，\(b' = \dfrac b {\gcd (a, b)} = b\)
故显然，\(0 \le x < b\) 的特解 有且仅有一组
即 \(a\) 在 模 \(b\) 意义下，至多存在一个 \(< b\) 的非负逆元
求解
\(O (\log b)\) 求解任意 \((a, b)\) 的逆元
对于上述 同余方程，我们显然可以通过 \(\operatorname {exgcd}\) 简单求解
同时，当 \(b \in \mathbb P\) 时，根据 费马小定理，我们可以知道 \(n ^ {p - 2} \equiv n ^ {-1}\)，可以使用 快速幂 求解
以上方法 时间复杂度 均为 \(O (\log b)\)，常数较小，可以对任意 \((a, b)\) 求解
但多数情况中，模数是固定的，而 时间紧迫，我们需要一些 更快速的逆元求解方法
固定 \(b\)，线性求 \(1 \sim b - 1\) 的逆元
这就是我们通常指的 线性求逆元，显然有 \(1 ^ {-1} \equiv 1 \pmod b\)，我们尝试推导出 \(i ^ {-1}\)
此时令 \(k = \left \lfloor \dfrac b i \right \rfloor, j = b \bmod i\)，显然有 \(ki + j = b\) 即 \(ki + j \equiv 0 \pmod b\)
于是我们左右同乘 \(i ^ {-1} j ^ {-1}\)，有
\[\begin {aligned} kj ^ {-1} + i ^ {-1} & \equiv 0 & \pmod b \\ i ^ {-1} & \equiv - kj ^ {-1} & \pmod b \\ i ^ {-1} & \equiv - \left \lfloor \dfrac b i \right \rfloor (b \bmod i) ^ {-1} & \pmod b \end {aligned} \]于是写成代码就是
const int MOD = 998244353;
int Inv[MAXN];
inline void Init () {
for (int i = 1; i <= P; ++ i)
Inv[i] = 1ll * (MOD - MOD / i) * Inv[MOD % i] % MOD;
}
可以来 Luogu P3811 【模板】模意义下的乘法逆元 检验 板子的正确性
固定 \(b\)，线性求任意序列 \(a\) 的逆元
这是一种利用 前缀积 求解逆元的方式，我们设 \(s\) 是序列 \(a\) 的前缀积
如果我们知道了 \(s_n\) 的逆元，可以尝试 倒推回去
显然，我们知道 \(a_i \times s_{i - 1} = s_i\)，于是 \(a _ i ^ {-1} = s _ {i - 1} \times s _ i ^ {-1}\)，又 \(s _ {i - 1} ^ {-1} = s _ i ^ {-1} \times a_i\)
倒推即可求出所有 \(a _ i ^ {- 1}\)，时间复杂度 \(O (n + \log b)\)，\(\log b\) 是因为要求 \(s_n\) 的逆元
const int MAXN = 3000005;
int S[MAXN], A[MAXN], I[MAXN];
inline int Qpow (int a, int b, const int MOD) {...}
inline void Solve (const int N, const int P) {
S[0] = 1;
for (int i = 1; i <= N; ++ i) S[i] = 1ll * A[i] * S[i - 1] % P;
long long K = Qpow (S[N], P - 2, P);
for (int i = N; i >= 1; -- i) I[i] = S[i - 1] * K % P, K = K * A[i] % P;
}
附上两种算法的板子提交记录 Sol.1 on Luogu P3811，Sol.2 on Luogu P3811
几种算法的优劣显然，此处不多分析
3. 二次探测定理
若 \(p \in \mathbb P\) 且 \(p > 2\)，则 \(x ^ 2 \equiv 1 \pmod p\) 有且仅有 \(x \equiv 1\) 与 \(x \equiv p - 1\) 两个解
我们先来考虑 \(x ^ 2 \equiv 1 \pmod m\) 有多少个解这个 广泛一些的问题
考虑 \(m = p ^ k, p \in \mathbb P\)，那么上述同余式可以变形为 \((x + 1) (x - 1) \equiv 0 \pmod {p ^ k}\)
显然 \(p ^ k \mid (x + 1) (x - 1)\) ，故有 \(p ^ k \mid x - 1\) 或 \(p ^ k \mid x + 1\)，即存在两个解 \(x \equiv \pm 1 \pmod {p ^ k}\)
当 \(p > 2\) 时，容易发现，不可能有 \(p ^ k \mid x - 1\) 且 \(p ^ k \mid x + 1\)
当 \(p = 2\) 时，若存在 \(2 ^ k \mid (x - 1) (x + 1)\)
可以证明，\(x - 1, x + 1\) 中，一个数能被 \(2\) 整除，但不能被 \(4\) 整除，则另一个一定能被 \(2 ^ {k - 1}\) 整除
两数差为 \(2\)，容易发现，当其中一个数为 \(2 ^ p, p > 1\) 的 整倍数 时，另一个数 只能为 \(2\) 的倍数
故上述结论显然
这意味着，当 \(k > 2\) 时，存在四个解 \(x \equiv \pm 1 , x \equiv 2 ^ {k - 1} \pm 1 \pmod {2 ^ k}\)
容易发现，\(x ^ 2 \equiv 1 \pmod m\) 当且仅当 对于 所有 满足 \(m_p > 0\)* 的 \(p\)，有 \(x ^ 2 \equiv 1 \pmod {p ^ {m_p}}\)
* : \(p \in \mathbb P\)，在 记号与声明 中有 \(m_p\) 的定义
可以证明，每个质数均 独立 于其它质数
根据上面的结论，对于每个 \(p > 2\) 的质数 \(p\)，其将会贡献 两种解的情况
故若 \(m\) 有 \(k\) 种 不同的奇质因子，则方程 \(x ^ 2 \equiv 1 \pmod m\) 的解数为 \(2 ^ k\)
而当 \(m\) 是偶数时，情况会稍微复杂一点，若 \(m\) 有 \(k\) 种 不同的质因子
则 \(x ^ 2 \equiv 1 \pmod m\) 的 精确解数 是
\[2 ^ { k - [8 \mid m] + [4 \mid m] - [2 \mid m] } \]在上述过程中，我们已经证明了 二次探测定理
4. 威尔逊定理 / 威尔逊逆定理
\((n - 1) ! \equiv -1 \pmod n \Longleftrightarrow n \in \mathbb P\)
威尔逊定理 是其中 \(\Longleftarrow\) 的部分，即对于任意质数 \(p\)，有 \((n - 1) ! \equiv -1 \pmod p\)
我们代入 \(p = 2\)，其显然符合条件，于是我们只需考虑 奇质数 的部分
考虑使用 逆元配对 的思想来证明这个定理
在上面部分，我们证明了，一个数 \(n\) 在模 \(p\) 意义下 至多有一个 \(< p\) 的非负逆元（\(n < p\)）
而由于我们要求了 \(p \in \mathbb P\)，故 \(n \perp p\)，该逆元存在，我们将之记作 \(n'\)
显然，\(n, n'\) 互为逆元，从而不会有其它 \(< p\) 的非负数逆元为 \(n\) 或 \(n'\)
于是有 \(nn' \equiv 1 \pmod p\)，若 \(n \neq n'\)，显然 这一对数 消去后 不影响等式关系
故我们可以在 \((p - 1)!\) 中逐渐将 成对的 \(nn'\) 消去，容易发现，最终会留下一些数
而 这些数 即是 不满足 \(n \neq n'\) 的数，换言之，其逆元是其本身
容易发现，这样的数就是 \(x ^ 2 \equiv 1 \pmod p\) 的解，根据上面的 二次探测定理
当 \(p\) 为 奇质数 时，\(x\) 仅有两解 \(\pm 1\)，故 \((p - 1) ! \equiv 1 \times (p - 1) \equiv -1 \pmod p\)，得证
而 威尔逊逆定理 讲的就是 \(\Longrightarrow\) 的部分
即对于所有满足 \((n - 1) ! \equiv -1 \pmod n\) 的 \(n\)，\(n\) 一定为 质数
显然，考虑反证，若 \(n\) 不是质数，则其可被分解成 至少两个更小的数的乘积
而这两个数必然可在 \((n - 1) !\) 中 找到，故 \((n - 1)! \equiv 0 \pmod n\)
若这两个数不等，易得，若这两个数相等，设为 \(x ^ 2 = n\)，我们找到 \(x\) 与 \(2x\) 即可
显然，若 \(2x > n - 1, n > 0\)，则有 \(n < 3 + 2\sqrt 2\)，对于这些 \(n\)，带入验证即可
于是 威尔逊定理 / 威尔逊逆定理 均得证
5. 有趣的遗留问题？
就是在 欧几里得 - 类欧几里得算法 - * 当 \(n = c - 1\) 时的 封闭形式 中提到过的一个结论
我们设 \(d = \gcd (a, c)\)，于是 \(ai \bmod c ~ (i \in [1, \dfrac c d])\) 一定是 \(0, d, 2d, ..., c - d\) 的 一种排列
这个东西在当时已经 简易证明 了，在这里来 详细论述 一下
考虑设 \(a = k_0 d, c = k_1 d\)，于是我们有 \(k_0 \perp k_1\)（\(k_1 = \dfrac c d\)）
我们先把 \(d\) 去除，即转化成 \(k_0i \bmod k_1 ~ (i \in [1, k_1])\) 一定是 \(0, 1, ..., k_1 - 1\) 的 一种排列
然后开始 反证法，若其 不是 \(0, 1, ..., k_1 - 1\) 的 一种排列
则一定存在 \(i, j ~ (i < j)\) 使得 \(k_0 i \equiv k_0 j \pmod {k_1}\)，故 \(k_1 \mid k_0 (j - i)\)
显然 \(i, j \in [1, k_1]\)，故 \(k_0 (j - i) < k_0 k_1\)，又 \(k_0 \perp k_1\)，有 \(\operatorname {lcm} (k_0, k_1) = k_0 k_1\)
而显然 \(k_0 \mid k_0 (j - i), k_1 \mid k_0 (j - i)\)，又 \(k_0 (j - 1) \neq k_0 k_1\)，矛盾，故原命题得证