求一术与方程术


林开亮

1.jpg

刘徽在《九章算术注》中提出了对矩阵同时做行列变换求解方程组的方法.

在本栏目第1期中国剩余定理,我们向大家介绍了著名的中国剩余定理,并引发了读者的热烈反响,感谢大家对本栏目的鼓励支持,以及对具体内容的建议和评论。今天我们想给大家介绍一下求一术及其推广方程术。前者在中国剩余定理的介绍中已经出现,我们先简单回顾一下。

前文中国剩余定理所叙述的中国剩余定理,其关键思想有两个:一是通过(线性方程组的)叠加原理将一个一般的同余方程组分解为多个特殊的同余方程组;而是将特殊的同余方程组(通过换元)转化为一次同余方程的求解,而后者可以用求一术来求解。

按照古人的叙述(注,下述表述与 中国剩余定理中的表述略有不同,但实质一样,且更与历史相符),求一术可以表述如下:

求解方程

$$    \newcommand{\M}{\mathrm{mod\,\,}}    \newcommand{\Z}{\mathbb{Z}}    $$    $$ax\equiv 1(\M b)\quad(a,b\in\Z^+)\tag{♣}\label{♣}$$

的整数解的求一术:

首先写出矩阵

$$A=\begin{bmatrix} a&b\\ 1&0\\ \end{bmatrix}$$

然后对第一行两个元素辗转相除,并将对应的操作应用于第二行(用矩阵的语言说,相当于对A做初等列变换),直至第一行的两个元素都变成不能更小的正整数,此时:若此两个数中有一个数是1,则它下方的那个数是(♣)的一个特解;否则,(♣)无整数解。此外,若已得到(♣)的一个特解,比方说,$x=u$那么,(♣)的通解为

$$x=u+bk,\quad k\in\Z.\tag{♠}$$

我们举个例子。

用求一术解丢番图方程:

$$35x\equiv 1 (\M 3)\tag{1}$$

解:

$$\left[ \begin{array} { c c } { 35 } & { 3 } \\ { 1 } & { 0 } \end{array} \right] \xrightarrow[ c _ { 1 } - 11 c _ { 2 } ]{ 35 = 11 \cdot 3 + 2 \;} \left[ \begin{array} { c c } { 2 } & { 3 } \\ { 1 } & { 0 } \end{array} \right] \xrightarrow[c _ { 2 } - 1 c _ { 1 }] { 3 = 1 \cdot 2 + 1 \;} \left[ \begin{array} { c c } { 2 } & { 1 } \\ { 1 } & { - 1 } \end{array} \right]$$

所以$x=-1+3k,\,k\in\Z$是(1)的通解。

注:$c_1,c_2$分别表示矩阵的第$1$列与第$2$列$c$是column(列,也有专栏的意思)的首字母。

求一术可以推广成下述求解丢番图方程的方程术。

定理:[求解丢番图方程$ax + by= c$(其中$a,b$为正整数)的方程术]设

$$A = \left[ \begin{array} { l l } { a } & { b } \\ { 1 } & { 0 } \\ { 0 } & { 1 } \end{array} \right]\xrightarrow[列变换]{a,b\,辗转相除\;}\left[ \begin{array} { c c } { d } & { 0 } \\ { x _ { 0 } } & { s _ { 0 } } \\ { y _ { 0 } } & { t _ { 0 } } \end{array} \right]或\left[ \begin{array} { c c } { 0 } & { d } \\ { s _ { 0 } } & { x _ { 0 } } \\ { t _ { 0 } } & { y _ { 0 } } \end{array} \right]$$

则有以下结论 (i) $d = \gcd(a,b)$是$a$和$b$的最大公因子; (ii) $ax+ by= c$ 有整数解 $\Leftrightarrow d|c$, 且此时其通解为 $$\left[ \begin{array} { l } { x } \\ { y } \end{array} \right] = \frac { c } { d } \left[ \begin{array} { l } { x _ { 0 } } \\ { y _ { 0 } } \end{array} \right] + k \left[ \begin{array} { l } { s _ { 0 } } \\ { t _ { 0 } } \end{array} \right],$$ 其中$k$为任意的整数。

作为例子,我们来求解“猴子分桃”问题中的丢番图方程,参见张景中院士:五猴分桃问题

例: 求解丢番图方程 $$1024x —3125y = 8404\tag{2}$$解:为利用方程术,我们将(2)的未知数视为$x$与$- y$, 这样它们的系数就都是正整数了.

$\left[ \begin{array} { c c } { 1024 } & { 3125 } \\ { 1 } & { 0 } \\ { 0 } & { 1 } \end{array} \right]$ $\xrightarrow[第2列减去第1列的3倍\;]{3125=3\cdot 1024 +53}$ $ \left[ \begin{array} { c c } { 1024 } & { 53 } \\ { 1 } & { - 3 } \\ { 0 } & { 1 } \end{array} \right]$

$\xrightarrow[第1列减去第2列的19倍]{1024=19\cdot 53 +17} $ $\left[ \begin{array} { c c } { 17 } & { 53 } \\ { 58 } & { - 3 } \\ { - 19 } & { 1 } \end{array} \right]$

$\xrightarrow[第2列减去第1列的3倍]{53=3\cdot 17 +2} $ $\left[ \begin{array} { c c } { 17 } & { 2 } \\ { 58 } & { - 177 } \\ { - 19 } & { 58 } \end{array} \right]$

$\xrightarrow[第1列减去第2列的8倍]{17=8\cdot 2 +1}$ $\left[ \begin{array} { c c } { 1 } & { 2 } \\ { 1474 } & { - 177 } \\ { - 483 } & { 58 } \end{array} \right]$

$\xrightarrow[第2列减去第1列的2倍]{2=2\cdot 1}$ $\left[ \begin{array} { c c } { 1 } & { 0 } \\ { 1474 } & { - 3125 } \\ { - 483 } & { 1024 } \end{array} \right]$

所以,我们得到(2)的通解为 $$\left\{ \begin{array} { l } { x = 8404 \cdot 1474 - 3125 k } \\ { - y = 8404 \cdot ( - 483 ) + 1024 k } \end{array} \right.$$ 化简得 $$ \begin{cases} x &= 12387496 - 3125 k \\ y &= 4059132 - 1024 k \end{cases} \quad k\;为任意整数\tag{3} $$ 利用带余除法,不难得到 $$ \begin{cases} 12387496 & = 3963 \times 3125 + 3121 \\ 4059132 & = 3963 \times 1024 + 1020 \end{cases} $$ 因此(2)的最小正整数解为(在(3) 中令$k = 3963$): $$ \begin{cases} x & = 3121 \\ y & = 1020 \end{cases} $$

注:我们不打算证明方程术,它本质上就是解线性方程组的矩阵变换方法,这一方法最早记录在《九章算术》中,其中第八章就叫“方程”。有兴趣的读者,可以参见从射雕到九章——在天大理学院物理系的通俗报告

作者: 林开亮,西北农林科技大学理学院讲师