Notes on Module

逆元

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

$$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))$$

费马小定理

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

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

线性同余方程组

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

$$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}}$$

中国剩余定理

$$\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}$$

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

$n!$

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

${n \choose k} \bmod 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! \over k!(n-k)!}$$

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

418 I'm a teapot