线性同余与乘法逆元

欧几里得算法

$$\forall a,b\in \N,\gcd(a,b)=\gcd(b,a\bmod b)$$

证明：

$$考虑记a与b的公因数为d\\\because \exist t,k,r\in\N,b=t\cdot d,a=k\cdot (t \cdot d)+r\\\because d\mid b,d\mid a\\\therefore \exist x\in\N,x\cdot d=a=k⋅(t⋅d)+r\\\quad \Leftrightarrow x=\dfrac{k⋅(t⋅d)+r}{d}=kt+\dfrac{r}{d}\\\because x\in \N\\\therefore d\mid r\\\therefore d\mid (a\bmod b)\\\therefore a\bmod b 的因数集与a与b的公因数集相同\\\therefore \gcd(a,b)=\gcd(b,b\bmod a)$$

此算法也常称为辗转相除法。

#include<bits/stdc++.h>
using namespace std;
int a,b;
int gcd(int x,int y)
{
	if(y==0) return x;
	int r=x%y;
	return gcd(y,r);
}
int main()
{
	cin>>a>>b;
	cout<<gcd(a,b);
	return 0;
}

裴蜀定理

$对于a,b\in \N，x,y\in\Z，则关于x,y的不定方程有$

$$ax+by=\gcd(a,b)$$

证明：

$$先考虑证明~ax+by 的和为\gcd(a,b)倍数\\\because \exist x',y'\in\N,a=x'\cdot\gcd(a,b),b=y'\cdot\gcd(a,b)\\\therefore ax+by=x\cdot x'\gcd(a,b)+y\cdot y'\gcd(a,b)\\\qquad\qquad\,\,\,=\gcd(a,b)\cdot(xx'+yy')\\\therefore \gcd(a,b)\mid (ax+by)\\\therefore \forall t\in\Z,ax+by=t\cdot \gcd(a,b)$$

显然只有当等式右边为$\gcd(a,b)$或$\gcd(a,b)$倍数时才存在整数解。

---

扩展欧几里得算法

我们再来考虑如何找到这个不定方程的一个特解。

$$考虑当 b=0时，显然有一对(x,y)，使得(x,y)=(1,0)时满足要求，即a+0=\gcd(a,0)\\考虑当b\ne 0时,根据欧几里得算法,有 \gcd(a,b)=\gcd(b,a\bmod b)\\\therefore \exist x',y'\in \Z,\, ax+by=bx'+(a\bmod b)y'\\ \,\,\,\,=bx'+(a-\left\lfloor\dfrac{a}{b}\right\rfloor \cdot b)y'\\ \,\,\,\,=bx'+ay'-\left\lfloor\dfrac{a}{b}\right\rfloor by'\\\,\,\,\,=ay'+b(x'-\left\lfloor \dfrac{a}{b}\right\rfloor y')\\x=y'\\\quad y=x'-\left\lfloor\dfrac{a}{b}\right\rfloor y'$$

因此，只需求出$x’,y’$就可以得到$x,y$，而$x’,y’$可以由方程右边为 $\gcd(b,a\bmod b)$ 时得到，这不就是一个欧几里得算法的递归过程吗？我们往上层层递归，直到当b为0时我们就可以得到$(x,y)=(1,0)$，然后我们就可以运用上述公式递归求得 $(x,y)$

解决这种不定方程的问题常在欧几里得算法中实现，因此被称为扩展欧几里得算法，也称为$exgcd$。

#include <bits/stdc++.h>
using namespace std;
int a,b;
int x,y;
int exgcd(int l,int r)
{
	if(r==0)
	{
		x=1;
		y=0;
		return l;
	}
	int d=exgcd(r,l%r);
	int t=x;
	x=y;
	y=t-l/r*y;
	return d;
}
int main()
{
	cin>>a>>b;
	int ans=exgcd(a,b);
	cout<<x<<" "<<y<<" "<<ans;
	return 0;
} 

继续观察这个不定方程，此时我们已经可以用上述算法找到一个特解$(x_0,y_0)$，我们现在来思考如何得到这个不定方程的通解。

$$我们考虑从方程的特解入手，现在我们已经拥有了两个不定方程：\\\mathbb{1.}ax+by=\gcd(a,b)\\\mathbb{2.}ax_0+by_0=\gcd(a,b)\\由~\mathbb{1}~式减去~\mathbb{2}~式得：~a(x-x_0)+b(y-y_0)=0\\\Leftrightarrow a(x-x_0)=b(y_0-y)\\考虑等式两边同时除以\gcd(a,b)\\~\\\dfrac{a}{\gcd(a,b)}(x-x_0)=\dfrac{b}{\gcd(a,b)}(y_0-y)\\~\\显然有\dfrac{a}{\gcd(a,b)}与\dfrac{b}{\gcd(a,b)}互质\\~\\\therefore \forall t\in\Z，x-x_0=t\cdot \dfrac{b}{\gcd(a,b)}，y_0-y=t\cdot \dfrac{a}{\gcd(a,b)}\\~\\\therefore x=x_0+t\cdot \dfrac{b}{\gcd(a,b)}\\\quad y=y_0-t\cdot\dfrac{a}{\gcd(a,b)}$$

