初等数论——同余

2024-04-13 15:51 由 hutongzhou 发表于 #其他

前置

模运算

定义： $a \% b (a\mod b)$ ，表示 $a$ 除以 $b$ 的余数。

加法： $(a+b) \% p$ 。
减法： $(a-b+p) \% p$ 。加 $p$ 是为了防止负数。
乘法： $(a \times b) \% p$ 。
除法无法直接运算，要用逆元（在下面会讲到）。
平方运算： 快速幂

模运算满足： 结合律，交换律，分配律 。

同余的定义及其性质

定义： 若 $a,b$ 除以 $m$ 的余数相同，则称 $a,b$ 模 $m$ 同余，记作 $a \equiv b(\mod m)$。

由对于模n同余的所有整数组成的这个集合称为同余类（congruence class或residue class）。

模 $m$ 的同余类一共有 $m$ 个，它们构成 $m$ 的 完全剩余系 。

$1$ 到 $m$ 中与 $m$ 互质的数代表的同余类共有 $\varphi(m)$ 个，它们构成了 $m$ 的简化剩余系。

性质1： 满足对称性，同加性，同乘性，同幂性。

性质2： 若 $a \equiv b(\mod p),c \mid a,c \mid b$，则 $a \equiv b(\mod \dfrac{m}{\gcd(m,c)})$ 。

费马小定理

若 $p$ 是质数，$\forall a \in Z,a^{p} \equiv a (\mod p)$ 。当 $a,p$ 互质时，则有 $a^{p-1} \equiv 1(\mod p)$ 。

引理：当 $p$ 是质数时，其因子只有 $1$ 和 $p$ 两个。因此，若两个数相乘是 $p$ 的倍数，其中必然至少有一个是 $p$ 的倍数。
当 $a$ 不是 $p$ 的倍数时，不存在 $x \neq y$ 且 $1 \leq x,y < p$ 使得 $a \times y \equiv a \times x(\mod p)$ 而 $x-y<p$ 是 $p$ 的倍数，与 $1 \leq x,y < p$ 的限制矛盾。
进一步地，考虑 $1 \sim p-1$ 所有数，它们乘以 $a$ 之后在模 $p$ 意义下互不相同，说明仍得 $1 \sim p-1$ 所有数。
因此，$\prod_{i=1}^{p-1}i \equiv \prod_{i=1}^{p-1}ai(\mod p)$。又因为 $\prod_{i=1}^{p-1}i$显然不是 $p$ 的倍数，所以费马小定理成立。

欧拉定理

若正整数 $a,n$ 互质，$a^{\varphi(n)} \equiv 1(\mod n)$ 其中 $\varphi(n)$ 为欧拉函数。

设 $x_1,x_2 \cdots x_{\varphi(n)}$ 是模 $n$ 的简化剩余系，那 $ax_1,ax_2, \cdots ax_{\varphi(n)}$ 也是模 $n$ 的简化剩余系。
因为 $\gcd(a,n)=1$ ，$ax_1 \dot a x_2 \cdots ax_{\varphi(n)} \equiv x_1,x_2 \cdots x_{\varphi(n)} (\mod n)$ ，所以欧拉定理成立。

可以发现费马小定理是欧拉定理的一种特殊情况。

扩展欧拉定理

若 $a,n$ 互质，$a^b \equiv a^{b \mod \varphi(n)}$

若 $a,n$ 不互质，当 $b>\varphi(n)$ 时，$a^{b \equiv \varphi(n)+\varphi(n)}$

因为证明有些复杂，见oi wiki 。

扩展欧拉定理可以用来降幂，当幂太大时，此公式可以减小复杂度，而当 $b< \varphi(n)$ 幂比较小，就没有必要降幂了。

例题：P4139 上帝与集合的正确用法

线性同余方程

裴蜀定理

定义： $a,b$ 是不全为零的整数，对于任意整数 $x,y$ ， $\gcd(a,b) \mid ax + by $ ，且存在整数 $x,y$，使得 $ax +by = \gcd(a,b) $。

逆定理： 设 $a,b$ 是不全为零的整数，若 $d>0$ 是 $a,b$ 的公约数，且存在整数 $x,y$，使得 $ ax +by = d$，则 $d = \gcd(a,b)$ 。

特殊地，设 $a,b$ 是不全为零的整数，若存在正整数 $x,y$ ，使得 $ax +by =1 $ ，则 $a,b$ 互质。

当有 $n$ 个数时，此定理依然成立。

例题： P4549 【模板】裴蜀定理

code

#include<bits/stdc++.h>
using namespace std;
int n;
int gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y); 
}
int main()
{
	scanf("%d",&n);
	int x,y;
	cin>>x;
	for(int i=2;i<=n;i++)
	{
		cin>>y;
		x=gcd(x,y);
	}
	cout<<abs(x)<<endl;
	return 0;
 }

扩展欧几里得算法

上文裴蜀定理，讲述了存在整数 $x,y$，使得 $ax +by = \gcd(a,b) $ ，这里讲述如何求解 $x,y$ 。

