剩余定理
一、剩余问题
    在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。
 
二、两个定理
    定理1：几个数相加，如果只有一个加数，不能被数a整除，而其他加数均能被数a整除，那么它们的和，就不能被数a整除。
    如：10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。
    定理2：两数不能整除，若被除数扩大（或缩小）了几倍，而除数不变，则其余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。
    如：22÷7＝3……1
    （22×4）÷7＝12……1×4（＝4）
    （要余2即 22×2÷7＝6……2）
    （22×9）÷7＝28……1×9-7（＝2）
    （想余5则22×5÷7＝15……5）
三、读解《中国剩余定理》
    中国数学史书上记载：
在两千多年前的我国古代算书《孙子算经》中，有这样一个问题及其解法：
    今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？
    答曰：23
    术曰：“三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之，得二百三十三，以二百一十减之即得。”
    “术”即解法。书中还介绍了上述问题中余数为一的一般解法：凡三三数之剩一，则置七十；
五五数之剩一，则置二十一；七七数之剩一则置十五；一百六以上，以一百零五减之即得。
    在明朝程大位著《算术统宗》一书中，把上述问题的基本解法，用诗句概括为：
    三人同行七十稀，五树梅花廿一枝，
    七子团圆正半月，除百令五便得知。
    解法1：依定理译成算式解为：
    70×2＋21×3＋15×2＝233
    233－105×2＝23
    这就是享誉中外的《中国剩余定理》。对此古代剩余问题，时至今日另有解法。
    解法2：用各除数的“基础数”法解。
    基础数的条件：
    （1）此数必须符合除数自身的余数条件；
    （2）此数必须是其他所有各除数的公倍数。
    （一）求各除数的最小公倍数
        ［3，5，7］＝105
    （二）求各除数的基础数
    （1）［3］ 105÷3＝35
        ［35］÷3＝11……2
    （2）［5］ 105 ÷ 5＝21
        21÷5＝4……1（当余3）
        ∵1×3＝3  21×3＝［63］
    （3）［7] 105 ÷ 7＝15
        15 ÷ 7＝2……1（当余2）
        ∵1×2＝2
        ∴15×2＝［30］
    （三）求各基础数的和
    35+63+30＝128
    （四）求基准数（最小的，只有一个）
    128-105=23
    （五）求适合条件的数X
    X＝23+105K（K是整数）
    （注：此法易行，且具有一般性）
    解法3：用枚举筛选法解
    按除数3，7同余2，依次逐一枚举；随后用除以5余3，进行筛选，便可获解。
    摘录条件
              3......2
    （基准数） ÷5……3    同余 2
              7......2
    （一）求3和7的最小公倍数
        ［3，7] ＝21
    （二）进行枚举筛选
    （1）21＋2=23  23÷5＝4……3
    一般地有：X=基准数+各除数的最小公倍数×K（K是整数）
    四、剩余问题的解法与应用
    例：韩信点兵，有兵一队，若列成五行纵队，则末行一人；若列成六行纵队，则末行五人；若列成七行纵队，则末行四人；若列成十一行纵队，则末行十人，求兵数至少有多少人？
    用基础数法解：
                  5......l
    基准数（2111）÷6……5
                  7......4
                  11......10
    （一）求各除数的最小公倍数
        ［5， 6， 7， 11]＝2310
    （二）求各除数的基础数
    （l）［5] 2310÷5＝462
      462÷5＝92……2
      ∵2×3－5＝1
      ∴462×3＝［1386］
    （2）［6] 2310÷6＝385
        385÷6＝64……1
        ∵ 1×5＝5
        ∴385×5＝［1925］
    （3）［7］ 2310÷7＝330
      330÷7＝47……1
      ∵1×4＝4
      ∴330×4＝［1320］
    （4）［11] 2310÷11＝210
        210÷11＝19……1
      ∵1×10＝10
      ∴210×10＝［2100］
    （三）求各基础数的和
    1386＋1925＋1320＋2100＝6731
    （四）求最小的基准数
    6731－2310×2＝2111（人）
    （五）求最适合条件的数X
    X=2111＋2310K（K为整数）
    答：这队兵至少有2111人。
    注：各除数应两两互质，可确保命题的真实性。
    五、推导《3、5、8剩余定理）及启用
    题目：一个数除以3余2；除以5余3；除以8则余1。此数最小是多少？
    摘录条件           3……2
    （基准数）（113）÷5……3
                        秦九韶著作8……1
    A、推导定理：只要能确定3、5、8各除数的余数均为1的基础数，便可推导出定理，随后再乘以各对应的余数，即可依此定理解题。
    （一）［3、5、8］＝120
    （二）求各除数的余数均为1的基础数
    （1）［3］120÷3＝40
          ［40］÷3＝13……1
    （2）［5］120÷5＝24  24÷5＝4……4
        ∵4×4－5×3＝l
        ∴24×4＝［96］
    （3）［8］120÷8＝15  15÷8＝1……7
        ∵7×7－8×6＝1　
        ∴15×7＝［105］
由此得出《3、5、8剩余定理》诗曰：
    三人同行40多， 五树梅花96朵，
    八仙过海105招，除百二十便解惑。
    （三）分别乘以各对应的余数再求和而获解
    40×2＋96×3＋105×l＝473
    （四）求最小的基准数
    473－120×3＝113
    B、启用定理，再解两题
    （一）      3……1
        （79）÷5……4
              8......7
    解：40×1＋96×4＋105×7＝1159
        1159－120×9＝79
    （二）      3……2
        （11）÷5……1
              8......3
    解：40×2＋96×1＋105×3＝491
        491－120×4＝11
    C、补充《3、4、5剩余定理》
    三人同行40里，四季花开45枝，
    五朵金花36浪，除去六十便得知。
              3......2
        （53）÷4……1
              5......3
    解：40×2＋45×1＋36×3＝233
        233－60×3＝53
    由此可知，“剩余问题”的“解法定理”，都是可以推得的，都是非常灵验的。
    通过对“剩余问题”的研讨，使我们进一步认识了其“解法定理”，提高了解题能力，证明其解题方法可行、实用、有趣和灵活多样。《3、5、8剩余定理》、《3、4、5剩余定理》……《a、b、c剩余定理》等“解法定理”的推导成功，证明对“剩余问题”完全可以运用“定理解题”。
中国剩余定理
 
数学研究所    李文林  袁向东
 
在我国古代劳动人民中，长期流传着“隔墙算”、“剪管术”、“秦王暗点兵”等数学游戏。有一首“孙子歌”①，甚至远渡重洋，输入日本：
“三人同行七十稀，五树梅花廿一枝，
七子团圆正半月，除百零五便得知。”
这些饶有趣味的数学游戏，以各种不同形式，介绍世界闻名的“孙子问题”的解法，通俗地反映了中国古代数学一项卓越的成就。
“孙子问题”在现代数论中是一个一次同余问题，它最早出现在我国公元四世纪的数学著作《孙子算经》中。《孙子算经》卷下“物不知数”题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？显然，这相当于求不定方程组
N=3x+2，N=5y+3，N=7x+2
的正整数解N，或用现代数论符号表示，等价于解下列的一次同余组：
N 2(mod3) 3(mod5) 2(mod7)②

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。