首页 > 编程知识 正文

孙子问题的解法 剩余定理,孙氏定理 数学

时间:2023-05-03 12:17:41 阅读:261717 作者:3191

中国剩余定理 乘法逆元 乘法逆元的定义

乘法逆元的计算


这里采用的方式是穷举法,一遍一遍试出满足条件的最小x值,通常采用编程方式去找出x。

中国剩余定理(孙子定理)的定义及解法






上面定理的证明需要一个同余换模的定理作支撑,以下是定理的定义及证明:

实际推算过程中,不一定按照上述定理的推算过程,可以以局限式的推出结果:
1.一个班学生分组做游戏,如果每组三人就多1人,每组五人就多2人,每组七人就多3人,问这个班有多少学生?
解:设这个班有x个学生,则x除以3余1;x除以5余2;x除以7余3。
(1)首先求出x除以5余2;x除以7余3最小正整数:
把除以7余3的数从小到大排列:3,10,17,24,31,……
以上各数除以5的余数分别为: 3,0 ,2 ,4 ,1 ,……
所以满足条件的是17,因此x除以35余17
(2)求出x除以35余17;x除以3余1最小正整数:
把除以35余17的数从小到大排列:17,52,87,……
以上各数除以3的余数分别为: 2, 1 ,0 ,……
所以满足条件的是52。

这里x除以35余17只是以17作为一个最小的满足(1)条件的最小整数来推算最后的最小满足(1)和(2)的结果。

按照上述定理的严格推算可以为以下解答过程:
求正整数解x满足:
x= 1mod3
= 2mod5
= 3mod7
首先利用秦九韶发明的“大衍求一术”求出5和7的最小公倍数35的倍数中除以3余数为1的最小一个数70 (这个数35相对于3的数论倒数),3和7的最小公倍数21相对于5的数论倒数21,3和5的最小公倍数15相对于7的数论倒数15。然后计算
70x1+21x2+15x3= 157
157便是可能的解之一。它加减3、5、7的最小公倍数105的若干倍仍然是解,因此最小的解为157除以105的余数52。以上解法若推广到一般情况,便得到了中国剩余定理(孙子定理)

这里参考一篇关于中国剩余定理在实际问题的应用解答过程
中国剩余定理【数论】
中国剩余定理(孙子定理)

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。