于是我们就得到了由不定方程特解得到通解的方法。

接下来我们再来扩展一下，考虑如何求出不定方程中 $x$ 的最小非负整数解。

$$考虑到我们是从 x=x_0+t\cdot\dfrac{b}{\gcd(a,b)} 得到所有的x的，因此，想要求最小的非负整数x，实际上是要满足以下式子\\~\\x_0+t\cdot\dfrac{b}{\gcd(a,b)}\ge0,x_0+(t+1)\cdot\dfrac{b}{\gcd(a,b)}\le 0\\由于t可取任意整数，因此上述式子等价于\\x_0-t\cdot\dfrac{b}{\gcd(a,b)}\ge0,x_0-(t+1)\cdot\dfrac{b}{\gcd(a,b)}\le 0\\~\\很显然，此时最小的x非负整数值可以由x_0\bmod \dfrac{b}{\gcd(a,b)}得到\\但考虑到x_0有可能是负数，此时我们应该考虑如何将负数取模转换为正数取模\\~\\对于负数x\bmod m的值，考虑\bmod 的性质，这个式子等价于((x\bmod m)+m)\bmod m\\~\\因此我们考虑对(x_0\bmod \dfrac{b}{\gcd(a,b)})+\dfrac{b}{\gcd(a,b)}来确保式子永远为正数，后在对其取\bmod\\~\\因此，x的最小非负整数解为 ((x_0\bmod \dfrac{b}{\gcd(a,b)})+\dfrac{b}{\gcd(a,b)})\bmod \dfrac{b}{\gcd(a,b)}$$

例题
https://www.luogu.com.cn/problem/P1516

---

线性同余方程

给定正数$a,b,m$，求一个整数$x$满足$a\cdot x\equiv n\pmod b$，或者无解。
由于未知数是一次的，因此我们称 $ax\equiv n\pmod b$ 为线性同余方程（一次同余方程）。

$我们考虑同余方程 ax\equiv n\pmod b，则定有b\mid(ax-n)\\因此有y\in\Z,使得ax-n=by，即ax-by=n，由于y可取任意整数，因此等价于 ax+by=n$

于是我们就将同余方程转换为了一个不定方程，此方程当且仅当 $\gcd(a,b)\mid n$ 时存在整数解。
当存在整数解时，我们可以通过扩展欧几里得算法求出不定方程 $ax+by=\gcd(a,b)$时的一个特解$(x_0,y_0)$。
由于$n=\dfrac{n}{\gcd(a,b)}\cdot \gcd(a,b)，$因此不定方程 $ax+by=n$的特解即为 $(x_0\cdot \dfrac{n}{\gcd(a,b)},y_0\cdot \dfrac{n}{\gcd(a,b)})$
转换可得线性同余方程 $ax\equiv n\pmod b$ 的一个特解$x_0\cdot \dfrac{n}{\gcd(a,b)}$。

一个定理：

$对于一个线性同余方程ax\equiv n\pmod b$，都有 $\gcd(a,b)个\bmod b不同余的解，若已知第一个解为x_0，则x_i=x_0+i\cdot \dfrac{b}{\gcd(a,b)}，i\in\Z,0\le i<\gcd(a,b)。$

证明：

$$考虑证明x_i=x_0+i\cdot \dfrac{b}{\gcd(a,b)}是方程的解：\\\because ax_i\equiv n\pmod b\\\Leftrightarrow a(x_0+i\cdot \dfrac{b}{\gcd(a,b)})\equiv n\pmod b\\\Leftrightarrow ax_0+a\cdot i\cdot \dfrac{b}{\gcd(a,b)}\equiv n\pmod b\\\Leftrightarrow ax_0+i\cdot \operatorname{lcm}(a,b)\equiv n\pmod b\\\because i\cdot \operatorname{lcm}(a,b)\bmod b=0\\\therefore ax_0+i\cdot \operatorname{lcm}(a,b)\equiv ax_0\pmod b\\\therefore ax_i\equiv ax_0\equiv n\pmod b\\因此x_i=x_0+i\cdot \dfrac{b}{\gcd(a,b)}是方程的解\\~\\\because0\le i<\gcd(a,b)\\\therefore 0\le i\cdot \dfrac{b}{\gcd(a,b)}<b\\\therefore x_{0\cdots i}显然\bmod b互不同余，且有\gcd(a,b)个解$$

