线性同余方程组

线性同余方程组是线性方程组在数论同余下的推广。

矩阵同余

设$m \in \Z^+, A = (a_{ij}), B = (b_{ij}) \in \Z^{l \times n}_m$，称矩阵$A$与$B$模$m$同余，如果$a_{ij} \equiv b_{ij} \pmod{m}$，记作$A \equiv B \pmod{m}.$

于是，上文一元二次同余方程组的解就可表示为

$$\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \equiv |A|^{-1} A^* \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \pmod{m}$$

其中，$A^*$为$A$的伴随矩阵。

线性同余方程组

定理：设$A = (a_{ij}) \in \Z_m^{n \times n}$，且$(|A|, m) = 1$，$A^*$为$A$的伴随矩阵，于是

$$|A|^{-1} \cdot A^* \cdot A \equiv E \pmod{m}.$$

进而，若已知$B = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix} \in \Z_m^{n}$，则关于$X = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \in \Z_m^{n}$的线性同余方程组

$$AX \equiv B \pmod{m}.$$

有唯一解

$$X \equiv |A|^{-1} \cdot A^* \cdot B \pmod{m}.$$