解一元同余方程初等数论

前面介绍了同余的概念、性质和应用，介绍了有关剩余类和剩余系的知识，以及费马小定理和欧拉定理.本节在此基础上介绍一元一次同余方程的概念和解法.

定义1 设a，b为整数常数，m为大于1的正整数，x为未知整数，若a≢0（modm)，则称ax≡b（modm)为一元一次同余方程，简称同余方程.

定义2 若存在整数c，使得ac≡b（modm)成立，则称x≡c（modm)为同余方程ax≡b（modm)的一个解；求同余方程解的过程，叫作解同余方程.

由同余方程解的定义可见，同余方程的解不是一个数，而是满足同余方程的一类数，即模m的一个剩余类c＋km（k为整数).

下面讨论同余方程有无解的判断和有解时的求法.

先介绍无解的判断定理.

定理1 设（a，m)=d，若d|/b，则方程ax≡b（modm)无解.

证明 设有整数c满足ax≡b（modm)，即ac≡b（modm)，则m|（ac-b).

又设ac-b=mn（n∊Z)，则b=ac-mn.

∵d|a，d|m，∴d|b，这与已知矛盾.

故不存在这样的整数c满足ax≡b（modm)，即同余方程无解.

例1 判定下列同余方程哪个无解：

（1)4x≡1（mod15)； （2)4x≡1（mod10)；

（3)6x-3≡0（mod10)； （4)ax＋b≡0（modm).

解 （1)因为（4，15)=1|1，故可能有解（后面可知有解).

上例解（1)中，结论是可能有解，究竟是有还是无解？如果有，有多少？如何求？这是我们自然应当进一步研究的问题.为此，我们有如下定理.

定理2 若（a，m)=1，则ax≡b（modm)有唯一解.

证明 （1)存在性（证明是构造性的，即给出了求解方法).

方法1 ∵（a，m)=1，由第一章欧拉算法可知，存在整数s，t，使as＋mt=1，∴asb＋mtb=b，a（sb)≡b（modm)，故x≡sb（modm)是解.

方法2 ∵（a，m)=1，由欧拉定理可知，aφ（m)≡1（modm)，

∴baφ（m)≡b（modm).

∴a（baφ（m)-1)≡b（modm)，∴x≡baφ（m)-1（modm).

（2)唯一性（反证).

设同余方程有两个解：

x≡r（modm)，x≡q（modm).

∵ar≡b（modm)，aq≡b（modm)，

∴ar≡aq（modm).

∵（a，m)=1，∴r≡q（modm).

这与假设矛盾，故有唯一解.

例2 解4x≡1（mod15).

解 因为（4，15)=1，故有唯一解.

方法1 由欧拉算法可得4×4-15=1，故唯一解为x≡4（mod15).

方法2 ∵φ（15)=8，∴x≡47（mod15).

两个结果形式不同，实为一个：47≡4（mod15).

方法3 4x≡1≡1＋15≡16（mod15).∵（4，15)=1，∴x≡4（mod15).

可见，方法3是直接通过加模的整数倍，再约系数得解，比前两个方法要便于操作，直接求解.这种方法可称之为同解变形法.

例3 解14x≡27（mod31).

解 因为（14，31)=1，故有唯一解.

14x≡27≡27＋31≡58（mod31).

∵（14，58)=2，（2，31)=1，∴7x≡29（mod31).

7x≡29≡29＋2×31≡91（mod31).

∴x≡13（mod31).

下面介绍多解的判断及求法.

定理3 若（a，m)=d|b，则同余方程ax≡b（modm)有d个解.

分析 当d=1时就是定理2；需要证明存在d个解，找到即可；还要证明除了找到的d个之外，无其他解，可反证.

证明 （1)存在性.

由已知可设a=dα，m=dβ，（α，β)=1，b=dλ，代入原方程，得αx≡λ（modβ).

∵（α，β)=1，∴αx≡λ（modβ)有唯一解.

