Notes on Module
逆元
对于模意义下的除法，$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。