[特别关注]中国剩余定理及求模的逆元的公式

ysr

这个论坛很难登录！说两句吧。
强烈要求召开科学大会，在万众瞩目的火炬之中，如何欲盖弥彰的魔鬼将无所遁形，昭然若揭。发展科学，是必须的，于国于家是有利的，等抗击疫情胜利了，就可以召开科学大会，专题会议，能培养科学氛围，改变社会气氛。
    否则科学真理可能将石沉大海终为土灰，没有科学世界是啥样？可以想象必是群魔乱舞，科学是魔鬼的对头，科学不应许魔鬼有横行的权利！

ysr

ysr 发表于 2019-12-15 12:30
求乘法的逆元的程序代码，利用陆元鸿教授的矩阵变换法做的，计算小于10位的两个数的逆元，n模p的逆元。

...

再重发一下，这个程序很重要，不仅可以用来解一次方程和中国剩余定理，还可以用来破解RSA密码。
求乘法的逆元的程序代码，利用陆元鸿教授的矩阵变换法做的，计算小于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。由于代码太长，需要可调用程序如大数的乘法除法加法减法等，不发了，下面给出主程序。

ysr

中国剩余定理和求乘法的逆元


普及个知识:中国剩余定理在小学课本中有，大学也讲，所以老少皆宜。古代中国研究已很精辟，并广泛应用。历代皇帝重视历法，历法中大量用到这种计算，古代中国历法精确就得益于此。农历是阴阳合历，既照顾太阳又照顾月亮，较复杂，我不懂历法，不知具体如何算。在现代科技中也会用到，如公钥密码体制中的公钥和私钥的计算。
法:若某数除以ABC余分别为r1，r2，r3，求此数？
      求除A余r1要在BC的倍数中求，先求乘以BC使余数(/A)为1的乘率m，(或直接得出余r1的乘率)，则m乘r1与BC的积满足/A余r1。
依次类推得到分别满足BC的解，再加起来就得到答案，除以最小公倍数得到的余数就是最小的解，最小解是唯一的。
   当数据很大不便于从1试到m，求m的方法古人叫“大衍求一术”，其实就是现代的求模的逆元，若ed/P余1则e与d互为逆元。查书，用到辗转相除法，好象没有公式，只讲到方法:辗转相除(用余数再去除除数)到余1再逆推回去。（注意一点：若求e模p的逆元，则e与p必须互质，不是互质数没有逆元。即使求出来个结果也是不对的。比如15/3没有逆元，无论何值乘以15都能被3整除，而21/15也没有逆元，即使按下面的方法算出来结果了，也是错误的。因为我们知道互质数辗转相除最后余数为1，而不互质的，辗转相除最后余数是最大公约数。）
公式比较复杂，最后结果需要分3种情况输出，不方便不推导了。
   下面图片是陆元鸿教授给出的矩阵解法：（教授给出的例子分别是一类，我补充了一个就是7/4的逆元为3的例子，是又一类，加上这个就完整了。）
图片附于后面。（这种方法求逆元，我已经编程，有需要的请与我联系）
    下面举个例子，就是用此方法来求逆元进而解决中国剩余定理的问题：
题：
今有物不知其数，三、三数之余2，五、五数之余1，七、七数之余4，13、13数之余10，55、55数之余21，56、56数之余39，问物几何？

