数论6中国剩余定理.doc

第六讲 中国剩余定理 韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人······。刘邦茫然而不知其数。 我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？ 首先我们先求5、9、13、17之最小公倍数9945(注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积)，然后再加3，得9948(人)。 中国有一本数学古书 《孙子算经》 也有类似的问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？” 答曰：“二十三” 孙子算经的作者及确实著作年代均不可考，不过根据考证，著作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。 中国剩余定理(Chinese Remainder Theorem)在近代抽象数学中占有一席非常重要的地位。 我们在解决类似“物不知其数”题，也就是出现一个数N除以A余a，除以B余b，除以C余c这一类问题的时候，我们有四个方法把余数问题转化为“整除问题”： 一、减同余 例如：a=b. 则有A|N -a，且B|N一a，N-a=[A，B]n，而N的值是： N= [A，B]n+a； 二、加同补 例如 ：A-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】(难度星级★★★)有一个年级的同学，每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除所得的余数各不相同。