---
title: Notes on Module
tags:
  - Chinese Remainder Theorem
  - Combinatorics
  - Lucas's Theorem
  - Multiplicative Inverse
  - Note
  - Prime
id: "1094"
categories:
  - - OI
    - Number Theory
date: 2017-07-07 21:10:53
---

### 逆元

对于模意义下的除法，$a/x \equiv b \pmod m \Leftrightarrow a \times x^{-1} \equiv b \pmod m$，则称$x^{-1}$为$x$在模$m$意义下的逆元。

关于逆元的求法可以参考 Notes on Multiplicative Inverse。

考虑线性同余方程$ax \equiv b \pmod m$，有

$$
(a/(a, m))x \equiv b/(a, m) \pmod {m/(a, m)}
$$

显然，当$(a, m) \not \mid b$时，原方程无解；否则，有

$$
x \equiv (a/(a, m))^{-1} \times (b/(a, m)) \pmod {m/(a, m)}
$$

因此原方程的解为

$$
x \equiv (a/(a, m))^{-1} \times (b/(a, m)) + (m/(a, m)) \times k \pmod m \ (0 \le k \lt (a, m))
$$

原方程可能有多解，也可能无解。

---

### 费马小定理

当$p$是素数时，对任意整数$x$都有$x^p \equiv x \pmod p$。若$p \not \mid x$，则

$$
\begin{align}
x^{p-1} &\equiv 1 \pmod p \\\\
x^{-1} &\equiv x^{p-2} \pmod p
\end{align}
$$

当$m$不是素数且$x$与$m$互质时，有

$$
x^{\varphi(m)} \equiv 1 \pmod m
$$

其中$\varphi(m)$为欧拉函数，其值等于不大于$m$的正整数中与$m$互质的数的个数。

利用线性筛，每次发现质数$p$时把它倍数的欧拉函数乘上$(p-1)/p$，就可以求出$1$到$n$的欧拉函数。

---

### 线性同余方程组

给定由若干个形如$a_ix \equiv b_i \pmod {m_i}$的方程组成的方程组，求它的解。如果有解，则一定有无穷多解，并可以表示为$x \equiv b \pmod m$的形式，因此问题转化为求解$b$和$m$。如果我们能求解方程组

$$
\left\\{
\begin{align}
x &\equiv b_i \pmod {m_i} \\\\
ax &\equiv b_{i+1} \pmod {m_{i+1}}
\end{align}
\right.
$$

那么只要对方程逐个求解即可得到答案。

因为$x \equiv b_i \pmod {m_i}$，所以$x=tm_i+b_i$，代入第二个式子，得到

$$
a(tm_i+b_i) \equiv b_{i+1} \pmod {m_{i+1}}
$$

移项后得到

$$
atm_i \equiv b_{i+1}-ab_i \pmod {m_{i+1}}
$$

这是一个一次同余方程。当$(am_i, m_{i+1}) \not \mid b_{i+1}-ab_i$时原方程组无解。

---

### 中国剩余定理

如果同余方程组满足

$$
\forall i \in [1, n], \ a_i=1 \land \forall i, j \in [1, n] \land i \neq j, \ (m_i, m_j)=1
$$

那么答案的形式一定是

$$
x \equiv b \pmod {\prod m_i}
$$

反之，对于一个合数$n$，如果$n=ab \land (a, b)=1$，那么$x \bmod n$的值确定了之后，$x \bmod a$和$x \bmod b$的值也就确定了。因此，以$n$为模数来考虑和以$a$、$b$为模数来考虑是等价的。这个定理叫做中国剩余定理。

所以，对于模合数的情况只要考虑模若干$p^k$（$p$为素数）的情况就可以了。如果$n$是一个 square-free 的数，那么问题就转化成模素数的情况，从而变得容易求解。

若$n$不是 square-free 的数，可以将每个数字$x$用一个二元组$(a, b)$表示，代表$x=ap_i^b$。有以下运算规则

$$
\begin{align}
(a, b)\times(c, d)&=(ac, b+d) \\\\
(a, b)/(c, d)&=(ac^{-1}, b-d)
\end{align}
$$

关于扩展中国剩余定理可参考 Strange Way to Express Integers。

---

### $n!$

在计数问题中经常用到$n!$。因此有必要了解$n!$在模$p$意义下的一些性质。

假设$p$是素数，$n!=ap^e \ (a \not \mid p)$，求$a \bmod p$和$e$，$e$是$n!$能够迭代整除$p$的次数。显然

$$
e=n/p+n/p^2+n/p^3+ \cdots
$$

因为$n/d$等于不超过$n$的能被$d$整除的正整数个数。

接下来计算$a \bmod p$。可以发现，不能被$p$整除的项在模$p$意义下呈周期性，它们的积为

$$
((p-1)!)^{n/p} \times (n \bmod p)!
$$

事实上，根据威尔逊定理，$(p-1)! \equiv -1 \pmod p$。因为除了$1$和$p-1$之外的其余项都可以和各自的逆元相乘得到$1$。

接下来计算可以被$p$整除的项的积。可以被$p$整除的项为$p, 2p, 3p, \ldots, (n/p)p$，将$p$消去后得到$1, 2, 3, \ldots, n/p$。因此问题的范围就由$n$缩小到了$n/p$。

---

### ${n \choose k} \bmod p$

当$p$不太大时，根据卢卡斯定理，令

$$
n=\sum n_ip^i \ (0 \le n_i \lt p), \ k=\sum k_ip^i \ (0 \le k_i \lt p)
$$

则

$$
{n \choose k} \equiv \prod {n_i \choose k_i} \pmod p
$$

还有另一种思路。首先，把${n \choose k}$写成阶乘的形式

$$
{n \choose k}={n! \over k!(n-k)!}
$$

设

$$
n!=a_1p^{e_1}, \ k!=a_2p^{e_2}, \ (n-k)!=a_3p^{e_3}
$$

从中可以看出，当$e_1 \gt e_2+e_3$时，${n \choose k}$可以被$p$整除；当$e_1=e_2+e_3$时，${n \choose k}$无法被$p$整除，此时${n \choose k} \equiv a_1(a_2a_3)^{-1} \pmod p$。

关于扩展卢卡斯定理可参考 Ceizenpok’s Formula。