加载中…[转载]中国剩余定理“大衍求一术”手算方法及四个习题
(2019-12-27 12:42:00)
标签：
转载 |
分类： 余一好奇收藏馆 |
原文地址：中国剩余定理“大衍求一术”手算方法及四个习题作者：小牛
今天广东佛山下雪。有一些雪花还真有点像鹅毛。这是我退休后移居广东20年来，第一次看到的景像。
用现代数学表示，即：
X≡R1 (mod m1 )
X≡2 (mod 3
)
X≡R2 (mod m2)
→ X≡3
(mod 5 )
X≡R3 (mod m3)
X≡2 (mod 7 )
求物数X
计算步骤及名词注释如下：
1 余数R ： 例中 R1=2、R2=3、R3=2
2 模，亦即除数m ：例中 m1=3、m2=5、m3=7
3 模的最小公倍数G ：G =m1×m2×m3，例中 G
=3×5×7=105
4 衍数（局部公倍数）y
：Y1=m2m3、Y2=m1m3，Y3=m1m2，例中Y1=5×7＝35、Y2=3×7＝21、Y3=3×5＝15
5 计算乘率C
：这是解算中国剩余定理的关键。计算“乘率”的方法，我认为在《孙子算经》年代就已经知道了，只是书上没有详细说明而己。否则怎么会有“三三数之剩二，置一百四十
… 凡三三数之剩一，则置七十 …
”等语呢？因为140＝70×2，而2就是“乘率”。到了南宋，秦九韶才在《数书九章》一书中写出计算方法，称之为“大衍求一术”。
“求一”就是使 (衍数Y×乘率C) －模m×商N＝余数1。以同余式表示为 ：
衍数Y×乘率C≡1 (mod m)。
例中 35C1≡1 (mod 3 ) 、
21C2≡1 (mod 5 ) 、15C3≡1
(mod 7 )。
已知Y、m、1，求C。经计算得C1＝2、C2＝1 、C3＝1。求C的细节，见下面四个习题。
上述各项计算结果见下表：
同余式 i 衍数Y 乘率C 余数R 模m
检验 (Y C -
1)/ m = 整数N
6 最终：X≡Y1C 1 R1＋Y2C2 R2＋Y3C3 R3 (mod G) 。见下表
：
最近，倒在网页上看到一篇博文，介绍清代黄宗宪的《求一术通解》里求乘率的方法，大喜，以为可以见到真传了。看其运算过程，有“辗转相除”的影子，但怎样得到最终结果的，还是讲得不细、不具体，我还是看不懂。
好在现代数学著作中，有二个方法可以求“乘率C”。但是否就是原汁原味的“大衍求一术”法，
我则不知道。这二个方法是：
1、35C≡1 (mod 3)
设商为Y，就等价于：35C＝3Y＋1，或35C－3Y＝1
2、35C－3Y＝1
实际上是一个二元一次不定方程。下面是解算C：
3、C＝(3Y+1)∕35
凡分子中Y的系数(3)，小于分母(35)，就要改化这个等式，倒过来：
4、Y＝(35C－1)∕3
现在分子上C的系数 (35)，大于分母
(3)，可以了。
5、Y＝(35C－1)∕3＝11C＋(2C－1)∕3＝11C＋T1
〔其中(2C－1)∕3＝T1 ，要求T1是整数〕
6、T1＝(2C－1)∕3
分子上C的系数(2) 小于分母(3)，要倒过来。
7、C＝(3T1+1)∕2＝T1＋(T1＋1)∕2＝T1＋T2
〔其中 (T1＋1)∕2 ＝T2 ，要求T2是整数〕
8、T2＝(T1＋1)∕2
当分子中T1的系数为1时，才停止展开，得：
9、T1＝2T2－1
此时得整数了。下面是回代求C、Y。
T1代入7式的C：
10、C＝T1＋T2＝2T2－1 ＋T2＝3T2－1
代入5式的Y：
11、Y＝11C＋T1＝11(3T2－1)＋2T2－1＝35T2－12
最后：C＝ 3 T2－1
Y ＝35T2－12
当T2＝0时，C＝－1、Y＝－12
负数，不取
当T2＝1时，C＝ 2、Y＝ 23
取最小正整数。
检验： 35C＝3Y＋1 → 35×2＝3×23＋1 70＝69＋1
正确
最后得 C＝2
衍数35的乘率C＝2，就是这样来的。
35 C≡1 (mod 3 ) ，是一次同余式
(35与3互质)，它等价于二元一次不定方程：
35 C－3Y＝1 ，现在求C、Y的最小解。而C正是“大衍求一术”中的乘率。
第一步 辗转相除：辗转相除的起算数为35与3 。
被除数＝除数×商＋余数
35＝ 3×11 ＋2 …
（1）
3＝ 2× 1 ＋1 …
（2）
由35 经辗转相除，最终得余数1。以下便逆向回代。由1开始，反求被除数35的乘率C与商Y。
第二步 清理一下余数3、1的表达式：
余数＝被除数－除数×商
由（2）式得 1＝3－2
由（1）式得 2＝ 35－3×11
第三步 逆向回代，把各余数的表达式代入，使最后的等式中只保留被除数35、除数3，形式为：
1 ＝3－2
保留3，把余数2的表达式2＝(35－3×11 )代入：
＝3 － (35－3×11)＝ 35×(－1)＋3×12 →
35×(－1)－3×(－12)，等式中只有被除数35与除数3，没有余数，就完成逆算。
对比 35 C－3
Y＝1
与
35×(－1)－3×(－12)＝1
可见 C＝－1 ，Y＝－12，与“欧拉方法”的结果相同。
C＝－1为负数，不取，加最小公倍数3，得C＝2
衍数35的乘率C＝2，就是这样来的。
其他21C2≡1 (mod 5 )
的解C2＝1及15C3≡1 (mod 7 ) 的解C3＝1
，也是同样方法。
35C≡1 (mod 3 ) 、21C2≡1 (mod 5 ) 及15C3≡1 (mod 7
)为例，的确可以凑出C＝2、1、1，倒也不难。我以前也是这样想的。但靠凑，没有理据。碰到C很大，不知凑到何时。于是我才想到编程，其实编程方法也是凑，不过因为速度太快，也就使我乐于此道。但如果停留在此步，学识似乎不够。于是我又刻苦一下，终于基本上弄懂了手算的方法。
1、45C≡1 (mod 7 )
设商为Y，等价于：45C－7Y＝1
2、45C－7Y＝1
实际上是一个二元一次不定方程：得C：
3、C＝(7Y+1)∕45
凡分子中Y的系数
(7)，小于分母(45)，就要改化这个等式，倒过来：
4、Y＝(45C－1)∕7
现在分子上C的系数(45)，大于分母(7)，可以了。
5、Y＝(45C－1)∕7＝6C＋(3C－1)∕7＝6C＋T1 〔其中 (3C－1)∕7
＝T1 ，要求T1是整数〕
6、T1＝(3C－1)∕7
分子上C的系数3小于分母(7)，要倒过来
7、C＝(7T1+1)∕3＝2T1＋(T1＋1)∕3＝2T1＋T2 〔其中
(T1＋1)∕3 ＝T2 ，要求T2是整数〕
8、T2＝(T1＋1)∕3
当分子中T1的系数为1时，才停止展开，得
9、T1＝3T2－1
此时得整数。下面是回代求C、Y。
T1代入7式C：
C＝2T1＋T2 得C＝2(3T2－1)＋T2＝6T2－2＋T2＝7T2－2
代入5式Y，Y＝6C＋T1＝6(7T2－2)＋(3T2－1)＝42T2－12＋3T2－1＝45T2－13
最后：C＝ 7T2－2
Y＝45T2－13
当T2＝0时，C＝－2、Y＝－13 负数，不取
当T2＝1时，C＝ 5、Y＝32
取最小正整数。
检验： 45C＝7Y+1 → 45×5＝7×32+1 → 225＝224＋1
正确。最后得 C＝5 。
45C－7Y＝1 ，辗转相除的起算数为45与7 。
第一步 辗转相除：
被除数＝除数×商＋余数
45 ＝ 7 ×6＋ 3 …
（1）
7 ＝ 3 ×2＋ 1 …
（2）
由45 经辗转相除，最终得余数1。以下便逆向回代。由1开始，反求被除数45的乘率C与商Y。
第二步 清一下余数3、1的表达式：
余数＝被除数－除数×商
由（2）式得 1＝ 7 － 3 ×2
由（1）式得 3＝ 45 － 7 ×6
第三步 逆向回代，把各余数的表达式代入，使最后的等式中只保留被除数45、除数7形式为：
1 ＝7 －3×2
保留7，把余数3的表达式3＝(45－7×6) 代入：
＝7 － (45－7×6)×2＝7 －
45×2＋7×12＝45×(－2)＋7×(13)，等式中只有被除数45与除数7，没有余数了，就完成逆算。
对比 45 C－7
Y＝1
与 45×(－2)＋7×(13) ＝1 →
45×(－2)－7×(－13) ＝1 ，
所以 C＝－2
，Y＝－13，取最小正整数C＝7－2＝5，与“欧拉方法”的结果相同。可见“辗转相除的逆向追求法”也非常有效，步骤不多、计算简易、结果正确。陈景润在《初等数论Ⅰ》中的第59、61、81、82、83、125、133、134页多次用到这个方法。
1、25C≡1 (mod 18)
2、C＝(18Y＋1)∕25
3、Y＝(25C－1)∕18 ＝C＋(7C－1)∕18＝C＋T1
4、T1＝(7C－1)∕18
5、C＝(18T1+1∕7＝2T1＋(4T1+1)∕7＝2T1＋T2
6、T2＝(4T1+1)∕7
7、T1＝(7T2－1)∕4＝T2+(3T2－1)∕4＝T2+T3
8、T3＝(3T2－1)∕2
9、T2＝(4T3+1)∕3＝T3+(4T3+1)∕3＝ T3+(T3+1)∕3＝T3+T4
10、T4＝(T3+1)∕3
11、T3＝3T4+1
回代到9
T2＝T3+T4 ＝3T4-1+T4＝4T4-1
回代到7
T1＝T2+T3＝4T4-1＋3T4+1 ＝7T4-2
回代到5
C＝2T1＋T2＝2(7T4-2)＋4T4-1＝14T4-4+4T4-1=18T4－5
回代到3
Y＝C＋T1 ＝18T4－5 ＋7T4－2＝=25T4－7
最后：C＝18T4－5
Y ＝25T4－7
当T4＝1时，C＝13、Y＝18
最后：C＝13
25C≡1 (mod 18 )
25C－18Y ＝1
第一步 辗转相除：
被除数＝除数×商＋余数
25 =18×1＋7 … （1）
18 = 7×2＋4 …
（2）
7 = 4×1+3
… （3）
4 =3×1+1
… （4）
第二步 清一下余数 1、3、4、7的表达式：
余数＝被除数－除数×商
由（4）式得 1＝( 4 － 3 )
由（3）式得 3＝(7 － 4 )
由（2）式得 4＝(18 － 7 ×2
)
由（1）式得 7＝( 25 －18 )
第三步 逆向回代，
1＝4 － 3 ×1 ＝(18－7×2 )－(7－4 )＝18－7×3＋ (18－7×2 )
＝18×2－7×5＝18×2－( 25 －18)×5＝－25×5+18×7
＝25×(－5)－18×(－7)
与 25C－18Y ＝1 相对照，得 C＝－5、
取正值，C＝－5＋18＝13
即：为了解算YX≡R (mod m)
得到X，要先解算YC≡1 (mod
m)，再两边乘R，便得X=CR。
因此，要解71X≡58 (mod 105 )
求X，得先解71C≡1 (mod 105 )
，求C。
现仅用“欧拉方法” 来求C 。
1、71C≡1 (mod 105)
2、71C－105Y＝1
3、C＝(105Y＋1)∕71＝Y＋(34Y＋1)∕71＝Y＋T1
4、T1＝(34Y＋1)∕71
5、Y＝(71T1－1)∕34＝2T1＋(3T1－1)∕34＝2T1＋T2
6、T2＝(3T1－1)∕34
7、T1＝(34T2＋1)∕3＝11T2+(T2＋1)∕3＝11T2+T3
8、T3＝(T2＋1)∕3
9、T2＝3T3－1
回代到7
T1＝11T2+T3＝11(3T3－1) +T3＝33T3－11 +T3＝34
T3－11
回代到5
Y＝2T1＋T2＝2 (34 T3－11)＋3T3－1＝68 T3－22＋3T3－1＝71 T3－23
回代到3
C＝Y＋T1 ＝71 T3－23＋(34 T3－11) ＝105 T3－34
当T3＝1时，C＝71
再算 X
71C≡1 (mod 105)
两边乘上真正的余数58，得：
71×71×58≡1×58 (mod
105)
71×4118≡58 (mod 105)
对照 71X≡58 (mod 105 )
可见 X＝4118
验算 71×4118＝292378 、292378÷105＝2784 … 58
正确。但4118不是最小值，它超过除数105，所以要减去105的39倍才成为最小值。4118－39×105=23 → 得
X＝23
再验算 71×23＝1633 、1633÷105＝15 … 58正确
X通解为 X＝23＋105K ( K=0、1、2、3、… )
喜欢
0
赠金笔
前一篇：[转载]诗，读不懂怎么办？