扩展欧几里得定理
\[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\),\(\varphi'(p, a) = [a < 2](1 - 2a)p^a\)