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

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *