小学奥数-中国剩余定理ppt课件

在一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数。

这样的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中的解同余式。

① 有一个数，除以3余2，除以4余1，问这个数除以12余几？解：除以3余2的数有：2， 5， 8， 11，14， 17， 20，23…它们除以12的余数是：2，5，8，11，2，5，8，11…除以4余1的数有：1， 5， 9， 13， 17， 21， 25，29…它们除以12的余数是：1， 5， 9， 1， 5， 9，….一个数除以12的余数是唯一的.上面两行余数中，只有5是共同的，因此这个数除以12的余数是5。

如果我们把①的问题改变一下，不求被12除的余数，而是求这个数.很明显，满足条件的数是很多的，它是5+12×整数，整数可以取0，1，2，…，无穷无尽.事实上，我们首先找出5后，注意到12是3与4的最小公倍数，再加上12的整数倍，就都是满足条件的数.这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件.《孙子算经》提出的问题有三个条件，我们可以先把两个条件合并成一个.然后再与第三个条件合并，就可找到答案.②一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数。

解：先列出除以3余2的数：2， 5， 8， 11， 14， 17， 20， 23，26…再列出除以5余3的数：3， 8， 13， 18， 23，28…这两列数中，首先出现的公共数是8.3与5的最小公倍数是15.两个条件合并成一个就是8+15×整数，列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23，30…就得出符合题目条件的最小数是23.事实上，我们已把题目中三个条件合并成一个：被105除余23.那么韩信点的兵在1000-1500之间，可能是105×10+23=1073人问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”答曰：“二十三”术曰：三三数剩一置几何？答曰：五乘七乘二得之七十。

中国剩余定理暑假集训的时候就应该来写这篇博客的，当时听的有些糊涂，不过该来的还是得来。

中国剩余定理介绍在《孙⼦算经》中有这样⼀个问题：“今有物不知其数，三三数之剩⼆（除以3余2），五五数之剩三（除以5余3），七七数之剩⼆（除以7余2），问物⼏何？”这个问题称为“孙⼦问题”，该问题的⼀般解法国际上称为“中国剩余定理”。

在《孙⼦歌诀》中给出了解决这个问题的解法：三⼈同⾏七⼗稀，五树梅花廿⼀⽀，七⼦团圆正半⽉，除百零五便得知。

很是朗朗上⼝，但这是什么意思呢？具体解法分三步：找出三个数：1.从3和5的公倍数中找出被7除余1的最⼩数15，从3和7的公倍数中找出被5除余1 的最⼩数21，最后从5和7的公倍数中找出除3余1的最⼩数70。

2.⽤15乘以2（2为最终结果除以7的余数），⽤21乘以3（3为最终结果除以5的余数），同理，⽤70乘以2（2为最终结果除以3的余数），然后把三个乘积相加（15*2+21*3+70*2）得到和233。

3.⽤233除以3，5，7三个数的最⼩公倍数105，得到余数23，即233%105=23。

这个余数23就是符合条件的最⼩数。

就这么简单。

我们在感叹神奇的同时不禁想知道古⼈是如何想到这个⽅法的，有什么基本的数学依据吗？中国剩余定理分析我们将“孙⼦问题”拆分成⼏个简单的⼩问题，从零开始，试图揣测古⼈是如何推导出这个解法的。

⾸先，我们假设n1是满⾜除以3余2的⼀个数，⽐如2，5，8等等，也就是满⾜3*k+2（k>=0）的⼀个任意数。

同样，我们假设n2是满⾜除以5余3的⼀个数，n3是满⾜除以7余2的⼀个数。

有了前⾯的假设，我们先从n1这个⾓度出发，已知n1满⾜除以3余2，能不能使得 n1+n2 的和仍然满⾜除以3余2？进⽽使得n1+n2+n3的和仍然满⾜除以3余2？这就牵涉到⼀个最基本数学定理，如果有a%b=c,则有(a+kb)%b=c(k为⾮零整数)，换句话说，如果⼀个除法运算的余数为c，那么被除数与k倍的除数相加（或相减）的和（差）再与除数相除，余数不变。

在一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数。

这样的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中的解同余式。

①有一个数，除以3余2，除以4余1，问这个数除以12余几？ 解：除以3余2的数有：2， 5， 8， 11，14， 17， 20， 23… 它们除以12的余数是：2，5，8，11，2，5，8，11… 除以4余1的数有：1， 5， 9， 13， 17， 21， 25， 29… 它们除以12的余数是：1， 5， 9， 1， 5， 9，…. 一个数除以12的余数是唯一的.上面两行余数中，只有5是共同的，因此这个数除以12的余数是5。

如果我们把①的问题改变一下，不求被12除的余数，而是求这个数.很明显，满足条件的数是很多的，它是5+12×整数，整数可以取0，1，2，…，无穷无尽.事实上，我们首先找出5后，注意到12是3与4的最小公倍数，再加上12的整数倍，就都是满足条件的数.这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件.《孙子算经》提出的问题有三个条件，我们可以先把两个条件合并成一个.然后再与第三个条件合并，就可找到答案. ②一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数。

