同余和逆

同余

定义

a % m = b % m,记为a = b(mod m),称a和b模m同余,m为a,b的模

一元线性同余方程

定义

已知a,b,m.求未知整数x

ax = b(mod m)

由同余定义得ax - b是m的y倍(y为未知整数)

得ax + my = b(也就是二元线性丢番图方程),可以直接用解二元线性丢番图方程的方法解,也可以用逆的方法(下文逆应用写了)

定理

如果gcd(a,m) % b != 0方程无解

反之有gcd(a,m)个模m不同余的解(就是在模m的意义下有这么多个解)

比如a和m互素,就只有一个解

***!!!重要!!!***我才搞清楚原来要注意模m的意义下,比如a = 1, m = 13,如果没有模m的意义下x可以取1,14,….反之只有1

我们就可以得到一个推论如果 p 是质数那么在模p意义下的所有1到p-1的数的乘法逆元都是唯一的。

如果p不是质数,只是有可能没有解,但还是可以的

逆

定义

给定整数a,满足gcd(a,m) = 1,称ax = 1(mod m)的一个解为a模m的逆,写做a^-1^(这里a * a^-1^等于1哦)

比如8x = 1(mod31)解可以是2,4等(这里是没有模31的意义下的前提)

求解方法

拓展gcd

ax = 1(mod m)转换成ax + my = 1

这里a,m是互素的,ax + my = gcd(a, m)即(1)

拓展gcd得到特殊解x0,通解就是x0+ m*n

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

得到的x是一个特解,取到最小正整数就可以了,在模m的范围里

费马小定理

n为素数,a为正整数并且和n互素,则有a^n-1^ = 1(mod n)

得出a * a^n-2^ = 1(mod n)

a^n-2^modn就是a模n的逆

递推求多个逆

设p = k*i + r(r是余数),转换成k * i + r = 0(mod p)

p = k*i + r用常见的同余方程字母就是m = ax + m%a

乘上i^-1^, r ^-1^得到k*r ^-1^+i^-1^ = 0(mod p)

移位i^-1^ = -k * r ^-1^

即i^-1^ = -(p/i) * r ^-1^ (mod p),得到了i与当前逆元的关系

因为r小于i所以r ^-1^我们在之前一定求过

注意我们还需要保证i^-1^ > 0,故在方程右边加上p来取正,即p - p/i

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

应用

求解同余方程

对于ax = b(mod m),我们求出了a^-1^,两边同乘a^-1^

得到x = a^-1^b(mod m)

除法取模

对于a/b(mod p),我们可以先求出b^-1^,然后*a,再mod p就是解了

a * a^-1^是可以消成1的在模的意义下

同余方程组

定义

形如

x = a1(mod m1)

x = a2(mod m2)

…….

x = ar(mod mr)

求解方法

中国剩余定理(CRT,孙子定理)

使用前提:m1,m2,m3…..mr互素

公式:x = (a1M1M1^-1^ + a1M1M1^-1^ + …. + a1M1M1^-1^)(mod M)

M = m1m2m3…mr

Mi = M/mi

Mi^1^为Mi模mi的逆元

拓展CRT

https://www.luogu.com.cn/problem/P4777

核心思路是不断合并两个同余式,直到只剩一个

x = a(mod m)可以转换成x = a + km的形式

计算步骤

1:合并等式

x = a1 + Xm1(式1)

x = a2 + Ym2(式2)

得a1 + Xm1 = a2 + Ym2

移项Xm1 - Ym2 = a2 - a1

2:求解

Xm1 - Ym2 = a2 - a1即二元线性丢番图方程,exgcd可以得到特解X0

通解X = X0 + m2/gcd(m1,m2) * n

代入式1

3:新式

x = a1 + m1 X0 + m1m2/gcd(m1,m2) * n

由式1:x0 = a1 + m1 X0

得x = x0 + m1m2/gcd(m1,m2) * n

新方程x = a + Xm

a = x’

m = m1m2/gcd(m1,m2)