线性同余方程

维基百科,自由的百科全书

数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次,即形如:

的方程。此方程有解当且仅当能够被最大公约数整除(记作)。这时,如果是方程的一个解,那么所有的解可以表示为:

其中最大公约数。在模完全剩余系中,恰有个解。

例子

  • 在方程

中, ,3 不整除 2,因此方程无解。

  • 在方程

中, ,1 整除 2,因此方程在中恰有一个解:

  • 在方程

中, ,2 整除 2,因此方程在中恰有两个解:以及

求特殊解

对于线性同余方程

      (1)

整除 ,那么为整数。由裴蜀定理,存在整数对(可用扩展欧几里得算法求得)使得,因此 是方程 (1) 的一个解。其他的解都关于同余。

举例来说,方程

。注意到 ,因此 是一个解。对模 28 来说,所有的解就是

与线性丢番图方程的关系

考虑,其等价于是整数),也就是线性丢番图方程。运用辗转相除法可以求得该方程的解,有无限多个;但是在原同余方程中,解的个数受到限制,因此正如上面例子所示,只能选取前面的几个解。

线性同余方程组

线性同余方程组的求解可以分解为求若干个线性同余方程。比如,对于线性同余方程组:

首先求解第一个方程,得到,于是令,第二个方程就变为:

解得。于是,再令,第三个方程就可以化为:

解出:,即 。代入原来的表达式就有 ,即解为:

对于一般情况下是否有解,以及解得情况,则需用到数论中的中国剩余定理

参见