跳至內容

線性同餘方程

維基百科,自由的百科全書

數論中,線性同餘方程是最基本的同餘方程,「線性」表示方程的未知數次數是一次,即形如:

的方程。此方程有解若且唯若能夠被最大公約數整除(記作)。這時,如果是方程的一個解,那麼所有的解可以表示為:

其中最大公約數。在模完全剩餘系中,恰有個解。

例子

  • 在方程

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

  • 在方程

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

  • 在方程

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

求特殊解

對於線性同餘方程

      (1)

整除 ,那麼為整數。由裴蜀定理,存在整數對(可用擴展歐幾里得算法求得)使得,因此 是方程 (1) 的一個解。其他的解都關於同餘。

舉例來說,方程

。注意到 ,因此 是一個解。對模 28 來說,所有的解就是

與線性丟番圖方程的關係

考慮,其等價於是整數),也就是線性丟番圖方程。運用輾轉相除法可以求得該方程的解,有無限多個;但是在原同餘方程中,解的個數受到限制,因此正如上面例子所示,只能選取前面的幾個解。

線性同餘方程組

線性同餘方程組的求解可以分解為求若干個線性同餘方程。比如,對於線性同餘方程組:

首先求解第一個方程,得到,於是令,第二個方程就變為:

解得。於是,再令,第三個方程就可以化為:

解出:,即 。代入原來的表達式就有 ,即解為:

對於一般情況下是否有解,以及解得情況,則需用到數論中的中國剩餘定理

參見