如何求解一次同余式

什么是一次同余式？

形如 的式子叫一次同余式,求解一次同余式即求 满足一次同余式

一次同余式的解

同余式的解和我们所说的一般方程的解的概念不同。比如一元二次方程 ，它的解集是 。但是对于同余式我们有

证明

由于 ，可设 ，我们有

所以，解同余式事实上是求所有的 ，在模 的完全剩余系中，使得同余式成立的剩余个数为解的个数

一次同余式的解分为：无解、唯一解、多解三种情况

无解

当 则 一次同余式无解，其中 。

证明

显然， 由于 ，则 。由于 则 ，这与 相矛盾，所以一次同余式无解。

唯一解

当 时一次同余式有且仅有一个解。

证明

由广义欧几里得除法，当 时，存在唯一的 使得 ，将等式两边同乘 ，即 ,此时 是一次同余式的唯一解。

多解

如果 ，则一次同余式有 个解

证明

设 ，考虑方程

该方程满足唯一解的情况，设该方程的唯一解为 ，考虑 个解

1. 这 个解都满足 ,由于
   
   其中 因为 ，所以 ，即 ，同时 ,所以
   
2. k不能取其他的值,使其只有 个解，由于 在模 的意义下， 互不相同，同时当 时开始重复

一次同余式的解法

根据以上的证明过程，我们能得到这样的思考路径

1. 计算 ,如果 ，一次同余式无解。如果 ，同余式有唯一解。如果 ，同余式有 个解。
2. 如果 ，使用广义欧几里得除法计算
3. 如果 ，先计算 的特解 ，解为