数论常见定理_IT分享知识网

大家好，欢迎来到IT知识分享网。数论常见定理"

裴蜀定理（贝祖定理）

定理指出，设 \(a,b\) 是不全为 \(0\) 的整数，则存在 \(x,y\)，使得：

\[ax+by=\gcd(a,b) \]

证明

如果 \(a=0\) 或 \(b=0\)，则显然成立。
若 \(a\not=0,b\not=0\)。

由于 \(\gcd(a,-b)=\gcd(a,b)\)，不妨设 \(a>0,b>0\)。

欲证明 \(ax+by=\gcd(a,b)\) 有解，不妨将等式两边同时除以 \(\gcd(a,b)\)；

只用证明当 \(\gcd(a’,b’)=1\) 时，\(a’x+b’y=1\) 有解。

按照辗转相除法的原则，由于 \(\gcd(a’,b’)=\gcd(a’,a’\bmod b’)=\dots\)，我们设每次的余数为 \(r\)，则有：

\[\gcd(a’,b’)=\gcd(a’,r_1)=\gcd(r_2,r_1)=\dots=\gcd(r_{n-1},r_n)=\gcd(0,r_n)=1 \]

将式子展开，变为一个个等式，得：

\[\begin{aligned} a_1 &= x_1b+r_1 &(0\leq r_1<b_1)\\ b_1 &= x_2r_1+r_2 &(0\leq r_2<r_1)\\ r_1 &= x_3r_2+r_3 &(0\leq r_3<r_2)\\ &\cdots\\ r_{n-3} &= x_{n-1}r_{n-2}+r_{n-1}\\ r_{n-2} &= x_nr_{n-1}+r_n\\ r_{n-1} &= x_{n+1}r_n \end{aligned} \]

由下至上，根据 \(r_n=1\)，可以推得：

\[r_{n-2}=x_nr_{n-1}+r_n\\ 1=r_{n-2}-x_nr_{n-1}\\ \]

反复将 \(r_n=r_{n-2}-x_{n}r_{n-1}\) 代入式子，最终可以推出 \(1=a_1x+b_1y\)。

几何意义

关于 \(ax+by=n\) 的几何意义可以想象为一条直线，那么 \([0,n]\) 中可以被表示出来的整数就是 \((0,0),\left(\frac{n}{a},0\right),\left(0,\frac{n}{b}\right)\) 为顶点的三角形在第一象限内含有的整点个数。

显然有一个结论就是，在 \([0,n]\) 可以表示出的整数数量为：

\[\sum_{x=0}^{\lfloor\frac{n}{a}\rfloor}\left\lfloor\dfrac{n-ax}{b}\right\rfloor \]

类欧几里得可以在 \(\mathcal{O(\log{\max(a,b)})}\) 的时间内解决（但是决定把它咕咕咕）。

求解 – 扩展欧几里得

扩欧用来求出 \(ax+by=\gcd(a,b)\) 的一组解。

实际上是用类似于辗转相除法倒推出来的：（假设我们已经知道了一组解 \(x_2,y_2\)，试图推出 \(x_1,y_2\)）

\[\gcd(a,b)=ax_1+by_1\\ \Downarrow \]

\[\begin{aligned} \gcd(b,a\bmod b)&=bx_2+(a\bmod b)y_2\\ &=bx_2+\left(a-\left\lfloor\dfrac{a}{b}\right\rfloor\times b\right)y_2\\ &=ay_2+b\left(x_2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2\right) \end{aligned}\\ \]

那么必然存在一组解为：

\[\begin{cases} x_1=y_2\\ y_1=x_2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2 \end{cases} \]

这样我们就可以在递归进行中完成求解啦！

void exgcd(ll a,ll b,ll &x,ll &y)
{
	 if(!b) { x=0,y=1; return; }
	 exgcd(b,a%b,x,y);
	 ll tx=x,ty=y;
	 x=ty,y=tx-a/b*ty;
}

那么 Exgcd 在实际操作中有什么用处呢？求 \(a\) 在模 \(b\) 意义下的逆元！

当然这里 \(b\) 完全可以不被质数所束缚了。

若 \(ax\equiv 1\pmod{b}\)，则有 \(ax+by=1\)，则直接跑上面的 Exgcd 求解即可！