设解为x≡r（modβ)（r=0，1，…，β-1)，则αr≡λ（modβ).从而dαr≡dλ（mod dβ)，ar≡b（modm)，(www.xing528.com)

∴x≡r（modm)是ax≡b（modm)的一个解.

下面证明x≡r＋kβ（modm)（k=0，1，2，…，d-1)都是ax≡b（modm)的解.

∵ax≡a（r＋kβ)=ar＋akβ=ar＋dαkβ=ar＋αkm≡ar（modm)，ar≡b（modm)，

∴a（r＋kβ)≡b（modm).

∴x≡r＋kβ（modm)（k=0，1，2，…，d-1)都是ax≡b（modm)的解.

下面用反证法证明x≡r＋kβ（modm)（k=0，1，2，…，d-1)是ax≡b（modm)的d个不同解.

设其中两个

是同余方程的一个解，则r＋k1β≡r＋k2β（modm)，从而k1β≡k2β（modm).

∵m=dβ，∴k1β≡k2β（moddβ)，∴k1≡k2（modd)，∴d|（k1-k2).

∵0≤k1，k2≤d-1，∴k1=k2.与k1≠k2矛盾.

故x≡r＋kβ（modm)（k=0，1，2，…，d-1)是ax≡b（modm)的d个不同的解.

（2)唯一性.

设原同余方程除了上述d个解之外，还有一个解x≡s（modm)，而上述d个解中的一个是x≡r（modm)，则as≡b（modm)，ar≡b（modm)，故as≡ar（modm).

∵（a，m)=1，∴s≡r（modm).∵m=dβ，∴s≡r（modβ).

∴s=r＋kβ（k∊Z).

由于x≡s（modm)是d个解之外的一个，故k＜0或k≥d.

设k=dq＋l（l=0，1，2，…，d-1)，则

故s≡r＋βl（modm).

而由（1)末知，这是同余方程的（1)中提到的d个解中的一个，这与假设它是那d个解之外的一个矛盾.

故那d个解之外不存在解.

例4 解同余方程6x≡15（mod33).

解 因为（6，33)=3|15，所以有3个解.由原同余方程可得2x≡5（mod11).因为（2，11)=1，所以2x≡5（mod11)有唯一解.

2x≡5≡5＋11=16（mod11)，所以x≡8（mod11)是2x≡5（mod11)的唯一解.

故原同余方程的3个解为：

是同余方程ax≡b（modm)的（a，m)=d个解.

例5 解同余方程111x≡75（mod321).

解 因为（111，321)=3|75，所以有3个解.

因为321=3×107，所以由原同余方程可得111x≡75（mod107)，从而

即4x≡75（mod107)，故4x≡75-107=-32（mod107)，x≡-8（mod107).

故原同余方程的3个解为：

例6 解同余方程1296x≡1125（mod1935).

解 （1296，1935)=9|1125，故有9个解.

由原同余方程得144x≡125（mod215)，则144x≡125-215=-90（mod215).即8x≡-5（mod215)，故8x≡-5-215=-220（mod215)，故2x≡-55（mod215)，进而2x≡-55＋215=160（mod215)，故x≡80（mod215).

故原同余方程的9个解为：x≡80＋215k（mod1935)（k=0，1，…，8).

习题2.5

1.判断下列同余方程有无解、有几个解：

（1)3x≡3（mod3)； （2)3x≡1（mod10)；

（3)5x≡1（mod10)；（4)7x≡9（mod8)；

（5)660x≡595（mod1385).

2.解下列同余方程：

（1)5x≡1（mod6)；（2)3x≡8（mod4)；

（3)2x≡1（mod17)；（4)9x≡4（mod2401)；

（5)243x≡112（mod551)；（6)256x≡179（mod337).

3.解下列同余方程：

（1)4x≡6（mod18)；（2)3x≡6（mod18)；

（3)8x≡44（mod72)；（4)1215x≡560（mod2755)；

（5)660x≡595（mod1385).