浅谈同余问题

费马小定理与乘法逆元

首先对于费马小定理有$a^p\equiv a(mod\ m)\Rightarrow a^{p-1}\equiv 1(mod\ m)$($p$为质数)

另外若$a*x\equiv 1(mod\ p)$我们令$x$为$a$的逆元记为$a^{-1}$

所以我们可以得到$ a^{p-2}\equiv a^{-1}(mod\ m)$并且对于$\frac {a}{b}\equiv a*b^{-1}(mod\ p)$

由费马小定理可以得到欧拉定理即$a^{\varphi(p)}\equiv 1(mod\ p)$,当且仅当$p$为质数的时候$\varphi(p)=p-1$

欧拉定理还有一个推论$a^b\equiv a^{b\ mod\ \varphi (p)}(mod\ p)$,可以帮助我们做指数级取模

对于求解一个连续区间的逆元(LuoguP3811)我们有一种其它的方法

我们现在求解$i$的逆元,设$p=ki+r$,则$ki+r\equiv 0(mod\ p)$

同时乘上$i^{-1},r^{-1}$,则有$k*r^{-1}+i^{-1}\equiv 0(mod\ p)$

所以$i^{-1}\equiv-k*r^{-1}(mod\ p)$,如上可以线性求解

扩展欧几里得算法

已知$a,b$,求解方程$ax+by=gcd(a,b)$的一组解

当$b=0$的时候,$gcd(a,b)=a$,该方程的解为$x=1,y=0$

设我们已知方程$bx’+(a%b)y’=gcd(b,a%b)=gcd(a,b)$的一组解$(x’,y’)$

可以得到$bx’+(a-a/bb)y’=gcd(a,b)\Rightarrow ay’+b(x’-a/by’)=gcd(a,b)$

所以令$x=y’, y=x’-(a/b)y’$就可以得到接下来方程的解

1
2
3
4
5
6
inline void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if ( b == 0 ) { d = a; x = 1; y = 0; return ; }
exgcd(b, a % b, d, x, y);
LL t = x; x = y; y = t - (a / b) * y;
}

线性同余方程

已知$a,b,p$,求解方程$a*x\equiv b(mod\ p)$

这个很简单,可以将方程转化为$ax-py\equiv b$即可,用扩展欧几里得求解

中国剩余定理

我们需要求解方程组并且保证$p_i$两两互质
$$
\left{
\begin{array}{c}
x\equiv a_1(mod\ p_1) \
x\equiv a_2(mod\ p_2) \
\ldots\
x\equiv a_n(mod\ p_n) \
\end{array}
\right.
$$
我们可以令$P=\prod_{i=1}^n p_i,P_i=P/p_i$,$t_i$是$P_i$在模$p_i$意义下的逆元

则答案即为$x\equiv \sum_{i=1}^n a_iP_it_i(mod\ P)$

同余方程组

同上解方程组,但不保证$p_i$两两互质,所以我们需要用其它方法

可以用线性同余方程的方法求解任意两个方程,这样进行$n-1$次后就可以得到最后的答案