我们设 $d=gcd(a,b)$。可以用辗转相除法法求出两个数的 $ \gcd$ ，所以我们假设它的另一个解是$x2,y2$，满足

\[b \times x2+(a \bmod b) \times y2=gcd(a,b) \]

也就是

\[b \times x2+(a \bmod b) \times y2=a \times x+b \times y \]

又因

\[a \mod b=a-b \times (a/b) \]

代入拆开得

\[a \times y2+(x2-y2 \times (a/b))=a \times x+b \times y \]

可得一个解

\[x=y2,y=x2-y2*(a/b) \]

现在发现只需要求出 $x2,y2$ 而我们观看一下求 $x,y$ 的式子，就是辗转相除法的式子，所以我们只需递推求一下 $x2,y2,x3,y3$等。

考虑一下递推边界，当递推到$b=0$ 时,

\[a \times x+b \times y= \gcd(a,b) \]

可转换成

\[a \times x= \gcd(a,b)=a \]

显然 $x=1，y \in Z$ 时，方程成立。

这样就求出了方程的一组特解，我们设为 $x_0,y_0$ 。

显然不定方程 $ax +by = \gcd(a,b) $ 有无穷解，所以要求通解形式。

可以知道 $ \Delta(ax)+\Delta(by)=0$ ，设 $\Delta =\lvert \Delta (ax) \rvert = \lvert \Delta (by) \rvert$，那 $a,b \mid \Delta$，$lcm(a,b) \mid \Delta$ ，所以 $ \Delta x$ 是 $\dfrac{lcm(a,b)}{a}=\dfrac{b}{d}$ 的倍数，$ \Delta y$ 是 $\dfrac{lcm(a,b)}{b}=\dfrac{a}{d}$ 的倍数。

所以通解为：

\[\begin{aligned} \begin{cases} x=x_0+\dfrac{b}{d} \times k\\ y=y_0-\dfrac{a}{d} \times k\\ \end{cases} \end{aligned} \]

这里 $k \in Z$。

实际做题时，会让求 $x$ 的最小正整数解，设 $t= \dfrac{b}{d}$

\[x=(x \mod+t) \mod t \]

特解的数据范围:ycx 的文章关于 exgcd 求得特解的数值范围

线性同余方程

定义：形如 $a \times x\equiv c (\mod b) ,a,b \in Z$ 的方程叫做线性同余方程。

求法：

原式转换成 :

\[a \times x + b \times y=c，y \in Z \]

这个式子和扩展欧几里得算法可以求的式子有点关联。

\[a \times x+b \times y=gcd(a,b) \]

设 $d=\gcd(a,b)$ ，由裴蜀定理可知，方程有解当 $d \mid c$ 。

原式又可转成：

\[a \times \frac{\gcd(a,b)}{c} \times x+b \times \frac{\gcd(a,b)}{c} \times y=\gcd(a,b) \]

这样用扩展欧几里得算法就可以求出。

模板： P1082 [NOIP2012 提高组] 同余方程

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c,d,x,y;
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=1;
		return a;
	}
	int t=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return t;
}
signed main()
{
	scanf("%lld%lld",&c,&d);
	exgcd(c,d,x,y);
	printf("%lld",(x%d+d)%d);
	return 0;
}

线性同余方程组（中国剩余定理）

\[\begin{aligned} \begin{cases} x \equiv a_1 (\mod m_1)\\ x \equiv a_2 (\mod m_2)\\ \cdots \\ x \equiv a_n (\mod m_n)\\ \end{cases} \end{aligned} \]

中国剩余定理(crt)

上式子中 $a \in Z,m \in N^*,(a,m)=1$。

求解方法：

设 $M=m_1 \times m_2 \times \cdots m_n$。

$b_i=\dfrac{M}{m_i}$，$b_i^{-1}$ 为 $b_i$ 模 $m_i$ 下的逆元。

$x= \sum_{i=1}^{n} a_i \times b_i \times b_i^{-1}$

证明：

尝试为每个同余方程设一个 $ x_i,x_i \equiv a_i (\mod m_i)$，可以知道 $ x_i \equiv 0(mod m_j) j \neq i$，记为条件一。

那 $x_i$ 为 $b_i$ 的倍数，如果要满足条件一 $x_i=b_i\times a_i$ 即可，
那要满足上面新设的同余方程，让 $x_i \times b_i^{-1}$ 即可，如果要让所以 $x_i$ 合成一个 $x$，加起来就可以了。

扩展中国剩余定理(excrt)

上面没看懂？没关系有更好理解并适用更广的扩展中国剩余定理（excrt），它不要求模数互质。

本质就是合并方程，我们把两个方程合并成新一个方程，依次类推就可以求解方程组了。

具体的说：合并方程 $x \equiv a_1 (mod m_1)$ 和 $x \equiv a_2 (mod m_2)$。

设 $x = a_1+p \times m_1 $，所以