费马小定理

定理指出，若 \(p\) 为素数，且 \(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv1\pmod{p}\)。

换一句话说，对于任意整数 \(a\)，有 \(a^p\equiv a\pmod{p}\)。

证明

设一个质数 \(p\)，取不为 \(p\) 的倍数的整数 \(a\)。

构造序列 \(A=\{1,2,3\dots,p-1\}\)。这个序列存在这样一个性质：

\[\prod_{i=1}^{p-1}A_i\equiv\prod_{i=1}^{p-1}(A_i\times a)\pmod{p} \]

证明：因为每个 \(A_i\times a\pmod{p}\) 都是唯一的，且都 \(<p\)，则每个 \(A_i\times a\pmod{p}\) 的对应一个 \(A_i\)。

因此：

\[\prod_{i=1}^{p-1}A_i\equiv\prod_{i=1}^{p-1}(A_i\times a)\equiv a^{p-1}\times \prod_{i=1}^{p-1}A_i\pmod{p}\\ a^{p-1}\equiv 1\pmod{p} \]

证毕。

欧拉定理

定理指出，对于正整数 \(n\) 和与 \(n\) 互质的数 \(a\)，满足一下性质：

\[a^{\varphi(n)}\equiv 1 \pmod n \]

扩展欧拉定理（通过这些可以欧拉降幂）

\[a^m \equiv \begin{cases} a^{m~\bmod~\varphi(n)},&\gcd(a,n) = 1,\\ a^{(m~\bmod~\varphi(n)) + \varphi(n)},&\gcd(a,n)\not= 1. \end{cases} \pmod{n} \]

Lucas 定理

定理指出：若 \(p\) 是素数，则有：

\[\dbinom{n}{m}\equiv\dbinom{n\bmod p}{m\bmod p}\dbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\pmod{p} \]

简单的推论：

将 \(n,m\) 都表示为 \(k\) 为的 \(p\) 进制数：

\[n=\sum_{i=0}^{k-1}n_i\times p^i\\ m=\sum_{i=0}^{k-1}m_i\times p_i \]

那么一定有：

\[\dbinom{n}{m}\equiv\prod_{i=0}^{k-1}\dbinom{n_i}{m_i}\pmod{p} \]

当我们在求 \(\binom{n}{m}\) 时，最多只会迭代 \(\log_p \max(n,m)\) 次，所以时间复杂度为 \(\mathcal{O(\log^2n)}\)。

\(\bigstar\texttt{attention}\)：求解的时候需要一直递归到 \(x<p,y<p\) 才能结束。

