下载掌阅APP，畅读海量书库
立即打开
求解线性同余方程 ax ≡ b （mod m ）。
同余方程的求解始终是初等数论的核心问题之一，最简单的情形当属下述线性同余方程或称为一次同余方程：
ax ≡ b （mod m ）。
下面讨论该方程何时有解以及解的个数问题。当然，把解局限在模 m 的剩余系中，亦即在模 m 所得的全部余数0，1，…， m -1中，谈论解的存在性、唯一性以及解的个数等问题。
先研究解的存在性问题。如果该方程有解 x ，则 ax - b 被 m 整除，亦即 ax - b 是 m 的一个倍数。此时存在整数 k 使得 ax - b = km ，变形为 b = ax - km 。这说明 b 可表示为 a 和 m 的一个整系数线性组合，从而 a 和 m 的最大公因子（ a ， m ）整除 b 。换句话说，得到了上述线性同余方程有解的必要条件。那么，该条件是否还是解存在的充分条件呢？事实上，使用欧几里得的辗转相除法去求两个整数的最大公因子时，能把两个数的最大公因子写成该两数的整系数线性组合。所以，存在整数 l ， k 满足
（ a ， m ）= al + mk 。
如果最大公因子（ a ， m ）整除 b ，令 b =（ a ， m ） n ，则有
b =（ a ， m ） n = a （ ln ）+ m （ kn ）。
于是 x ≡ ln （mod m ）即为同余方程 ax ≡ b （mod m ）的一个解。这就证明了一开始所讨论的线性同余方程 ax ≡ b （mod m ）有解的充分必要条件是 a 和 m 的最大公因子（ a ， m ）整除 b 。
接着，来研究该同余方程解的个数问题。为此先考虑 a 和 m 互素这一特殊情形，下面将证明此时的同余方程恰有一个解。事实上，根据上一段关于解的存在性讨论，当（ a ， m ）=1时方程 ax ≡ b （mod m ）有解，设 x = r 为其一个解。假如 x = s 也是其任意一个解，则两个同余式相减后即为
a （ r - s ）= ar - as ≡ b - b ≡0（mod m ）。
假定 a 和 m 互素，故从 m 整除 a （ r - s ）可推出 m 整除 r - s 。因为把解限制在模 m 的余数中，故有 r = s ，表明该同余方程有唯一的解。
一般地，将证明当（ a ， m ）整除 b 时，线性同余方程 ax ≡ b （mod m ）恰好有（ a ， m ）个解。为此，先作一些简化。令
d =（ a ， m ）， a = da' ， m = dm' ， b = db' 。
显然 a' 和 m' 互素，而且在 ax ≡ b （mod m ）中消去公因子 d 可得下述简化同余方程
a'x ≡ b' （mod m' ）。
根据上段关于解唯一性的讨论可知该简化同余方程恰有一个解，设为 r 。只需验证下述构造的 d =（ a ， m ）个数
r ， r + m' ， r +2 m' ，…， r +（ d -1） m'
即为原同余方程全部不同的解。
首先，从0≤ r < m' 可知对每个0≤ k ≤ d -1均有
0≤ r + km' ≤ r +（ d -1） m' < m' +（ d -1） m' = dm' = m 。
其次，这些数不仅两两不同，而且都是简化同余方程的解，自然也满足原同余方程。剩下的只是要证明原同余方程的每个解必然出现在这些数中。设 s 为 ax ≡ b （mod m ）的任意一个解，则 s 也是简化同余方程 a'x ≡ b' （mod m' ）的一个解。根据简化同余方程解唯一的性质，有 s ≡ r （mod m' ），故可令 s = r + km' 。注意到0≤ s < m = dm' ，这将迫使0≤ k < d ，表明 s 也出现在上述构造的 d 个数中。所以，这 d 个数确为同余方程全部不同的解。
综上所述，关于线性同余方程 ax ≡ b （mod m ）解的存在性和个数问题，总结如下：当 a 和 m 的最大公因子（ a ， m ）不整除 b 时该方程无解；当（ a ， m ）整除 b 时该方程恰有（ a ， m ）个解。另外，所有的解可从简化同余方程的唯一解构造出来。