线性同余方程求解

对于线性同余方程:$$ax \equiv b\pmod{n}$$ 其中 \(a > 0,n > 0\) 进行求解。
首先我们可以将其改写为线性不定方程的形式：$$ax + ny = b$$
注：以下讨论的方程的解都是整数解，非整数解不做讨论。

1. 解的情况

根据裴蜀定理：若 \(a,b\) 是整数,且 \(\gcd(a,b) = d\)，那么对于任意的整数 \(x,y\)，\(ax + by\) 都一定是 \(d\) 的倍数，特别地，一定存在整数 \(x,y\)，使 \(ax + by = d\) 成立。

我们可以得知，\(ax + ny\) 的值一定是 \(\gcd(a,n)\) 的倍数，那么:

当 \(b\) 为 \(\gcd(a,n)\) 的倍数时，原方程有整数解；反之则无整数解。

2. 解的数量

方程 \(ax \equiv b\pmod{n}\) 或者对模 \(n\) 有 \(d\) 个不同的解，或者无解，这里 \(d = \gcd(a,n)\)

3.求解

令 \(d = \gcd(a,n)\)，假设对某些整数 \(x'\) 和 \(y'\)，有 \(d = ax' + ny'\)。如果 \(d \mid b\)，则方程 \(ax \equiv b\pmod{n}\) 有一个解的值为 \(x_0\)，这里有 $$x_0 = x'\ (b/d)\ mod\ n$$

假设方程 \(ax \equiv b\pmod{n}\) 有解（即 \(d \mid b\)，这里 \(d = \gcd(a,n)\)），且 \(x_0\) 是该方程的任意一个解。因此，该方程对模 \(n\) 恰有 \(d\) 给不同的解，分别为 \(x_i = x_0 + i(n/d)\)，这里 \(i = 0,1,\cdots,d-1\)。

特例：

对任意 \(n > 1\)，如果 \(\gcd(a,n) = 1\)，则方程 \(ax \equiv b\pmod{n}\) 对模 \(n\) 有唯一解。

其实当 \(b = 1\) 时，这里求的 \(x\) 就是 \(a\) 对模 \(n\) 的乘法逆元。

对任意 \(n > 1\)，如果 \(\gcd(a,n) = 1\)，则方程 \(ax \equiv 1\pmod{n}\) 对模 \(n\) 或者有唯一解，或者无解。

证明以后再慢慢补。