一次同余方程
| 一次同余方程 | |
|---|---|
| 术语名称 | 一次同余方程 |
| 英语名称 | linear congruence |
| 别名 | 线性同余方程 |
一次同余方程/线性同余方程(linear congruence)指形如 [math]\displaystyle{ a x \equiv b \pmod n, n\not\mid a }[/math] 的同余方程。如果将各项都移至左侧，其左侧是未知数的最高次数为 1 的整式，
定义
对正整数 [math]\displaystyle{ n }[/math] 和整数 [math]\displaystyle{ a, b }[/math] ，且 [math]\displaystyle{ n \not\mid a }[/math] ，形如 [math]\displaystyle{ ax \equiv b \pmod n }[/math] 的方程称为一次同余方程/线性同余方程(linear congruence)。
若 [math]\displaystyle{ (\exists c \in \mathbb{Z})(ac \equiv b \pmod n) }[/math] ，则称 [math]\displaystyle{ x \equiv c \pmod n }[/math] 为一次同余方程 [math]\displaystyle{ ax \equiv b \pmod n }[/math] 的解。
注：这里的解是基于同余，而不是相等。
解
有解条件
若 [math]\displaystyle{ \operatorname{gcd}(a, n) \mid b }[/math] ，则一次同余方程 [math]\displaystyle{ ax \equiv b \pmod n }[/math] 有 [math]\displaystyle{ \operatorname{gcd}(a, n) }[/math] 个解；否则，同余方程 [math]\displaystyle{ ax \equiv b \pmod n }[/math] 无解。
解法
一次同余方程有很多解法。
对 [math]\displaystyle{ b = 1 }[/math] 的情况，即 [math]\displaystyle{ ax \equiv 1\pmod n }[/math] ：要么互质，解是模逆；要么不互质，无解。有解时可由大衍求一术求解。
对更广泛的情况，可以使用形式分数法求解。即通过对 [math]\displaystyle{ \tfrac{a}{b} }[/math] 做：
- 上下同乘与模数互质的数
- 对分子或分母加减模数 [math]\displaystyle{ n }[/math] 的倍数
- 约分
直至其化为 [math]\displaystyle{ \tfrac{k}{1} }[/math] 的形式， [math]\displaystyle{ k }[/math] 即是解。