[科普中国]-一次同余方程

简介

一次同余方程亦称线性同余方程，是一类简单的同余方程，指未知数仅出现一次幂的同余方程。

最简单的一次同余方为 (mod n)，此处整数 (mod n)及 b 为给定整数，求解 x。这相当于求解一次不定方程（indefinite equation）或一次丢番图方程（Diophantine equation） ，其中，a，b，n为已知整数，求整数解x，y。这一方程有解的充要条件为(a，n)|b。当 时，同余方程有唯一的解 。当 时，只有当d|b时有解，这时命 为 唯一的解， 。则原方程共有 d 个关于模 n 互不同余的解： 。

一般的一次同余方程 有解 的充要条件为 。若此条件成立，则共有 组互不同余的解，mod n。

关于一次不定方程，中国古代早有研究，如张丘建的“百鸡问”等。1

解法关于一次同余方程的解法和性质有下述定理：

1.设(a, m) = 1，m>0，则同余式ax≡b(mod m)恰有一个解；

2.设(a, m) = d，m>0，则同余式ax≡b(mod m)有解的充分必要条件是d|b，此时恰有d个解。

根据以上两个定理，同余方程ax≡b (mod m)在a≢0且(a,m)|b的条件下，必有(a,m)个关于模m互不同余的解。又根据最大公约数的性质，必有二整数x、y，能使ax+my=(a,m)。由于(a,m)|b，所以有 ， ，使 ，由此即可得到原方程的(a,m)个关于模m互不同余的解为。