扩展欧几里得定理
\[ax+by=(a,b); bx_0+(a \bmod b)y_0=(a,b); x = y_0; y = (a/b) y_0 + b(x_0) \]证：\({a}x+{b}y=(a,b)=(b,a \bmod b)=bx+(a \bmod b)y=bx_0+(a-(a/b)b)y_0={{b}}x_0+{{a}}y_0-(a/b){{b}}y_0=\mathbf{{a}}(y_0)+\mathbf{{b}}(x_0+(a/b)y_0)\)，化简后式为 \(ax+by\) 形式，对应得证。
欧拉定理
\[x^{\varphi(p)} \equiv 1 \pmod p(x \perp p) \]引理一：对于两个与 \(p\) 互质的数 \(a,b\)，\(p \perp ab\)。
证：显然有 \(a,b\) 均无 \(p\) 共同因子，设 \(\mathscr S x\) 为 \(x\) 的所有不同质因子集，则有 \(p \notin \mathscr S a, p \notin \mathscr S b\)，而且显然有 \(\mathscr S (ab) = \mathscr S a \cup \mathscr S b\)。所以有 \(p \notin \mathscr S (ab)\)，故 \(p \perp ab\)。
引理二：任取 \(k \in [0, p-1] \wedge k \perp p\)，令 \(S\) 为在 \([0, p-1]\) 之内所有与 \(p\) 互质的数，令 \(T\) 为 \(S\) 内每个数乘 \(k\) 的集合 \(\bmod p\)（不可重），则有 \(T \subseteq S\)。
令 \(a \in S\) 则 \(ak \in T\)。此时 \(a,k\) 均 \(\perp p\)，故 \(ak \in S\)，所以 \(ak \in T \Longrightarrow ak \in S\)，故得证。
引理三：任取 \(k \in [0, p-1] \wedge k \perp p\)，\(S,T\) 在上个引理定义，\(S=T\)。
显然只需要证明 \(|T| = |S|\)。反证法，假设不等大，则必有两个不同元素 \(a,b\)，满足 \(ak \equiv bk\)，又因为 \(k \perp p\)，故 \(k^{-1}\) 存在，于是两边乘 \(k^{-1}\)，即可推出矛盾。
原命题证明：引理三套用 \(k = x\)，得到 \(S_x = T_x\)，对集合内所有元素求积得到：
，又因为 \(\prod S \perp p\)（反复套用引理一），于是可以对 \(\prod S\) 取逆元，而且根据 \(\varphi\) 的定义，有 \(|S| = \varphi(p)\)，得证。
（常用变式：费马小定理，也就是满足 \(p \in \mathbf P\) 的情况下，有 \(x \equiv x^p \pmod p\)，证明显然。）
（常用变式：扩展欧拉定理，将 \(x^y\) 分成 \(x^tx^{y-t}\) 的形式，其中 \(t \perp p\)，套用欧拉定理。）
扩展欧拉定理的形式：
，证明烦琐，不做过多证明。
CRT
方程组 \(x \equiv a_i \pmod{b_i}\) 一定有一解
\[x = \sum a_i \epsilon_i \]，其中
\[\epsilon_i = M_i \times M_{i_{b_i}}^{-1} \]，其中
\[M_i = \dfrac{\prod b}{b_i} \]。
证明：这个方程组的 \(a\) 可以抽象为一个向量 \(\overrightarrow{a}\)，且有 \(\overrightarrow{a}\) 的解加 \(\overrightarrow{b}\) 的解就是 \(\overrightarrow{a} + \overrightarrow{b}\) 的解，于是我们只需要找出基向量 \([1,0,0,\dots,0,0],[0,1,0,\dots,0,0],\dots,[0,0,0,\dots,0,1]\) 即可。于是对于第 \(i\) 个基向量 \(\varepsilon_i\)（和 \(\epsilon_i\) 区分开，实际上，我们马上就会看到 \(\varepsilon_i\) 的解就是 \(\epsilon_i\)），有 \(M_i \mid \varepsilon_i\) 的解，以及 \(\varepsilon_i\) 的解 \(\equiv 1 \pmod{b_i}\)，于是有 \(\varepsilon_i\) 的解为 \(k \times M_i\)，而由于其 \(\equiv 1 \pmod{b_i}\)，可以发现 \(k = M_{i_{b_i}}^{-1}\)，于是得到 \(\varepsilon_i\) 的解就是 \(\epsilon_i\)。得证。
ExCRT
发现要求 \(M_i \perp b_i\)。如果不满足怎么办呢？
则两两合并：
，可以通过 exgcd 解出 \(p,q\)，套入可以将两个方程合并。
莫反
定理：
\[\mu * 1 = \epsilon \]，
定义 \([a_1\quad a_2\quad a_3\quad \cdots] = \prod p_i^{a_i}\)。若 \([a_1\quad a_2\quad a_3\quad \cdots] = r\)，则记 \(r_i = a_i\)。定义 \(\omega(n) = \sum [n_i \ge 1]\)。定义 \(t(n) \iff (\max n_i) \ge 2\)。定义 \(S(n) = \{p_i \mid S_i \ge 1\}\)。显然有 \(|S(n)| = \omega(n)\)。
则显然有 \(\omega(n) = \omega(m) \Longrightarrow (\mu * 1)(n) = (\mu * 1)(m)\)。
\(\mu\) 可以解释为 \(\mu(n) = \left\{\begin{matrix}0 & t(n) \\ -1^{\omega(n)} & \text{otherwise}\end{matrix}\right.\)，于是对于 \(\neg (t(n) \vee t(m))\)，有 \(\omega(n) = \omega(m) \Longrightarrow \mu(n) = \mu(m)\)，于是建立 \(S(n) \leftrightarrow S(m)\) 的双射 \(f(x)\)，因为对于相同的 \(K_i \in [0,1]\)，\(\omega(\prod\limits_{i \in S(n)} f(i)^{K_i})=\omega(\prod\limits_{i \in S(n)} i^{K_i})\)，所以可以建立一个双射 \(g(x) : \{d \mid n \wedge \neg t(d)\} \leftrightarrow \{d \mid m \wedge \neg t(d)\}\)，满足 \(\mu(g(x)) = \mu(f(x))\)，而 \(\forall x \in \{d \mid m \wedge t(d)\} \cup \{d \mid n \wedge t(d)\}, \mu(x) = 0\)，所以根据 \((1-1)^n\) 的展开，得证。
（选自我自己写的博客）
小发现
把函数写成
\[f(n) = \prod_i f'(p_i,n_i) \]的形式，则会有
\[(f*g)(n) = \prod_i \sum_{j=0}^{n_i} f'(p_i, j) \times g'(p_i, n_i - j) \]，于是可以搞一道原创题：求 \((1*1*\cdots*1*1)(n)\)，只不过我已经公开了（笑）
还有一些常见函数的表示：
\(\epsilon'(p, a) = [a = 0]\)，\(1'(p, a) = 1\)，\(id'(p, a) = p^a\)，\(\mu'(p, a) = [a < 2](1 - 2a)\)，\(d'(p, a) = (a + 1)\)，\(\sigma'(p, a) = p^a+1\)。