#include<bits/stdc++.h>
using namespace std;
int a,n,b;
int x,y;
int exgcd(int l,int r)
{
	if(r==0)
	{
		x=1;
		y=0;
		return l;
	}
	int d=exgcd(r,l%r);
	int t=x;
	x=y;
	y=t-l/r*y;
	return d;
}
void mod_slover()
{
	int g=exgcd(a,b);
    if(n%g!=0) exit(0);//判断是否有解 
    x=(x*(n/g))%b;
    x=x*(n/g);  //求解 
    x=((x%(b/g))+(b/g))%(b/g);  //取得最小正整数解 
    for(int i=0;i<g;i++)
    {
  	  cout<<x+i*(b/g)<<endl;
    }
    //枚举g个不同余的解 
}
int main()
{
  cin>>a>>n>>b;
  mod_slover();
  return 0;
}

例题
https://www.luogu.com.cn/problem/P1082
https://www.luogu.com.cn/problem/P5656

---

乘法逆元

或许乘法逆元有一个更加感性的理解：同余方程余数意义下的倒数

$考虑a,b,m\in\Z,\gcd(b,m)=1,若存在x\in\Z，且满足\dfrac{a}{b}\equiv ax\pmod m，则称x为b的\color{Blue}乘法逆元\~\\\color{Black}若\dfrac{a}{b}\equiv ax\pmod m，则有a\equiv abx\pmod m\Leftrightarrow \color{Blue}bx\equiv 1\pmod m，\color{Black}因此这也是乘法逆元的一种定义。$

因此我们就可以通过解$bx\equiv 1\pmod m$这个线性同余方程，得到最小正数解$x$，便得到$b$的乘法逆元。

知道了这么个名字就很酷的东西有什么用呢？观察乘法逆元的第一个定义，有了它我们就可以处理有理数取余(特别是当$a,b$特别大的情况下，同余性质很重要)。

不想贴了，就是求线性同余方程的解

利用$b$在$\bmod m$意义下的乘法逆元$b^{-1}$，我们可以得到$\dfrac{a}{b}\bmod m$的值，即为$ab^{-1}\bmod m$

例题
https://www.luogu.com.cn/problem/P2613

线性求逆元

考虑给出$p$，若要求$[1,p]$内所有数在$\bmod~p$意义下的乘法逆元，是否具有复杂度优的递推公式呢？

$$考虑求i的乘法逆元，则有\exist k,r\in \Z，p=k\cdot i+r，显然\\k\cdot i+r\equiv 0\pmod p\\将同余方程两边同时乘以 i 的逆元 i^{-1}\\k\cdot (i\cdot i^{-1})+r\cdot i^{-1}\equiv 0\pmod p\\k+r\cdot i^{-1}\equiv0\pmod p\\移项得\\r\cdot i^{-1}\equiv -k\pmod p\\再尝试将r消掉，于是乘以r^{-1}\\i^{-1}\equiv-k\cdot r^{-1}\pmod p\\考虑k=\left\lfloor\dfrac{p}{i}\right\rfloor，r=p\bmod i，带入\\i^{-1}\equiv-\left\lfloor\dfrac{p}{i}\right\rfloor\cdot(p\bmod i)^{-1}\pmod p\\考虑-\left\lfloor\dfrac{p}{i}\right\rfloor \bmod p可以转换为 p-\left\lfloor\dfrac{p}{i}\right\rfloor\\~\\i^{-1}\equiv (p-\left\lfloor\dfrac{p}{i}\right\rfloor)(p\bmod i)^{-1}\pmod p$$

考虑使用$inv_i$ 表示$i$在$p$意义下的乘法逆元，将$\pmod p$提出来，得

$$inv_i=(p-\left\lfloor\dfrac{p}{i}\right\rfloor)(p\bmod i)^{-1}\bmod p$$

这就是逆元的递推式，我们就可以线性求逆元了。

#include<bits/stdc++.h>
using namespace std;
int p;
int inv[100010];
int main()
{
  cin>>p;
  inv[1]=1;
  for(int i=2;i<=p;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;
  for(int i=1;i<=p;i++)
    cout<<inv[i]<<endl;
  return 0;
}

当然，我们也可以考虑利用费马小定理来求乘法逆元

$$由于当p为质数时，有a^p\equiv a\pmod p\\ \therefore a^{p-1}\equiv 1\pmod p\Leftrightarrow a\cdot a^{p-2}\equiv 1\pmod p$$

因此有当$p$为质数时，$a^{p-2}\bmod p$是$a$在$\bmod p$意义下的乘法逆元。
我们可以使用快速幂优化求$a^{p-2}$的过程，因此我们可以得到一个$\Theta(n\log_2n)$求逆元的算法。

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,p;
long long inv[30000010];
long long ksm(int a,int b)
{
	long long ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
signed main()
{
  cin>>n>>p;
  cout<<1<<'\n';
  for(int i=2;i<=n;i++)
  {
  	cout<<ksm(i,p-2)<<'\n';
  }
  return 0;
}

例题
https://www.luogu.com.cn/problem/P3811

---

总结

例题：
https://www.luogu.com.cn/problem/P5431