数论合集

\(Part\) \(1\): 裴蜀定理

定理：对于任意整数 \(a,b\) ，记 \(\gcd(a,b)=d\) ，则对于所有整数 \(x,y\) ，都有 \(d|ax+by\) ，特别的，一定存在整数 \(x,y\) 使得 \(ax+by=d\) 。

证明：因为 \(d=gcd(a,b)\) ，所以有 \(a\equiv b\equiv 0\pmod d\) ，所以 \(ax+by\equiv 0\times x+0\times y\equiv 0\pmod d\) ，所以 \(d|ax+by\) 。

记所有 \(ax+by\) 的集合为 \(S\) ，设 \(w=ax_1+by_1\) 是 \(S\) 中的最小正值，则有 \(w\ge d\) ；

对于所有 \(u=ax_2+by_2\in S\) ，有 \(u\mod w=u-kw=(x_1-kx_2)a+(y_1-ky_2)b\in S\) ，又因为 \(0\le u\mod w<w\) ，所以 \(u\mod v\) 只能等于 \(0\)，即对于所有 \(u\in S\) ，都有 \(w|u\) 。

又因为 \(a,b\in S\) ，所以 \(w|a, w|b\) ， 所以 \(w\) 是 \(a,b\) 的公因数，所以有 \(w\le d\) 。

综上所述 , \(w=d\) ，即 \(d\) 是集合 \(S\) 中的最小正值，证毕。

\(Part\) \(2\): 费马小定理

定理：若 \(p\) 为质数，则对于任意自然数 \(a\) ，都有 \(a^{p-1}\equiv 1\pmod p\) ，即 \(a^p\equiv a\pmod p\) 。

证明如下：

\(\bullet\)引理1：一个数 \(a\) 在模 \(p\) 意义下的乘法逆元存在的充要条件是 \(\gcd(a,b)=1\) 。

证明：若方程 \(ax\equiv 1\pmod p\) 有解，相当于 \(ax=py+1\) 即 \(ax+py=1\) 有解，由裴属定理可得，如果方程有解当且仅当 \(\gcd(a,p)=1\) ，且此时 \(ax+py\) 的最小正值为 \(1\) ，充分性和必要性同时得证。

\(\bullet\)引理2：对于正整数 \(a,b,c,p\) ，且 \(\gcd(c,p)=1\) 如果 \(ac\equiv bc\pmod p\) ，则有 \(a\equiv b\pmod p\) 。

证明：由于 \(\gcd(c,p)=1\) ，由引理 \(1\) 可得 \(c\) 在模 \(p\) 意义下存在乘法逆元，所以 \(ac\equiv bc\pmod p\rightarrow ac\times c^{-1}\equiv bc\times c^{-1}\pmod p\rightarrow a\equiv b\pmod p\) 。

\(\bullet\)证明：

我们构造两个序列 \(S={1,2,…，p-1}\) ，\(T=a,2a,3a,…,(p-1)a\) ，其中 \(a\not \equiv 0\pmod p\) 。

首先由引理 \(2\) 可知，\(T\) 中元素两两不同，因为如果 \(i a\equiv j a\pmod p\) ，则 \(i=j\) ，所以 \(S\) 与 \(T\) 同构。

所以 \(\prod_{i\in S}i=\prod_{i\in T}i\) ，即 \((p-1)!\equiv a^{p-1}(p-1)!\pmod p\) 。

又因为 \(p\) 为质数，所以 \(\forall 1\le i<p\) ，\(\gcd(i,p)=1\) ，所以 \(\gcd((p-1)!,p)=1\) ，那么再次应用引理 \(2\) ，可得：

\(a^{p-1}(p-1)!\equiv (p-1)!\pmod p\rightarrow a^{p-1}\equiv 1\pmod p\) ，证毕。

\(Part\) \(3\): 欧拉函数相关

定义：在 \(1\) ~ \(n\) 中与 \(n\) 互质的数的个数称为 \(n\) 的欧拉函数，记为 \(\varphi_n\) 。

\(Part\) \(3.1\): 欧拉函数的性质

性质\(1\). 如果 \(x\) 是质数，则 \(\varphi_x=x-1\) 。

性质\(2\). 欧拉函数是积性函数，即如果 \(\gcd(x,y)=1\) ，则 \(\varphi_{x y}=\varphi_x\varphi_y\) 。

性质\(3\).\(\varphi_{p^k}=p^{k-1}(p-1)\) 。

性质\(4\). 若 \(x\) 的唯一分解是 \(x=\prod_{}{p_i^{k_i}}\) ，则 \(\varphi_x=n\prod_{}{(1-\frac{1}{p_i})}\) 。