解：先列出除以3余2的数：2， 5， 8， 11， 14， 17， 20，23， 26… 再列出除以5余3的数：3， 8， 13， 18， 23， 28… 这两列数中，首先出现的公共数是8.3与5的最小公倍数是15.两个条件合并成一个就是8+15×整数，列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23， 30… 就得出符合题目条件的最小数是23. 事实上，我们已把题目中三个条件合并成一个：被105除余23.那么韩信点的兵在1000-1500之间，可能是105×10+23=1073人问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”答曰：“二十三”术曰：三三数剩一置几何？答曰：五乘七乘二得之七十。

中国剩余定理又名「孙子定理」或称「鬼谷算」、「隔墙算」、「剪管术」、「秦王暗点兵」或「韩信点兵」，但当今数学界则称之为「中国剩余定理」（Chinese Remainder Theorem）。

「今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？」（摘自《孙子算经》卷下，第26题），意思是：现在一个未知数，除3时，余数是2；除5时，余数是3；除7时，余数是2，问这个未知数的最小值？中国著名数学家华罗庚教授，对这道题目有以下的说法：「求一个数，3除余2，5除余3，7除余2。

这个问题太容易回答了，因为3除余2，5除余3，7除余2，则21除余2。

而23是3、7余2最小的数，刚好又是5除余3的数。

所以心算快的人都算出！」（摘自《华罗庚科普著作选集》第84页）正如华罗庚教授所说，重点并不是计算出23这个结果，数学便是不仅于此。

数学的研究便是希望找到这道题的特质，作出普遍化的解法。

你又可知道这道名题的普遍解吗？很多中国的名事迹或名题，在民间都有歌谣，有的唱出一个故事，有的唱出这些名题的解法。

而这「鬼谷算」也不例外，而且还有几个不同版本，以下是其中之一：三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知。

摘自《算法统宗》卷四这些解的意思是说，用70乘3除所得的余数，用21乘5除所得的余数，用15乘7除所得的余数，然后再加起来。

如果其和大于105，则减去105，直至小于105为止，最后这个数便是答案。

以「鬼谷算」中的余数为例： 2×70+3×21+2×15－105－105 =23那么，（一）如何推出这个结果？（二）如果除数改变了，或有更多的余数时又如何？简而言之，可以把这个方法推广吗？讨论中国剩余定理，同余（congruence）的概念是必须的理论基础。

给定一个正整数n，我们说两个数a、b是对模n同余，如果a－b是n的倍数。

用符号a≡b(mod n)来代表。

中国剩余定理<本⼈⽐较喜欢做总结，所以许多的知识都是从⽹上找到的并且重新组织利⽤，主要⽬的是为了加深我个⼈的理解和总结，欢迎⼤家指出错误，⼀起讨论，⼀起进步>“有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？”这就是中国剩余定理的来源了，什么意思呢？就是说数⼀堆物品,如果三个三个数的话，就会剩下⼆个，如果五个五个数的话，就会剩下三个，如果是七七数的话，就会剩下⼆个，那么到底有多少个呢？（来源wiki）我想从特殊到⼀般来讨论这个问题；题⽬其实可以抽象来数学问题如下:现在我们想想，如何才能找到这么⼀个数x呢？⾸先我们定义a[1 2 3] = 2, 3, 2;m[1 2 3] = 3, 5, 7; 我们思考下，如果存在这么⼀个x的话，那么它有什么性质呢？⾸先它要满⾜被mi取模时其对应的值为ai,好那么我们从编程中的循环来思考，是否存在那么⼀个Ti使得对于Ti % mi = ai,同时Ti % mj(j != i) = 0 如果存在的话，那么我们x 就可以等于 T1 + T2 + T3 (因为可以把模分别分配到Ti上，有两个值为0)有的话，⼜要怎么构造？好，起码我们现在有⼀思路了。

那么Ti怎么构建，⾸先⼀定有⼀个 ai % mi = ai,那么我们可以找⼀个Ti/ai ，它满⾜Ti/ai % mi = 1,同时由Ti % mj(j != i) = 0、 Ti/ai % mi = 1、Ti % mi = ai可以得到这个Ti/ai 这个项有⼀个性质 Ti/ai % mj = 0;好了现在关于Ti/ai这个项已经有了⼀定的性质：Ti/ai % mj =0, Ti/ai % mi = 1,故通过构造令Ti/ai是mj的倍数，同时，它会是在mi下两个互为倒数的乘积，所以⽤取Mi 为mi的累乘，但排除第i项⽬，同时令ti = Mi 模 mi 的数论倒数，也即满⾜ti * Mi = 1 (mod mi), Ti/ai = ti * Mi;(这⾥要补充下说明，什么是模mi的数论倒数，也就是说当Mi确定的时候，可以通过 ti * Mi % mi == 1这个判断的数字，这个可以循环来求，循环的最⼤次数是mi,因为ti < mi，打到⼀个最⼩的ti就可以了)那到现在确定了Ti = ai * ti * Mi,同时对于（S)我们有⼀个ti * Mi % mi = 1 ,也就是说所以就可以确定T1、 T2、T3，也就可以求出X了。