什么是“大衍求一术”？

luyuanhong

什么是“大衍求一术”？

作者 | 张影

来源 |《数学元年》

“大衍求一术”是中国古代数学的一项杰出成就，给出了求二元一次方程整数特解的有效方法。

本文介绍“大衍求一术”的算法与数学原理，适合中学生课外阅读。

（一）为什么需要“大衍求一术”？



（二）“大衍求一术”要意



（三）“大衍求一术”的算法与解释



（四）“大衍求一术”举例

本节通过例子，演示“大衍求一术”算法的过程。



(五)“大衍求一术”原文

秦九韶《数书九章》第一卷的“大衍求一术”原文是：

大衍求一术云：置奇右上，定居右下。与天元一于左上。先以右上除右下，所得商数，与左上一相生，入左下。然后乃以右行上下，以少除多，递互除之，所得商数随即递互累乘，归左行上下。须使右上末后奇一而止。乃验左上所得，以为乘率。



需要注意，“除”的意思是“去除”，不是“除以”。

我国现行的中小学数学教科书，把“除以”简化为“除”，大谬。

了解“大衍求一术”原文的详细解读，可以参考：

沈康身《中国数学史大系·第五卷 两宋》第四章



关于“大衍求一术”原理的证明，可以参考：

万哲先《孙子定理和大衍求一术》高等教育出版社，1989.5



（六）结束语

“大衍求一术”为解一次同余式方程组提供了关键工具，从而在中国古代历法关于“上元积年”的计算中起着重要作用。

不过，明朝中叶以后，“大衍求一术”几乎失传，直到十九世纪才被考证重现，并稍加改进。

从现代数学的角度来看，“大衍求一术”可以帮助理解著名的矩阵群 SL(2,Z) 的结构。

“大衍求一术”，汇古通今。它从历史中走来，引领我们踏进美丽的数学花园。

ysr

大衍求一术的最后输出应该是分类输出的，大致分三种:
此图就是大衍求一术的过程，是秦九韶弄出来的，与矩阵变换求乘法的逆元的原理是本质上一样的，比外国早了500年。

这个原理我没有推导，应该正确，我验证了一下，也是需要分类输出的，比如7/4，结果是上排为2，1，下排为5，1，实际答案是5-2=3，3*7/4=5……1，还要注意的是当某数除以1的情况，也就是下排先变成1的时候，商为某数减1而不是某数除以1仍然得某数，比如3/1则商为2余数为1.
还有一种情况就是比如23/61，最后结果是，上排为3，1，下排为5，7，实际答案是3+5=8，8*23=184，184/61=3……1。
如何分类，还不清楚，有待研究。
看上去简单，过程不明显，不容易理解，原理可以参考矩阵变换法求乘法的逆元。

比如：61/23得到，上排38，1，下排5，1，实际答案是38+5=43，（43>23,由于43 MOD 23=20，所以20是对的是最小的解）验证：43*61-1=2623-1=2622，而2622/23=114，成立。（而（20*61-1）/23=1219/23=53）

ysr

陆老师发的求乘法的逆元的矩阵变换法就很好，确定清楚，可以供大家学习！（我已经根据陆老师的原理做成了程序，各种情况都能解决）

回复您的点评：代码在论坛在我的文章里，陆教授的矩阵变换法也在我的文章里，陆教授也有一篇专门的文章介绍此法！

mathmatical

收藏，学习！

ysr

ysr 发表于 2022-10-31 06:17
陆老师发的求乘法的逆元的矩阵变换法就很好，确定清楚，可以供大家学习！（我已经根据陆老师的原理做成了程 ...

我的文章不好找的话，我复制一下代码：

求乘法逆元的程序代码：
求乘法的逆元的程序代码，利用陆元鸿教授的矩阵变换法做的，计算小于10位的两个数的逆元，n模p的逆元。Private Sub Command1_Click()
Dim n, p, a, b, c, d, r
  n = Trim(Text1.Text)
  p = Trim(Text2.Text)
  a = 1
  b = 0
  c = 0
  d = 1
  
  If Val(n) > Val(p) Then
     m = n
     q = p
     s1 = 1
  Else
     m = p
     q = n
     s1 = 0
  End If
Do Until Val(m) Mod Val(q) = 0
    s = m \ q
     r = m Mod q
     s1 = s1 + 1
     If s1 Mod 2 = 1 Then
     a = a
     b = a * s + b
     c = c
     d = c * s + d
     Else
     b = b
     a = a + b * s
     d = d
     c = c + d * s
     End If
     m = q
     q = r
  Loop
  If Val(a + b * m) = p Then
  b = b
  a = a + b * (m - 1)
  d = d
  c = c + d * (m - 1)
  Else
  If Val(b + a * m) = p Then
  a = a
  b = b + a * m
  c = c
  d = d + c * m
  Else
  b = b
  a = a + b * (m - 1)
  d = d
  c = c + d * (m - 1)
  End If
  End If

  
  Text3 = n & "模" & p & " 的逆元为：" & a
  

End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
Text3 = ""
End Sub
大数的乘法逆元的程序也出来了，如：67模147573952589676412927 的逆元为：145371356282367809749。由于代码太长，需要可调用程序如大数的乘法除法加法减法等，不发了。
分3种情况，注意7/4的逆元为3，输出结果为：当b+a*m=p=1+1*3=4，则a=a=3（程序前面已经递推得到a=3）。
（解释一下程序代码的步骤，例如求7模4的逆元为几?实际为3，因为3*7/4余数为1.步骤：n=7，p=4，当n>p时，m=n，q=p，当n小于p时，m=p，q=n，第二步开始，m=q，q=r，然后始终是求m/q的商s，和余数r，直到r=1或者r=0（因为任何整数除以1余数都是0）结束。
初始值a=1，b=0，c=0，d=1。
当步骤序号为奇数时，a=a，b=b+s*a，当步骤序号为偶数时，b=b，a=a+s*b。
最后分以下3种情况输出结果：
当a+b*m=p时，a=a+b*（m-1），当b+a*m=p时，a=a，其它情况则a=a+b*（m-1）.
例如7/4的逆元就是b+a*m=p的情况，输出a=a=3（程序前面递推到这一步已经得到a=3）。（n不等于p，n=p没有逆元，这种情况不存在））
求40040模3 的逆元的手工计算：（我是用程序算出来的，其实就是古人说的求余数为1的乘率）
40040/3的余数为2，2*2/3余数为1，所以，逆元为2.

ysr

20模27 的逆元为：23，
27模20 的逆元为：3，
96模67 的逆元为：37，
67模96 的逆元为：43，
23模61 的逆元为：8，
61模23 的逆元为：20，
27模64 的逆元为：19，
这都是程序计算的结果。

（论坛的时间比实际时间晚8个小时？应该是论坛的时间+8=实际时间）

ysr

2022模1027 的逆元为：353，
1027模2022 的逆元为：1327，
9253模225600 的逆元为：172717，
225600模9253 的逆元为：2169，

复制黏贴前面的程序就可以计算的。

ysr

2022*353-1027*695=1，
9253*172717-225600*7084=1.

有程序好算，比手工方便一点。

ysr

社会的发展与进步，从来就不是单靠喊口号就能实现的，你连基本的科学工具都不会使用，在这扯犊子呢？国家靠你这样的人能发展？老老实实的学习本领吧，幸好国家民族是靠千千万万个像我这样的知识分子发展。  Nicolas2050发表于 2023-1-1 07:47

你是哪根葱？