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

中国剩余定理 2015 08 22 1 整数除法 被除数 除数 商 余数 余数 除数 A B C R 被除数 余数 除数 商 A R B C 2 例1 一个两位数 用它除58余2 除73余3 除85余1 求这个两位数 用它除58余2 意外着这个两位数是56 58 2 的因数 同样的也是70和84的因数 所以这个两位数是56 70 84的公因数 答案是14 3 例2 有一盒乒乓球 每次8个8个地数 10个10个地数 12个12个地数 最后总是剩下3个 这盒乒乓球至少有多少个 因为每次都多出3个 所以拿走3个乒乓球 那么不论是8个8个地数 10个10个地数 12个12个地数 都没有剩余 这时乒乓球的个数就应该是8 10和12的公倍数 8 10 12 120 120 3 123所以这盒乒乓球至少有123个 4 例3 把几十个苹果平均分成若干份 每份4个余2个 每份10个余8个 每份25个余23个 这堆苹果共有几个 题目的意思相当于 这个数除以4缺2 除以10缺2 除以25也缺2 因此加上2后 除以4 除以10和除以25时 就都正好能整除了 也就是4 10和25的公倍数 4 10 25 100 100一2 98 所以这堆苹果的数量是98 5 例4 有一个数 除以8余数是3 除以11余数是2 这个数最小是多少 由于这个数除以8和11的余数不相同 而且缺少的数也不相同 因此不能直接利用最小公倍数来解决我们先看 除以11余2 这个条件 从小到大依次在所有满足 除以11余2 的数中寻找 除以8余3 的数 2 11 13 13 8 1 5 不符合 13 11 24 24 8 3 也不符合 24 11 35 35 8 4 3 符合条件 因此这个数最小是35 6 例5 一堆糖果 4个一数多1个 9个一数多4个 11个一数多9个 这堆糖果至少有多少个 这个问题可以概括为 一个数 除以4余1 除以9余4 除以11余9 我们可以从满足 除以11余9 的数中 找出 除以9余4 的数 这只要依次加上11即可 然后再找出 除以4余1 的数 这需要依次加上9和11的最小公倍数99即可 9 11 2020 9 2 2 不符合 除以9余4 的条件 20 11 3131 9 3 4 符合 除以9余4 的条件 但31 4 7 3 不符合 除以4余1 的条件 31 99 130 130 4 32 2 也不符合 除以4余1 的条件 130 99 229 229 4 57 1符合 除以4余1 的条件 因此这堆糖果至少有229个 7 韩信点兵 的故事 韩信阅兵时 让一队士兵5人一行排队从他面前走过 他记下最后一行士兵的人数 1人 再让这队士兵6人一行排队从他面前走过 他记下最后一行士兵的人数 5人 再让这队士兵7人一行排队从他面前走过 他记下最后一行士兵的人数 4人 再让这队士兵11人一行排队从他面前走过 他记下最后一行士兵的人数 10人 然后韩信就凭这些数 可以求得这队士兵的总人数 2111 4421 8 孙子算经 中的题目我国古代数学名著 孙子算经 中有 物不知数 的题目 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 还有专门用来解决同一个数除以3 5和7的问题的歌诀 三人同行七十稀 五树梅花廿一枝 七子团圆正半月 除百零五便得知 实际上70是能被5和7整除但被3除余1 21能被3和7整除但5除余1 15能被3和5整除但被7除余1 这个系统算法是南宋时期的数学家秦九韶研究后得到的 这就是著名的中国剩余定理 9 例6 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 题目中此数被3除余2 那就用70乘以2 被5除余3 歌诀 三人同行七十稀 五树梅花廿一枝 七子团圆正半月 除百零五便得知 那么就用21乘3 被7除余2 那就15乘2 相加 70 2 21 3 15 2 233 看情况减3 5 7的最小公倍数的倍数 此题减105的2倍 得到23 10 例7 一个数 除以5余1 除以7余2 除以9余4 这个数最小是多少 这道题目同样可以用例5的方法进行计算 但是现在我们准备采用类似于例6的方法 例6的方法之所以方便 是因为歌诀中给出了70 21和15这三个数 那么这道题目中又该是多少呢 歌诀中的70正好是能被5和7整除 而被3除余1的最小数 21正好是能被3和7整除 而被5除余1的最小数 15正好是能被3和5整除 而被7除余1的最小数 利用这个思路 我们来解答例7 因为 7 9 63 63 5 12 3 而63x2 126 126 5 25 1 所以能被7和9整除 而被5除余1的最小数是126 11 例7 续 一个数 除以5余1 除以7余2 除以9余4 这个数最小是多少 能被7和9整除 而被5除余1的最小数是126 同样的方法 我们可以找出能被5和9整除 而被7除余1的最小数是225 能被5和7整除 而被9除余1的最小数是280 1 126 2x225 4 280 696 这个数显然太大 接下来就要减去5