同余方程&孙子定理&模线性同余方程

参考博客

一次同余方程

a * x \equiv b (m o d <mtext>            </mtext> n)

分情况讨论

若有 ,根据欧几里得扩展，存在 l,m使得，等式两边同时模n，得 ,对于 $a * x \equiv b (m o d <mtext> </mtext> n)$ $a * l * x \equiv b * l (m o d <mtext> </mtext> n)$ $x \equiv b * l (m o d <mtext> </mtext> n)$

若有 , 对于 $a * x \equiv b (m o d <mtext> </mtext> n)$

移项

a * x - b \equiv 0 (m o d <mtext>            </mtext> n)

即

n | (a * x - b)

已知

d | a, d | n

于是

d | b

所以同余方程有解的条件是

d | b

令

a_{1} = a / d, b_{1} = b / d, n_{1} = n / d

则有

n_{1} | (a_{1} * x - b_{1})

即为

a_{1} * x \equiv b_{1} (m o d <mtext>            </mtext> n_{1}) <mtext>            </mtext>     <mtext>            </mtext>     <mtext>            </mtext>     <mtext>            </mtext>     <mtext>            </mtext> 且 (a_{1}, n_{1}) = 1

就变成情况1，可以解出此时的

x \equiv b_{1} * l (m o d <mtext>            </mtext> n_{1})

即

x = b_{1} * l + n_{1} * t

t的取值范围为(0,d-1)

中国剩余定理

解线性同余方程，运用拉格朗日插值法，得孙子定理

模板

int m[maxn];
int  China(int a[],int n,int b[])//其中a[]是模数，b[] 是余数
{
    int M = 1;
    for(int i = 0;i < n;++i)
        M *= a[i];
    int ans = 0;
    for(int i = 0;i < n;++i)
    {
        int Mi = M/a[i];
        LL x,y;
        ex_gcd(Mi,a[i],x,y);
        ans += b[i] * x*Mi;
    }
    ans = (ans%M + M) %M;
    return ans;
}

扩展

合并两个模数
假设


令


两式相减得
利用欧几里得扩展求出带入（1）求出一个特解

y = x (m o d <mtext>            </mtext> l c m (m_{1}, m_{2}))

证明 x与y同余于

l c m （ m_{1}, m_{2})

m_{1} | x - y

m_{2} | x - y

所以

l c m (m_{1}, m_{2}) | x - y

,所以x和y关于

l c m (m_{1}, m_{2})

同余

同余方程&amp;孙子定理&amp;模线性同余方程

参考博客

一次同余方程

中国剩余定理

模板

扩展

同余方程&孙子定理&模线性同余方程