查看“︁一次同余方程”︁的源代码

[[分类:同余方程]]
{{InfoBox
|name=一次同余方程
|eng_name=linear congruence
|aliases=线性同余方程
}}
'''一次同余方程'''/'''线性同余方程'''('''linear congruence''')指形如 <math>a x \equiv b \pmod n, n\not\mid a</math> 的[[同余方程]]。如果将各项都移至左侧，其左侧是未知数的最高[[次数]]为 1 的[[整式]]，

== 定义 ==

对正整数 <math>n</math> 和整数 <math>a, b</math> ，且 <math>n \not\mid a</math> ，形如 <math>ax \equiv b \pmod n</math> 的方程称为'''一次同余方程'''/'''线性同余方程'''('''linear congruence''')。

若 <math>(\exists c \in \mathbb{Z})(ac \equiv b \pmod n)</math> ，则称 <math>x \equiv c \pmod n</math> 为'''一次同余方程 <math>ax \equiv b \pmod n</math> 的解'''。

注：这里的解是基于同余，而不是相等。

== 解 ==

=== 有解条件 ===

若 <math>\operatorname{gcd}(a, n) \mid b</math> ，则一次同余方程 <math>ax \equiv b \pmod n</math> 有 <math>\operatorname{gcd}(a, n)</math> 个解；否则，同余方程 <math>ax \equiv b \pmod n</math> 无解。

=== 解法 ===

一次同余方程有很多解法。

对 <math>b = 1</math> 的情况，即 <math>ax \equiv 1\pmod n</math> ：要么互质，解是模逆；要么不互质，无解。有解时可由[[大衍求一术]]求解。

对更广泛的情况，可以使用形式分数法求解。即通过对 <math>\tfrac{a}{b}</math> 做：
* 上下同乘与模数互质的数
* 对分子或分母加减模数 <math>n</math> 的倍数
* 约分
直至其化为 <math>\tfrac{k}{1}</math> 的形式， <math>k</math> 即是解。


{{同余理论}}