解：
21/5余数1，
39/7余数4，
与前面不矛盾，所以，有解，
3*5*7*13*11*8=120120，（这就是最小公倍数）
120120/3=40040，
120120/5=24024，
120120/7=17160，
120120/13=9240，
120120/55=2184，
120120/56=2145，
40040模3 的逆元为：2，则满足3，3数余2的为：2*40040*2=160160，
24024模5 的逆元为：4，则满足5，5数余1的为：4*24024*1=96096，
17160模7 的逆元为：5，则满足7，7数余4的为：5*17160*4=343200，
9240模13 的逆元为：4，则满足13，13数余10的为：4*9240*10=369600，
2184模55 的逆元为：24，则满足55，55数余21的为：24*2184*10=524160，（因为96096/55=1747余11，加10就会余数为21），
2145模56 的逆元为：33，则满足56，56数余39的为：33*2145*7=495495，（因为343200/56=6128余32，加7就会余数为39），
495495/56=8848余7，所以，正确，
160160+96096+343200+369600+524160+495495=1988711，
1988711/3=662903余2，
1988711/5=397742余1，
1988711/7=284101余4，
1988711/13=152977余10，
1988711/55=36158余21，
1988711/56=35512余39，所以，都符合实际，正确！
1988711/120120=16余66791，所以，最小解为66791.（这类问题有无穷解，最小的一个是唯一的）
求乘法逆元的程序代码：
求乘法的逆元的程序代码，利用陆元鸿教授的矩阵变换法做的，计算小于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.
其它依次类推，2184/55=余39，要至少试验23次，得到24*39/55=余数1，
2145/56余数17，至少32次得到33*17/56余数1.
手工计算是费劲，需要技巧，注意具体问题与普遍公式的区别，特殊的差异，题目多拐个弯就容易出错，注意！
比如：96096/55=1747余11，不是余数为0，后面的一项必须要加上11才能为21，且加数必须为5的倍数（或其他的前面的模，一般都对不必太在意）。
另一位网友的解法：
记住一条即可，任意数做被乘数，从0递增到P-1倍，加任意一个数，在这p个数中一定有一个数被P整除。等差数列如下：m+（i-1）T，1≤i≤P,则此数列中一定有一个值被P整除。m为事先给的值，T为周期值（或者跨度数，步长），P为给定的值，且与m互质（这个方法就是穷举法，递推法，数据小的时候行，看上去还简单，数据大的时候就无法用，还是前面的方法具有普遍性）。

这种方法很有用，实际生活中工作中总会遇到此类问题，比如解一次不定方程的时候就用到，和求中国剩余定理的问题一样。应该普及，欢迎指导，欢迎探讨！

ysr

例求答案 ？
一筐鸡蛋：
1个1个拿，正好拿完。
2个2个拿，还剩1个。
3个3个拿，正好拿完。
4个4个拿，还剩1个。
5个5个拿，还差1个。
6个6个拿，还剩3个。
7个7个拿，正好拿完。
8个8个拿，还剩1个。
9个9个拿，正好拿完。

问筐里最少有多少鸡蛋？

能算出这道题的智商不一般！求答案 ？有高手没，算算吧！
解：（注意：5个5个呐余数差1，就是余数为4，而不是余数为1）
63模8 的逆元为：7，7*63=441，441/5余数为1，不行，7+8=15显然不行能被5整除了，7+2*8=23，63*23=1449.经验证符合题意，最小 答案是1449.

ysr

这类问题，最早见于《孙子算经》(作者不详年代不确定)，其中把解法概括为几句“顺口溜”，其实只解决了除数为3，5，7的情况。而到了宋朝的秦九韶才给出了系统的解法，叫“大衍求一术”，到1852年才由英国传教士把秦九韶的“大衍求一术”带到欧洲，外国数学家发现该法与高斯和欧拉弄出来的一次同余方程组的解法是一致的，但秦九韶的方法比高斯和欧拉早了500年，从而无可辩驳的确认此法为“中国剩余定理”。
“大衍求一术”和前面的矩阵变换法相似，原理相同，可以说是同一种方法。
秦九韶的方盘内，最多4个数，初始状态只有3个数的，右上角置被除数叫“奇”(相等于n)，右下角置除数叫“居”(相当于p)，左上角置“天元”为1(相等于初值a=1)，左下角初始状态没有数(相当于初值b=0)，通过辗转相除，居和奇及天元不断变化，左下角的数也不断变化，直到右边出现余数为1的情况结束，则天元位置的数据即为所求“乘率”(就是逆元)。
和矩阵变换一样，只不过是行变换而不是列变换，还少了c和d两个多余的变量(其实最后d=p，c为p模n的逆元)。
秦九韶的方法是古文记载的，要翻译成现在的话，还要变为数学语言，而方盘的运算和程序或沙盘一样，中间数据不断变化，只保留最后结果，中间过程和数据不保留，不容易明白，上面的矩阵变换容易理解，二者原理一样，所以，不再重复叙述了，学会了矩阵变换就等于掌握了“大衍求一术”。

“大衍求一术”居然也不用逆推的，可见古人对此类问题研究相当精辟！

ysr

没法，发表个学术成果很难，出书也难啊！(我准备再出版一次了)