二元一次同余方程组

像二元一次方程组那样，我们也给同余式中引入二元一次同余方程组，它是线性同余方程组的特例。

概念

设$m_1, m_2 \geqslant 1$，$a_{11}, a_{12}, a_{21}, a_{22}, b_1, b_2 \in \Z$为常数，我们把下面的关于$x_1, x_2 \in \Z$的方程组就称为二元一次同余方程组。

$$\begin{cases} a_{11} x_1 + a_{12} x_2 \equiv 0 \pmod{m_1} \\ a_{21} x_1 + a_{22} x_2 \equiv 0 \pmod{m_2} \end{cases}$$

我们这里仅讨论最简单的一种情形：$m = m_1 = m_2.$

它可以写成

$$\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \equiv \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \pmod{m}$$

可令$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$，称作同余方程组的系数矩阵。

为了讨论方便，我们仅研究特殊的情形：$(|A|, m) = 1$。

解上述方程组

定理：$(|A|, m) = 1$时，二元一次同余方程组

$$\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \equiv \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \pmod{m}$$

在模$m$的意义下有唯一解，它是

$$\begin{cases} x_1 \equiv |A|^{-1} (a_{22} b_1 - a_{12} b_2) \\ x_2 \equiv |A|^{-1} (a_{11} b_2 - a_{21} b_1) \end{cases} \pmod{m}$$

其中，$|A|^{-1} |A| \equiv 1 \pmod{m}.$

这和普通的线性方程组有很多相似之处，仅需注意的是找$|A|$的逆元$|A|^{-1}$时是在模$m$的完系中找。

例如，二元同余方程组$\begin{cases} 3 x_1 + 4 x_2 \equiv 5 \pmod{13} \\ 2 x_1 + 5 x_2 \equiv 7 \pmod{13} \end{cases}$的$|A| = \begin{vmatrix} 3 & 4 \\ 2 & 5 \end{vmatrix} \equiv 7 \pmod{13}.$
进而满足$7 \cdot |A|^{-1} \equiv 1 \pmod{13}$的$|A|^{-1} \equiv 2 \pmod{13}.$
所以$\begin{cases} x_1 \equiv 2 \times (25 - 28) \equiv -6 \pmod{13}; \\ x_2 \equiv 2 \times (21 - 10) \equiv -4 \pmod{13}. \end{cases} \pmod{m}$

上下节

• 上一节：中国剩余定理
• 下一节：数论函数