初等数论基础：一次同余方程求解

本节讨论一次同余方程的解法.对这类同余方程，人们已完全掌握了它的求解方法.

定理5.2.1　一次同余方程ax≡b（modm），a≢0（modm）有解当且仅当（a，m）|b，此时该同余方程有（a，m）个解，这些解为

其中（x0，y0）是不定方程ax+my=b的某个解.

证明　　（1）ax≡b（modm）有解⇔存在x0∈Z使得ax0≡b（modm）⇔存在x0∈Z使得m|ax0-b⇔存在x0，y0∈Z使得ax0+my0=b⇔ax+my=b有解⇔（a，m）|b.

（2）先证（5.2.1）是ax≡b（modm）的（a，m）个不同的解.注意到

有这表明诸满足同余方程ax≡b（modm）.设

则从而（a，m）|t1-t2.但|t1-t2|＜（a，m），故t1=t2.这表明（5.2.1）是ax≡b（modm）的（a，m）个不同的解.

设x≡u（modm）是ax≡b（modm）的任一解.则存在v∈Z使得（u，v）是ax+my=b的一解.据定理3.1.3知存在t0∈Z使得记

t0=q（a，m）+r，0≤r＜（a，m）.

则这表明故x≡u（modm）就是（5.2.1）中的（a，m）个解之一.证毕.

例5.2.2　求同余方程124x≡100（mod36）的一切整数解.

解　由（124，36）=4|100知同余方程有4个解.不定方程124x+36y=100同解于31x+9y=25.根据第三章的方法可求得124x+36y=100的一解（4，-11）.故原同余方程的解为x≡4+9t（mod36），t=0，1，2，3.解毕.

据定理5.2.1，有以下结论.(www.xing528.com)

推论5.2.3　若x0∈Z且ax0≡b（modm），则一次同余方程ax≡b（modm）的解为

利用推论5.2.3及同余的若干性质也可以来解一次同余方程.请看下面的例子.

例5.2.4　求同余方程124x≡100（mod36）的一切整数解.

解　由（124，36）=4|100知同余方程有4个解.另一方面，对任意整数x，有

这表明4满足同余方程124x≡100（mod36）.据推论5.2.3知

是原同余方程的所有解.解毕.

定理5.2.1指出了二元一次不定方程和一次同余方程的密切关系，并将一次同余方程的求解问题归结为二元一次不定方程的求解问题.事实上，也可以用一次同余方程的理论来解二元一次不定方程.请看下面的例子.

例5.2.5　解不定方程258x+162y=-24.

解　由（258，162）=6|-24知方程有解，也就是同余方程258x≡-24（mod162）有解.先求满足同余方程258x≡-24（mod162）的一个整数x0.事实上，对任意x，有

这表明x0=20满足同余方程258x≡-24（mod162）.将x0带入258x+162y=-24得该方程的一个解（20，-32）.据定理3.1.3，

就是原方程的一切整数解.解毕.