\[a_1 +p \times m_1 \equiv a_2 (mod m_2) \]

即：

\[p \times m_1 +q \times m_2 \equiv a_2 - a_1 (mod m_2) \]

这个地方可以用 exgcd 求解。

最后合并得到：

\[x \equiv a_1 +p \times m_1(mod (lcm(m_1,m_2))) \]

根据 裴蜀定理 ，$gcd(m_1,m_2)$ 不是 $a_2-a_1$ 因数时，方程无解。

模板：

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[20],b[20],ans,M=1,t[20],m[20];
int x,y;
int exgcd(int a,int b)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	exgcd(b,a%b);
	int t=y;
	y=x-a/b*y;
	x=t;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>b[i]>>a[i],M*=b[i];
	for(int i=1;i<=n;i++)
	{
		exgcd(M/b[i],b[i]);
		t[i]=x;
		t[i]=(t[i]%b[i]+b[i])%b[i];
	}
	for(int i=1;i<=n;i++)
	{
		ans+=a[i]*(M/b[i])*t[i]%M;
	}
	cout<<ans%M<<endl;
	return 0;
}

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

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e7+10;
int n;
int m[N],X[N];
int  exgcd(int a, int b,int &x,int &y)
{
	if(b == 0) 
	{ 
		x = 1;
		y = 0;
		return a;
	} 
	int d=exgcd(b, a % b,x,y);
	long long tx = x;
	x = y;
	y = tx - a / b * y; 
	return d;
}
int mul(int a,int b,int mod)
{
	int res=0;
	while(b)
	{
		if(b&1)res=(res+a)%mod;
		a+=a;
		a%=mod;
		b>>=1;
	}
	return res;
}
signed main()
{
	int x,y,ans=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	cin>>m[i]>>X[i];
	int a1=X[1],m1=m[1];
	for(int i=2;i<=n;i++)
	{
		int a2=X[i],m2=m[i];
		int a=m1,b=m2,c=(a2-a1%m2+m2)%m2;
		int d=exgcd(a,b,x,y);
		if(c%d!=0)
		{
			puts("-1");
			return 0;
		}
		x=mul(x,(c/d),(b/d));
		ans=a1+x*m1;
		m1=m2/d*m1;
		ans=(ans%m1+m1)%m1;
		a1=ans;
	}
	cout<<ans<<endl;
	return 0;
}

乘法逆元

定义

如果一个线性同余方程 $ax \equiv 1 (\mod b)$ 则 $x$ 称为 $a \mod b$ 的逆元，记作 $a^{-1}$。

应用： 上文提到除法无法直接取模，而用乘法逆元就可以求出。

根据定义可知 $a \times a^{-1}=1$ ，那

\[a \div b=\dfrac{a \times 1}{b}= \dfrac{a \times b \times b^{-1}}{b}=a \times b^{-1} \]

求解方法

求单个数的乘法逆元

当模数 $p$ 为质数时，可以用 费马小定理 求解

由定义知，$x$ 为 $a$ 的乘法逆元

\[ax \equiv 1 (\mod p) \]

再由费马小定理得：

\[ax \equiv a^{p-1} (\mod p) \]

所以

\[x \equiv a^{p-2} (\mod p) \]

用快速幂就可以求出

code

int qpow(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}
int main()
{
	a=qpow(a,p-2);//求 a 的逆元
}

当 $p$ 不为质数, $\gcd(a,p)=1$ 时，可以用扩展欧几里得算法求出。（$p$ 不为质数时也可以求）。

求乘法逆元本质上就是求线性同余方程，用求线性同余方程的方法求就可以了。

线性求 $1 \cdots n$ 的逆元

用递推来求逆元，当递推到 $i$ 时，设 $k= \lfloor \dfrac{p}{i} \rfloor ,j= p \mod i$，所以

\[p=k \times i + j \]

由此又可以推出

\[k \times i + j \equiv 0 (\mod p) \]

两边同乘 $i^{-1} \times j^{-1}$ 得：

\[j^{-1} \times k+i^{-1} \equiv 0(\mod p) \]

所以

\[i^{-1} \equiv -k \times j^{-1} (\mod p) \]

既然是递推式，就要关注递推的起始项，当 $i=1$ 时，$1$ 的模任何数的逆元都是 $1$。

code

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (p - p / i) * inv[p % i] % p;
}

代码中 $p - p/i$ 是为了防负数。

求任意 $n$ 个数的逆元

要求 $a_1 \cdots a_n$ 的逆元。

定义两个数组 $s，sv$ ，$s_i$ 表示前 $i$ 个数的乘积， $sv_i$ 表示前 $i$ 个数的逆元的乘积，那这样 $a_i$ 的逆元就是 $s_{i-1} \times sv_i$ 。

递推边界 $s_0=1$，$sv_n=s_n$ 的逆元。

code

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

原根

阶

热门相关：无敌大佬要出世帝少夜宠：小甜妻，乖！永恒王权重生之大文豪九阳剑圣