线性同余方程

形如 \(ax\equiv b(\mod n)\) 的方程称为线性同余方程，从区间 \([0,n-1]\) 中求解 \(x\).

逆元求解。

假设 \(gcd(a,n)=1\)，两边同时乘上 \(a^{-1}\) 即可。

设 \(g=gcd(a,n)\)，左侧始终可以 被 \(g\) 整除，若右侧不可则无解。

若右侧可以被 \(g\) 整除，则将 \(a,b,n\) 同时除以 \(g\)，得到 \(a’x\equiv b'(\mod n’)\).

此时 \(gcd(a’,n’)=1\)，回到上面的情况。

所以解为 \(x\equiv x’+i*n'(\mod n),i\in[0,g-1]\)，个数为 \(g\) 个或 \(0\) 个。

扩展欧几里得算法求解。

方程可以写成 \(ax+nk= b\)，有解的充要条件是 \(gcd(a,n)|b\).

先算出 \(ax_0+nk_0=gcd(a,n)\)，之后两边同时除以 \(gcd(a,n)\) 再乘上 \(b\) 即为一组解。

即 \(a=\frac{x_0}{gcd(a,n)}b,k=\frac{k_0}{gcd(a,n)}b\).

若 \(gcd(a,n)=1,ax+nk=b\) 的一组特解为 \(x_0,k_0\)，则任意解可以写成 \(x=x_0+nt,k=k_0-at,t\) 为任意整数。

对于求一个最小整数解，\(x=(x\mod t+t)\mod t,t=\frac{n}{gcd(a,n)}\)

原文地址：http://www.cnblogs.com/safeng/p/16907874.html