\(Part\) \(3.2\): 欧拉函数的求解

单个求解时： 利用性质 \(4\) ，试除法求出所有质因数，时间复杂度 \(O(\sqrt{n})\) 。

多个求解时： 利用性质 \(2\) 和性质 \(3\) ，使用线性筛求积性函数，时间复杂度 \(O(n)\) 。

\(Code:\)

inline void prework() {
	for(int i=2;i<=n;++i) {
		if(!vis[i]) vis[i]=1,pri[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt && i*pri[j]<=n;++j) {
			vis[i*pri[j]]=1;
			if(i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
			else phi[i*pri[j]]=phi[i]*pri[j];
			if(i%pri[j]==0) break;
		}
	}
}

\(Part\) \(3.3\): 欧拉反演：

\(n=\sum_{d|n}\varphi_d\)

证明：记 \(f_x=\sum_{i=1}^{n}{[\gcd(i,n)=x]}\) ，则显然有 \(n=\sum_{i=1}^n f_i=\sum_{d|n}f_d\) 。

又因为 \(f_x=\sum_{i=1}^{n}{[\gcd(i,n)=x]}=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}{[\gcd(i,\frac{n}{x})=1]}=\varphi_{\frac{n}{x}}\) ，所以 \(n=\sum_{d|n}{f_d}=\sum_{d|n}\varphi_{\frac{n}{d}}\) ，根据约数的对称性，可得 \(n=\sum_{d|n}\varphi_d\) ，证毕。

\(Part\) \(3.4\): 欧拉定理

定理：对于正整数 \(a,p\)，若 \(\gcd(a,b)=1\) ，则有 \(a^{\varphi_p}\equiv 1\pmod p\) 。

证明： 同理于费马小定理的证明，我们依然构造两个序列，\(S={r_1,r_2,…,r_{\varphi_p}}\) ， 表示所有小于 \(p\) 且与 \(p\) 互质的数，再构造 \(T={a r_1,a r_2,…,ar_{\varphi_p}}\) 。

若 \(a r_i\equiv q r_j\pmod p\) ，那么就有 \(i=j\) ，又因为 \(\gcd(a,p)=1\bigwedge\gcd(r_i,p)=1\rightarrow \gcd(a r_i,p)=1\) ，所以序列 \(S\) 与 \(T\) 同构。

记 \(w=\prod_{i=1}^{\varphi_p}{r_i}\) ，则有 \(a^{\varphi_p}w\equiv w\pmod p\) ，又因为 \(\gcd(w,p)=1\) ，所以 \(w\) 在模 \(p\) 意义下存在逆元，所以有：

\(a^{\varphi_p}w\equiv w\pmod p\rightarrow a^{\varphi_p}w\times w^{-1}\equiv w\times w^{-1}\pmod p\rightarrow a^{\varphi_p}\equiv 1\pmod p\) ，证毕。

\(Part\) \(3.4.1\): 拓展欧拉定理

定理：\(\forall a,p\)都有

证明如下：