ll C(ll x,ll y)
{
	 if(x<y) return 0;
	 if(x<mod && y<mod) return mi[x]*invmi[y]%mod*invmi[x-y]%mod;
	 return C(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}

扩展 Lucas

其实跟 Lucas 定理毫不相干，但都是用来求组合数对一个数取模的，但模数变成了一个合数。

Step 1：中国剩余定理

用唯一分解定理将模数 \(p\) 分解，构造出若干个同余方程：

\[\left\{ \begin{aligned} a_1\equiv \displaystyle\binom{n}{m}&\pmod {{q_1}^{\alpha_1}}\\ a_2\equiv \displaystyle\binom{n}{m}&\pmod {{q_2}^{\alpha_2}}\\ &\cdots\\ a_r\equiv \displaystyle\binom{n}{m}&\pmod {{q_r}^{\alpha_r}}\\ \end{aligned} \right. \]

Step 2：移除分子分母中的素数

由于无法直接求解 \(\binom{n}{m}\pmod{q^{\alpha}}\)，因为逆元不能直接求解，所以考虑拆开式子。

\[\begin{aligned} \dbinom{n}{m}&\equiv\dfrac{n!}{m!(n-m)!}&\pmod{p^{\alpha}}\\ &\equiv\dfrac{\frac{n!}{p^x}}{\frac{m!}{p^y}\frac{(n-m)!}{p^z}}p^{x-y-z}&\pmod{p^{\alpha}}\\ \end{aligned} \]

其中 \(\dfrac{n!}{p^{x}}\equiv 1\pmod{p}\)，那么难点就在于求解 \(\dfrac{n!}{p^x}\pmod{p^{\alpha}}\)。

Step 3：Wilson 定理的推论

其实说不上是用威尔逊定理，这就是一个计算上面式子的技巧。

考虑对 \(n!\) 变形：

\[\begin{aligned} n!&=1\times2\times3\times\cdots\times n\\ &=(p\times2p\times3p\times\cdots)(1\times 2\times\cdots)\\ &=\left(p^{\lfloor\frac{n}{p}\rfloor}\times 1\times 2\times \cdots\right)\prod_{i=1,i\not\equiv0\pmod{p}}^ni\\ &=\left(p^{\lfloor\frac{n}{p}\rfloor}\times \left\lfloor\dfrac{n}{p}\right\rfloor!\right)\prod_{i=1,i\not\equiv0\pmod{p}}^ni\\ &=p^{\lfloor\frac{n}{p}\rfloor}\times \left\lfloor\dfrac{n}{p}\right\rfloor!\left(\prod_{i=1,i\not\equiv0\pmod{p}}^{p^{\alpha}}i\right)^{\left\lfloor\frac{n}{p^k}\right\rfloor}\left(\prod_{i=p^k\left\lfloor\frac{n}{p^k}\right\rfloor,i\not\equiv0\pmod{p}}^{n}i\right) \end{aligned} \]

最后一步因为除出来的余数是有循环节的，直接按照循环节找，在把余数单独拎出来。

\(\left\lfloor\dfrac{n}{p}\right\rfloor!\) 直接递归处理即可。

那么还剩下 \(x,y,z\) 没有求，设 \(g(n)\) 表示 \(n!\) 中有多少个 \(p\) 因子。根据上面的式子可以得到递推式：

\[g(n)=\left\lfloor\dfrac{n}{p}\right\rfloor+g\left(\left\lfloor\dfrac{n}{p}\right\rfloor\right) \]

最后用中国剩余定理合并即可。

中国剩余定理

\[\begin{cases} x &\equiv a_1 \pmod {p_1}\\ x &\equiv a_2 \pmod {p_2}\\ &\vdots\\ x &\equiv a_k \pmod {p_k}\\ \end{cases} \]

形式的同余方程组的定理，其中 \(p_1,p_2,…,p_k\) 为两两互质的整数，求出 \(x\) 的最小非负整数解。

求解方法

记模数的积为 \(P\)；
对于第 \(i\) 个方程：
- 计算 \(m_i = \tfrac{P}{p_i}\)，这样保证了这一位的结果不会对其他方程产生影响；
- 计算 \(m_i\) 在模 \(p_i\) 意义下的逆元 \(m_i^{-1}\)（似乎好像要用到 Exgcd），可以在这一个方程中消去 \(m_i\) 的影响；
方程组的唯一解为所有解累加起来（由于上面的操作方程之间不会互相影响），答案为：

\[\sum_{i=1}^n a_i m_i m_i^{-1} \pmod {P} \]

\(\bigstar\texttt{important}\)：毒瘤出题人有可能把 \(a_i\) 变为负数！需要取绝对值！

板题：P3868 [TJOI2009]猜数字，P1495 【模板】中国剩余定理(CRT)/曹冲养猪。

P2480 [SDOI2010]古代猪文

给出 \(G,n(1\le G,n\le 10^9)\)，求：

\[G^{\sum_{k|n}\binom{n}{k}}\pmod{999~911~659} \]

因为 \(999911659\) 是一个质数，可以利用欧拉定理将式子转化为：

\[G^{\sum_{k|n}\binom{n}{k}\bmod~999~911~658}\pmod{999~911~659} \]

考虑如何计算：

\[\sum_{k|n}\dbinom{n}{k}\bmod 999~911~658 \]

主要 \(\binom{n}{k}\bmod{999~911~658}\) 比较难搞，决定将这个模数分解：\(999~911~658=2\times 3\times 4679\times 35617\)，对于每个质数用 Lucas 定理求解，最后 CRT 合并即可。

扩展中国剩余定理

\[\begin{cases} x &\equiv a_1 \pmod {p_1}\\ x &\equiv a_2 \pmod {p_2}\\ &\vdots\\ x &\equiv a_k \pmod {p_k}\\ \end{cases} \]

形式的同余方程组的定理，其中 \(p_1,p_2,…,p_k\) 为不一定两两互质的整数，求出 \(x\) 的最小非负整数解。

求解方法

假设两个方程是 \(x\equiv a_1\pmod{p_1},x\equiv a_2\pmod{p_2}\)，考虑合并两个方程：

\[x\equiv a_1\pmod{p_1}~,~x\equiv a_2\pmod{p_2}\\ x=a_1+m_1p_1~,~x=a_2+m_2p_2\\ a_1+m_1p_1=a_2+m_2p_2\\ m_1p_1-m_2p_2=a_2-a_1 \]

若 \(\gcd(p_2,p_1)\) 不能整除 \(a_2-a_1\)，直接无解；
否则记这一次合并后 \(x=ans\)，合并后的方程为 \(x\equiv A\pmod{P}\)，其中 \(A=ans,P=\text{lcm}(p_1,p_2)\)。

\(\bigstar\texttt{important}\)：当数据范围很大的时候需要及时龟速乘！

板题：P4777 【模板】扩展中国剩余定理（EXCRT）

ll n,a1,p1,a2,p2,P,x,y;
void exgcd(ll a,ll b)
{
	 if(!b) { x=(a2-a1)/gcd(p1,p2),y=0; return; }
	 exgcd(b,a%b);
	 ll tx=x,ty=y;
	 x=ty,y=(tx-mul(a/b,ty,P)+P)%P;
}

n=rd();
for(int i=1;i<=n;i++)
{
	 p2=rd(),a2=rd(),P=p1/gcd(p1,p2)*p2;
	 if(i==1) { p1=p2,a1=a2; continue; }
	 if(a2<a1) swap(a1,a2),swap(p1,p2);
	 
	 if((a2-a1)%gcd(p1,p2)) assert(0);
	 exgcd(p1/gcd(p1,p2),p2/gcd(p1,p2));
	 assert((mul(x,p1,P)+mul(y,p2,P))%P==(a2-a1+P)%P);
	 
	 a1=(a1+mul((x%P+P)%P,p1,P))%P,p1=P;
}
printf("%lld\n",a1);

威尔逊定理

定理指出：对于素数 \(p\) 有 \((p-1)!\equiv-1\pmod{p}\)；且若正整数 \(p’\) 满足前面的条件，\(p’\) 一定为质数。

证明

引理 \(1\)：对于集合 \(A=\{2,3,4\dots,p-2\}\)，对于所有 \(A\) 中元素 \(a\)，一定存在不同于 \(a\) 的元素 \(b\in A\)，\(b\) 为 \(a\) 在模 \(p\) 意义下的逆元。

证明 – 反证法：

若 \(b=1\)，且 \(ab\equiv 1\pmod{p}\)，则 \(a\) 只可能为 \(1\)，矛盾。

若 \(b=p-1\)，且 \(ab\equiv 1\pmod{p}\)，则：

\[a(p-1)\equiv 1\pmod{p}\\ ap-a\equiv 1\pmod{p}\\ p-a\equiv 1\pmod {p} \]

则 \(a\) 只可能为 \(p\)，矛盾。

引理 \(2\)：所有元素 \(a\in A\)，他们在模 \(p\) 意义下逆元互不相同。

证明 – 反证法：

若存在不同的整数 \(a_1,a_2\) 满足 \(a_1b\equiv a_2b\equiv 1\pmod{p}\)，则：\((a_1-a_2)b\equiv 1\pmod{p}\)，则 \(a_1=a_2\)，矛盾。

根据引理 \(1\) 与引理 \(2\) 可以得出集合 \(A\) 中元素可以互相配对使得他们的在 \(\bmod{p}\) 意义下乘积为 \(1\)。

又因为 \(1\times(p-1)\equiv -1\pmod {p}\)，所以定理得证。

BSGS

BSGS（baby-step giant-step），即大步小步算法，用来在 \(\sqrt{p}\) 的时间内求解下面的方程：（其中要求 \(a\perp p\)）

\[a^x\equiv b\pmod{p} \]

令 \(x=A\left\lceil\sqrt{p}\right\rceil-B\)，其中 \(0\le A,B\le \sqrt{p}\)，则有：

\[a^{A\lceil\sqrt{p}\rceil-B}\equiv b\pmod{p}\\ a^{A\lceil\sqrt{p}\rceil}\equiv ba^{B}\pmod{p} \]

我们已知 \(a,b\) 可以枚举 \(B\)，得出 \(ba^B\) 的所有取值，存储下来。再枚举 \(A\)，得出 \(a^{A\lceil\sqrt{p}\rceil}\) 的所有取值，查看是否相同即可。

inline int BSGS(int a,int mod,int b)
{
	int sq=ceil(sqrt(mod)); mp.clear();
	int powa=1;
	for(int B=0,x=1;B<=sq;B++)
		x=1ll*b*powa%mod,mp[x]=B,powa=1ll*powa*((B==sq)?1:a)%mod;
	for(int A=0,B,x=1;A<=sq;A++)
	{
		if(mp.find(x)!=mp.end()) { B=mp[x]; if(A*sq-B>=0) return A*sq-B; }
		x=1ll*x*powa%mod;
	}
	return -1;
}

扩展 BSGS

上面 \(a,p\) 不一定互质时该怎么做呢？由于只有在 \(a,p\) 互质的时候才有逆元，我们要想方法让他们变得互质。

设 \(d_1=\gcd(a,p)\)，如果 \(d_1\not\equiv0\bmod b\)，则方程无解，否则同时除以 \(d_1\)，得到：

\[\dfrac{a}{d_1}\times a^{x-1}\equiv \dfrac{b}{d_1}\left(\bmod \dfrac{p}{d_1}\right) \]

如果 \(\frac{a}{d_1}\) 和 \(\frac{p}{d_1}\) 还不互质就继续除，设 \(d_2=\gcd(\frac{a}{d_1},\frac{p}{d_1})\)，如果 \(d_2\not\equiv0\bmod \frac{b}{d_1}\) 就无解，否则同时除以 \(d_2\)，得到：

\[\dfrac{a^2}{d_1d_2}\times a^{x-2}\equiv \dfrac{b}{d_1d_2}\left(\bmod \dfrac{p}{d_1d_2}\right) \]

最终可以得到 \(\frac{p}{d_1d_2\dots d_k}\perp a\)，记 \(D=\prod_{i=1}^{k}d_i\)，则有：

\[\dfrac{a^k}{D}\times a^{x-k}\equiv \dfrac{b}{D}\pmod{\dfrac{p}{D}} \]

由于 \(a\perp \frac{p}{D}\)，则一定有 \(\frac{a^k}{D}\perp \frac{p}{D}\)，存在逆元，移项之后就可以变成了普通版的 BSGS。

\(\bigstar\texttt{Attention}\)：有可能解小于 \(k\)，那么判断 \(\frac{a^k}{D}\equiv \frac{b}{D}\pmod{\frac{p}{D}}\) 及时返回即可。

inline int inv(int a,int mod)
{
	int x,y;
	exgcd(a,mod,x,y);
	return (x%mod+mod)%mod;
}
inline int exBSGS(int a,int mod,int b)
{
	b%=mod;
	if(b==1 || mod==1) return 0;
	int k=0,D=1,U=1,tmod=mod,tb=b;
	for(int x;(x=gcd(tmod,a))>1;)
	{
		if(tb%x) return -1;
		tmod/=x,tb/=x,D*=x,k++;
		U=1ll*U*a/x%tmod;
		if(U==tb) return k;
	}
	tb=1ll*tb*inv(U,tmod)%tmod;
	int ret=BSGS(a,tmod,tb);
	if(ret==-1) return -1;
	return ret+k;
}

升幂定理

咕咕咕

二次剩余

咕咕咕

拉格朗日定理

咕咕咕

原根

咕咕咕

阶

咕咕咕

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/32998.html

数论常见定理

裴蜀定理（贝祖定理）

证明

几何意义

求解 – 扩展欧几里得

费马小定理

证明

欧拉定理

扩展欧拉定理（通过这些可以欧拉降幂）

Lucas 定理

扩展 Lucas

中国剩余定理

求解方法

P2480 [SDOI2010]古代猪文

扩展中国剩余定理

求解方法

威尔逊定理

证明

BSGS

扩展 BSGS

升幂定理

二次剩余

拉格朗日定理

原根

阶

相关推荐

发表回复