Dayan Seeking One Technique Form

Answer 1

大衍求一术算法每一步的结果是两行三列的数表，其上下两行分别满足一定条件。算法的初始状态设定为：如果满足一定条件则达到要求。设互素的正整数为 \(m\) 和 \(n\)（\(m\gt n\)），前两步算法按 \(m\) 和 \(n\) 分情形说明如下：

情形一：
1. 设 \(m\) 除以 \(n\) 的带余数除法的结果为：\(m = nq_{1}+r_{1}\)（\(0\lt r_{1}\lt n\)）。用所得的商 \(q_{1}\) 分别去乘初始数表中对应于 \(n\) 的两数并把结果加到对应于 \(m\) 的两数上，再把 \(m\) 更新为余数 \(r_{1}\) 得到第1步的结果：
\[
\begin{array}{ccc}
r_{1}&a_{1}&b_{1}\\
n&c_{1}&d_{1}
\end{array}
\]
其中数表的第一行满足 \(r_{1}=a_{1}m + b_{1}n\)。
2. 如果 \(r_{1}=1\) 则算法结束。设 \(r_{1}\neq1\) 且 \(n\) 除以 \(r_{1}\) 的带余数除法的结果为：\(n=r_{1}q_{2}+r_{2}\)（\(0\lt r_{2}\lt r_{1}\)）。用所得的商 \(q_{2}\) 分别去乘对应于 \(r_{1}\) 的两数并把结果加到对应于 \(n\) 的两数上，再把 \(n\) 更新为余数 \(r_{2}\) 得到第2步的结果：
\[
\begin{array}{ccc}
r_{2}&a_{2}&b_{2}\\
r_{1}&c_{2}&d_{2}
\end{array}
\]
其中数表的第二行满足 \(r_{2}=a_{2}m + b_{2}n\)。

情形二：
1. 设 \(n\) 除以 \(m\) 的带余数除法的结果为：\(n = mq_{1}+r_{1}\)（\(0\lt r_{1}\lt m\)）。用所得的商 \(q_{1}\) 分别去乘初始数表中对应于 \(m\) 的两数并把结果加到对应于 \(n\) 的两数上，再把 \(n\) 更新为余数 \(r_{1}\) 得到第1步的结果：
\[
\begin{array}{ccc}
r_{1}&a_{1}&b_{1}\\
m&c_{1}&d_{1}
\end{array}
\]
其中数表的第二行满足 \(r_{1}=a_{1}m + b_{1}n\)。
2. 设 \(m\) 除以 \(r_{1}\) 的带余数除法的结果为：\(m=r_{1}q_{2}+r_{2}\)（\(0\lt r_{2}\lt r_{1}\)）。用所得的商 \(q_{2}\) 分别去乘对应于 \(r_{1}\) 的两数并把结果加到对应于 \(m\) 的两数上，再把 \(m\) 更新为余数 \(r_{2}\) 得到第2步的结果：
\[
\begin{array}{ccc}
r_{2}&a_{2}&b_{2}\\
r_{1}&c_{2}&d_{2}
\end{array}
\]
其中数表的第一行满足 \(r_{2}=a_{2}m + b_{2}n\)。

一般地，“大衍求一术”算法每一步的结果，或者形如
\[
\begin{array}{ccc}
r_{i}&a_{i}&b_{i}\\
r_{i - 1}&c_{i}&d_{i}
\end{array}
\]
分别代表等式 \(r_{i}=a_{i}m + b_{i}n\);或者形如
\[
\begin{array}{ccc}
r_{i}&a_{i}&b_{i}\\
r_{i + 1}&c_{i}&d_{i}
\end{array}
\]
分别代表等式 \(r_{i}=a_{i}m + b_{i}n\)。这个过程一直进行下去，终止于数表的上行右列的数满足一定条件（终止的条件是：数表的上行右列的数满足特定要求）。特别地，如果辗转相除的过程终止于下行的 \(r_{k}\)（此时 \(r_{k - 1}=r_{k}q_{k+ 1}\)）需要人为地增加一步“除法”，强制要求余数等于1即：\(r_{k}=1\)。