我们尝试证明 \(\forall a,p,a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，其中 \(0\le r<\varphi_p,n\ge2\) 。

记 \(a\) 的完全分解为 \(a=\prod_{}{p_i^{c_i}}\) 。

引理 \(1\). \(\forall p_i,\varphi_{p_i^{c_i}}|\varphi_p\) ：

因为 \(\gcd(p_i^{c_i},p)=1\) ，由欧拉函数的积性可知，\(\varphi_p=\varphi_{p_i^{c_i}}\varphi_{\frac{p}{p_i^{c_i}}}\)，所以可得 \(\varphi_{p_i^{c_i}}|\varphi_p\) 。

\(\bullet\) 证明 \(1\). 对于 \(a\) 是质数及质数的幂的情况，上式成立：

记 \(a=x^y , p=x^kb\) ，其中 \(\gcd(a,b)=1\) ，若 \(k=0\) ，则 \(\gcd(a,p)=1\)， 由欧拉定理可知 \(a^{\varphi_p}\equiv 1\pmod p\rightarrow a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ；

若 \(k>0\) ，由引理 \(1\) 可得 \(\varphi_b|\varphi_p\) ，因为 \(\gcd(b,p)=1\) ，所以由欧拉定理得 \(a^{\varphi_b}\equiv 1\pmod b\rightarrow x^{y\varphi_p}\equiv 1\pmod b\) 。

记 \(x^{y\varphi_p}=ub+1\) ，两边同时乘上 \(x^k\) ，得到 \(x^{y\varphi_p+k}=um+x^k\rightarrow x^{\varphi_p+k}\equiv x^k\pmod p\) 。

因为 \(\varphi_p=\varphi_{x^k}\varphi_b=x^{k-1}(x-1)\varphi_b\) ，由于 \(x>=2\) （质数），所以 \(x^{k-1}(x-1)\ge k\) ，即 \(\varphi_p\ge k\) ，所以有推导如下：

\(x^{\varphi_p+k}\equiv x^k\pmod p\rightarrow x^{\varphi_p+k}\times x^{\varphi_p+r-k}\equiv x^k\times x^{\varphi_p+r-k}\pmod p\rightarrow x^{2\varphi_p+r}\equiv x^{\varphi_p+r}\pmod p\) ，由数学归纳法可以得到 \(x^{n\varphi_p+r}\equiv x^{\varphi_p+r}\pmod p\)

所以 \((x^{n\varphi_p+r})^y\equiv(x^{\varphi_p+r})^y\pmod p\rightarrow a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，证毕。

\(\bullet\) 证明 \(2\). 对于 \(a\) 不是质数或者质数的幂的情况，上式依然成立：

由证明 \(1\) 可以得到 \(a^{n\varphi_p+r}\equiv\prod(p_i^{c_i})^{n\varphi_p+r}\equiv\prod(p_i^{c_i})^{\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，证毕。

综上所述，\(\forall a,p,a^{n\varphi_p+r}\equiv a^{\varphi_p+r}\pmod p\) ，拓展欧拉定理得证。

\(Part\) \(4\): [exGCD]拓展欧几里得算法

——用于求解形如 \(ax+by=k\) 的二元一次方程。

设 \(\gcd(x,y)=d\) ，由裴属定理可知，方程有解的条件是 \(d|k\) ，我们首先考虑如何求解 \(ax+by=d\) 。

思考我们使用欧几里得算法求 \(gcd\) 的方式：

int Gcd(int u,int v){
	return v?Gcd(v,u%v):u;
}

当 \(v=0\) 时，\(u=d\) ，此时方程 \(au+bv=d\) 的解为 \(a=1,b=0\) 。考虑从这一层的答案推导出上一层的答案，\(u=v',v=u'-\lfloor\frac{u'}{v'}\rfloor\times v'\) ，带入得 \(au+bv=d\rightarrow av'+b(u'-\lfloor\frac{u'}{v'}\rfloor\times v')=d\rightarrow bu'+(a-\lfloor\frac{u'}{v'}\rfloor)v'=d\) ，所以上一层的解为 \(a'=b,b'=a-\lfloor\frac{u'}{v'}\rfloor b\) ，递归求解即可。

\(Code:\) 时间复杂度 \(O(log_{}{n})\)

int exgcd(int a,int b,int &x,int &y) {
	if(!b) {x=1,y=0; return a;}
	int ans=exgcd(b,a%b,x,y);
	int x0=x; x=y,y=x0-y*(a/b);
	return ans;
}

然后 \(ax+by=k\) 的一组解就是 \(\frac{bk}{d}x+\frac{ak}{d}y=k\) 。

通解： 方程 \(ax+by=d\) 的所有整数解为 \((a-\frac{wy}{d})x+(b+w\frac{wx}{d})y=d\) 。

\(Part\) \(5\): [CRT]中国剩余定理

——求解同余方程组

对于同余方程组如下，

其中 \(p_1,p_2,…,p_n\) 两两互质。中国剩余定理说明了该方程一定有解，且解在模 \(M=\prod_{i=1}^{n}{p_i}\) 意义下唯一，解为 \(x=\sum_{i=1}^{n}{\frac{a_i M}{p_i}inv_i}\mod M\) ，其中 \(inv_i\) 为 \(\frac{M}{p_i}\) 在模 \(p_i\) 意义下的逆元（可以证明一定存在）。

\(\bullet\) 首先我们证明我们构造的这个解的正确性：

对于一个同余方程 \(x\equiv a_i\pmod {p_i}\) ，可以发现对于所有 \(i\not=j\) ，因为 \(p_i|M\)，所以有 \(\frac{M}{p_j}\equiv0\pmod {p_i}\) ，所以 \(\sum_{j\not=i}{\frac{a_j M}{p_j}inv_j}\equiv0\pmod {p_i}\) ，因此我们只需要关心 \(\frac{a_i M}{p_i}inv_i \mod p_i\) 的值，而这个值显然为 \(a_i\mod p_i\) ，即对于所有 \(1\le i\le n\) ，\(x\equiv a_i\pmod {p_i}\)，证毕。

\(\bullet\) 其次我们来证明解在模 \(M\) 下的唯一性：

引理：对于正整数 \(a,b,c\) ，如果 \(b|c\) ，则有 \(a\equiv (a\mod c)\pmod b\) 。

证明：设 \(a=k c+r\) ，因为 \(b|c\) ，所以 \(b|k c\) ，则 \(a\equiv(kc+r)\equiv r\equiv(a\mod c)\pmod b\) 。

接着继续证明， 如果方程有两个解 \(x\) 与 \(x'\)，那么 \(\forall 1\le i\le n\) ，由引理可知，都有 \((x\mod M)\equiv (x'\mod M)\pmod {p_i}\)。

即 \(\forall 1\le i\le n\)， \(p_i|(x\mod M)-(x'\mod M)\) ，又因为 \(p_i\) 两两互质，所以 \(M|(x\mod M)-(x'\mod M)\rightarrow x\equiv x'\pmod M\) ，证毕。

\(Part\) \(5.1\): [exCRT]拓展中国剩余定理

——合并同余方程组

对于同余方程组如下，

与CRT不同的是，\(p_1,p_2,……,p_n\) 不再两两互质，我们可以通过合并同余方程来求解上述同余方程组。

考虑每次我们需要将两个同余方程：

合并成一个方程 \(x\equiv a\pmod {lcm(a_1,a_2)}\) 。

记 \(a=k_1 p_1+a_1=k_2 p_2+a_2\) ，即 \(k_1p_1-k_2p_2=a_2-a_1\) ，是一个线性方程组，此时：

若 \(a_2-a_1\not\equiv0\pmod {\gcd(p_1,p_2)}\)，由裴属定理说明该同余方程组已经无解了。

若 \(a_2-a_1\equiv0\pmod{\gcd(p_1,p_2)}\)，此时我们利用exGCD求出一组解 \(k_1,k_2\) ，此时满足 \(x=k_1p_1+a_1=k_2p_2+a_2\) ，所以两个同余方程被我们合并成了一个：\(x\equiv(k_1p_1+a_1)\pmod {lcm(p_1,p_2)}\) ，可以发现所有解之差均为 \(w\times lcm(p_1,p_2)\) 的形式，因此合并出来的结果在模 \(lcm(p_1,p_2)\) 意义下是唯一的。

对于所有同余方程，我们依次合并即可。

\(Part\) \(6\): 整除分块

——快速计算形如 \(\sum_{i=1}^{n}{\lfloor\frac{n}{i}\rfloor}\) 的值

思路：我们会发现在 \(1\le i\le n\) 中， \(\lfloor\frac{n}{i}\rfloor\) 的取值有很多重复的部分，而且取值相同的 \(i\) 是连续的一段，我们可以通过将一段的值一起计算来加速。

\(\bullet\)引理 \(1\)：\(\forall 2\le i\le\sqrt n\) ，\(\lfloor\frac{n}{i-1}\rfloor\not=\lfloor\frac{n}{i}\rfloor\)

证明：因为 \(i\le \sqrt n\) ，所以 \(\lfloor\frac{n}{i}\rfloor\ge\sqrt n\) ，如果有 \(\lfloor\frac{n}{i-1}\rfloor=\lfloor\frac{n}{i}\rfloor\) ，那么记 \(k=(n\mod (i-1))-(n\mod i)=n-(i-1)\lfloor\frac{n}{i-1}\rfloor-n+\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{i}\rfloor\ge\sqrt n\) ，又因为 \(0\le n\mod (i-1)< i-1<\sqrt n\bigwedge 0\le n\mod i<i\le \sqrt n\) ，所以 \(k<i\le \sqrt n\) ，产生矛盾，所以得证。

\(\bullet\) 引理 \(2\)：\(\forall 1\le i\le n\) ，\(\lfloor\frac{n}{i}\rfloor\) 最多有 \(2\sqrt n\) 种取值。

证明：\(\forall i\ge \sqrt n\) ，\(\lfloor\frac{n}{i}\rfloor\le\sqrt n\) ，最多 \(\sqrt n\) 种取值；\(\forall i<\sqrt n\) ，总共 \(\sqrt n\) 个数，也最多 \(\sqrt n\) 种取值；所以总共 \(2\sqrt n\) 种取值，证毕。

\(\bullet\) 定理：对于 \(i,j\le n\) ，使得 \(\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor\) 成立的最大的 \(j=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\) 。

证明：记 \(v=\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor\) ，则 \(\lfloor\frac{n}{v}\rfloor\ge\lfloor\frac{n}{\frac{n}{j}}\rfloor=j\) ，即 \(j\le \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\) ，证毕。

所以我们每一次可以计算当前 \(l\) 所在的块的右端点 \(\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\) ，然后 \(O(1)\) 将这一块的答案统一计算，块的个数为 \(\sqrt n\) 级别，时间复杂度 \(O(\sqrt n)\) 。