数论6中国剩余定理

《数论6中国剩余定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六讲中国剩余定理韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人······。刘邦茫然而不知其数。我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？首先我们先求5、9、13、17之最小公倍数9945(注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积)，然后再加3，得9948(人)。中国有一本数学古书《孙子算经》也有类似的问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何

2、？”答曰：“二十三”孙子算经的作者及确实著作年代均不可考，不过根据考证，著作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理(ChineseRemainderTheorem)在近代抽象数学中占有一席非常重要的地位。我们在解决类似“物不知其数”题，也就是出现一个数N除以A余a，除以B余b，除以C余c这一类问题的时候，我们有四个方法把余数问题转化为“整除问题”：一、减同余例如：a=b.则有A

3、N-a，且B

4、N一a，N-a=[A，B]n，而N的值是：N=[A，B]n+a；二、加同补例如：A-

5、a=B-b=d，则有N+d=[A，B]n，而N的值是：N=[A，B]n-d。三、逐级满足法四、中国剩余定理【例1】(难度星级★★★)数n大于10，且除以5余3，除以6余2，除以7余1，求适合条件的最小的自然数。【巩固】(难度星级★★★)一个三位数除以3余2，除以5余1，除以7余4，这个三位数最小是多少？【铺垫】(难度星级★★)满足被6除余1，被7除余2，被8除余3的最小自然数是多少？【例22(难度星级★★★)一个数除以4余1，除以5余4，除以7余3，求适合条件的最小的自然数。【例3】(难度星级★★★)今有物不知数，五五数之余三，七七数之余一，九九数之余四，问物几何？【例4

6、】(难度星级★★★)有一个年级的同学，每9人一排多6人，每7人一排多2人，每5人一排多3人，问这个年级至少有多少人？【巩固】(难度星级★★)一个数除以3余2，除以5余3，除以7余4，问满足条件的最小自然数。趣味数学明朝数学家程大位把这一解法编成四句歌诀：三人同行七十(70)稀，五树梅花廿一(21)枝，七子团圆正月半(15)，除百零五(105)使得知。同余性质应用【例5】(难度星级★★★★)求乘积418×8l4×l6l6除以13所得的余数。【例6】(难度星级★★★)求除以7的余数。【例7】(难度星级★★★★)设2n+1是质数，证明：被2n+1除所得的余数各不相同。