同余方程

2020年3月25日 · 11 views · 

同余方程是形如$a\equiv b\ \left(mod\ c\right)$的方程,表示$a\%c=b\%c$。
现在,已知a,c,m,求解$ax\equiv c\ (mod\ m)$。

推导过程:

把原始式子变形,构成扩展欧几里得能解的形式

$\left(ax-c\right)\%m=0$

$ax-c=my$

$ax-my=c$

通过解$ax^\prime-my^\prime=g$来达到解$ax-my=c$的目的

设$g=\gcd{\left(a,m\right)}$

则$\left(ax-my\right)%g=0$

若$c\%g=0$则方程有整数解。(因为下面算出来的结果要乘上 $c\%g=0$ ,如果 $c\%g!=0$则乘完会有小数 )

先解方程$ax^\prime-my^\prime=g$得$x^\prime,y^\prime$

用$x^\prime,y^\prime$表示$x,y$

把$ax^\prime-my^\prime=g$两边同时乘以$\frac{c}{g}$,得

$ax^\prime\cdot\frac{c}{g}+my^\prime\cdot\frac{c}{g}=c$

即$x=\frac{c}{g}x^\prime,y=\frac{c}{g}y^\prime$。

代码流程:

  • 求g=gcd(a,m)
  • 判断c mod g,即判断方程有无解
  • 把a,c,m带入并用欧几里得算法求得x’,y’
  • 求x

求其它解

由于$ax\prime-my\prime=g$有多组解,设$x_1$表示$x$的其它解,

设x1也满足方程$ax_1\equiv c\ (mod\ m)$

$∴ax\equiv ax_1\left(mod{m}\right)$

#把式子换一种方式表达

$∴(ax-ax_1)\%m=0$

$∴a\left(x-x_1\right)\%m=0$

#a和m都是g的倍数,所以同时除以g,不影响结果。

$∵g=\gcd{\left(a,m\right)}$

$∴a\%g=0,m\%g=0$

$∴\frac{a}{g}\left(x-x_1\right)\%\frac{m}{g}=0$

#$\frac{a}{g}\left(x-x_1\right)$一定是$\frac{m}{g}$的倍数,但是$\frac{a}{g}$又不是,所以$\left(x-x_1\right)$一定是

$∵\frac{a}{g}$ 与 $\frac{m}{g}$ 互质

$∴\left(x-x_1\right)$必定是$\frac{m}{g}$的倍数

$∴\left(x-x_1\right)\%\frac{m}{g}=0$

$∴x_1=x\pm\frac{m}{g}k$

//带求最小正整数解的版本
int con(int a, int b, int m)
{
	//ax≡b(mod m)
	int g = gcd(a, m);
	if (g % b != 0)
		return false;
	//ax'+by'=g
	int x, y;
	exgcd(a, m, x, y);
	x = b / g * x;
	while (x > 0)
		x -= m;
	while (x <= 0)
		x += m;
	return x;
}
返回

Steven's Website Copyright © 2020 Steven
Powerd by Wordpress & Theme by Steven
粤ICP备20028373号