形如 \(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)}\)
标签：方程,nk,gcd,equiv,线性,ax,同余,mod From： https://www.cnblogs.com/safeng/p/16907874.html