引理：对于方程 ax \equiv c \pmod{b}，其等价于方程 ax+by = c，其中 y = \lfloor \frac c b \rfloor - \lfloor \frac {ax} {b} \rfloor
证明：
将原方程的同余符号转化为等号得：
ax\,mod\,c = b\,mod\,c
由模的定义（a\,mod\,b = a - b \times \lfloor \frac a b \rfloor）得：
ax - b \times \lfloor \frac {ax} {b} \rfloor = c - b \times \lfloor \frac c b \rfloor
移项并合并同类项得：
ax + (\lfloor \frac c b \rfloor - \lfloor \frac {ax} {b} \rfloor)b = c
令 y = \lfloor \frac c b \rfloor - \lfloor \frac {ax} {b} \rfloor，即可得 ax + by = c，从而得证。
2. 判断方程有整数解的条件
引理：方程 ax + by = c 有整数解的充要条件是 \operatorname{gcd}(a,b) \mid c
在证明这个命题之前，先证明如下定理：
引理（裴蜀定理）：对于 \forall a, b \in Z,\exists x,y \in Z 使得 ax + by = \operatorname{gcd}(a,b)
证：
首先，显然有 \operatorname{gcd}(a,b) \mid a，\operatorname{gcd}(a,b) \mid b 。由整除的性质可知 \forall x,y \in Z, \operatorname{gcd}(a,b) \mid (ax + by) 。设 s 为 ax + by 的最小正值，故有 \operatorname{gcd}(a,b) \mid s。
设 k = \lfloor \frac {a} {s} \rfloor, r = a\,mod\,s，则有 r = a - k(ax + by) = a(1 - kx) + b(-ky)，发现 r 也为 (a,b) 的线性组合，而 r 又在模 s 剩余系中，故 r \in [0, s - 1]，又由于 s 为最小正值，故 r = 0。
所以 s \mid a，同理 s \mid b，根据两个数的公约数必为这两个数的最大公约数的约数，有 s \mid \operatorname{gcd}(a,b)，而上文已证明\operatorname{gcd}(a,b) \mid s ，故 s = \operatorname{gcd}(a,b) 。
进而得证，故 ax + by = \operatorname{gcd}(a,b) 这个方程一定有解……
考虑将 ax + by = \operatorname{gcd}(a,b) 变为 ax+by = c：
int exgcd(int a, int b, int &x, int &y)
//使用方法:初始调用本函数时调用原方程的a和b
{
if (b == 0)//递归终点
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);//注意这里y与x是反过来写的
y -= a / b * x;
return d;
}
4. 例题
P1082 同余方程
P1516 青蛙的约会
二、线性同余方程组
1. 方程简介
定义：线性同余方程组为形如：
\begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \\ \vdots \\ x \equiv b_n \pmod{a_n} \end{cases}
typedef long long ll;
inline ll CRT(int *a, int *b)
{
ll A = 1, x, y, ans = 0;
for (int i = 1; i <= n; ++i)
{
A *= a[i];
b[i] = (b[i] % a[i] + a[i]) % a[i];//防止 b[i] 出现负数
}
for (int i = 1; i <= n; ++i)
{
ll res = A / a[i];//求 m[i]
exgcd(res, a[i], x, y);//求 m[i] 逆元
x = (x % a[i] + a[i]) % a[i];
ans = (ans + mul(mul(x, res, A), b[i], A)) % A;
//mul 为龟速乘防爆 long long
}
return (ans + A) % A;
}
typedef long long ll;
inline ll exCRT(ll *a, ll *b, int n)
{
ll ans = b[1];//注意初始化
ll x, y, m = a[1];//这里的 m 是当前已经合并了的所有方程的 a[i] 的 lcm
for (int i = 2; i <= n; ++i)
{
ll B = ((b[i] - ans) % a[i] + a[i]) % a[i];//求两个要合并的方程 b 之差
ll d = exgcd(m, a[i], x, y);
x = mul(x, B / d, a[i]);//求出线性同余方程的解
ans += m * x;//求出 x0
m *= a[i] / d;//利用两个数的乘积等于这两个数 gcd 与 lcm 的乘积的原理更新 lcm
ans = (ans + m) % m;//合并方程的解
}
return ans;
}
不妨令 x = am - b，故原方程变为 A^{am - b} \equiv B \pmod{p} 。
方程两边同乘 A^b 得：
A^{am} \equiv A^bB \pmod{p}
然而还是考虑枚举……将 m 固定（这样也同时固定了枚举的范围），先枚举 b，将枚举过程中将对应的 A^bB 的值存进哈希表；后枚举 a，并同时通过查表找到一个对应的 b 使得方程成立，不难发现，整数 b 的枚举范围为 [0,m]，整数 a 的枚举范围为 [0,\frac {p} {m}]，故当 m = \sqrt{p} 时，时间复杂度最优，为O(\sqrt{p})。
故 BSGS 算法的时间复杂度为 O(\sqrt{p})。
Code：(由于自己写的哈希表常数太大，这里用 unordered_map 代替了哈希表)
unordered_map<int, int> V;
inline int BSGS(int A, int B, int p)
{
if (A % p == 0 && B) return -1;//判断无解的情况,这里无解返回-1
A %= p, B %= p;//小优化
if (B == 1) return 0;//当B为1时,A的0次方恰为1,与B在模p意义下同余
int m = floor(sqrt(1.0 * p)) + 1//注意sqrt()计算出的结果需上取整
V.clear();//清空哈希表
for (int i = 0, t = B; i < m; ++i, t = 1ll * t * A % p)
V[t] = i;//枚举a,并将对应的值插入哈希表
int j = power(A, m, p);//这里power为快速幂
for (int i = 1, t = j; i <= m + 1; ++i, t = 1ll * t * j % p)//注意乘1ll防爆int
{
if (V.count(t)) return i * m - V[t];//枚举b,并查表
}
return -1;//枚举完还未找到解,可知方程无解
}
（3）ExBSGS
当 A, p 不互质时，考虑将同余式 A^x \equiv B \pmod{p} 转化成等式 A^x + kp = B 。
设 d = \operatorname{gcd}(A, p)，将等式两边同除 d，式子将转化为 \frac{A} {d} A^{x - 1} + \frac{p} {d} k = \frac {B} {d}，令 p' = \frac {p} {d}，若此时 A, p' 仍不互质，则等式两边继续同除 d' = \operatorname{gcd}(A, p')，这样一直除到 A, p_i 互质为止（为了方便，我们将等式两边第 i 次同除后p 的值设为 p_i）。
假设我们两边同除了 y 次，设 d_i 为第 i 次两边同除时，\operatorname{gcd}(A, p_{i - 1}) 的值，则最终得到的式子为：
我们不妨设 C = \frac {A^y} {\prod_{i = 1}^y \limits d_i}, B' = \frac {B} {\prod_{i = 1}^y \limits d_i}, P' = \frac{p} {\prod_{i = 1}^y \limits d_i}, x' = x - y 。
故原方程被我们转化成了：
CA^{x'} \equiv B' \pmod{P'}
其中 A, P' 互质，而 C 不影响我们解方程，故直接套用上文的 BSGS 即可。
Code：
unordered_map<int, int> V;
inline int exBSGS(int A, int B, int p)
{
A %= p, B %= p;
if (B == 1) return 0;
if (!B && !A) return 1;
if (!A) return -1;
if (!B)//特判 B == 0 的情况
{
int res = 0, d = gcd(A, p);
while (d != 1)
{
++res, p /= d;
d = gcd(A, p);
if (p == 1) return res;
}
return -1;
}
int res = 0, d = gcd(A, p), C = 1;
while (d != 1)//计算 y(res)
{
if (B % d != 0) return -1;
p /= d, B /= d, C = 1ll * A / d * C % p;
++res, d = gcd(A, p);
if (C == B) return res;
}
V.clear();
int m = floor(sqrt(p)) + 1;//最后用 BSGS 解方程
for (int i = 0, t = B % p; i < m; ++i, t = 1ll * t * A % p)
V[t] = i;
int j = power(A, m, p);
for (int i = 1, t = 1ll * j * C % p; i <= m; ++i, t = 1ll * t * j % p)
//注意这里枚举时要多乘上一个 C
{
if (V.count(t)) return i * m - V[t] + res;//记得加上 y(res)
}
return -1;
}