什么是剩余定理?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/04/27 20:45:56
什么是剩余定理?
什么是剩余定理?
什么是剩余定理?
中国古代求解一次同余式组（见同余）的方法.是数论中一个重要定理.又称孙子定理.
内容
公元前后的《孙子算经》中有“物不知数”问题：“今有物不知其数,三三数之余二 ,五五数之余
三 ,七七数之余二,问物几何?”答为“23”.也就是求同余式组x≡2 （mod3）,x≡3 （mod5 ）,x≡2 （mod7）（式中a≡b （modm）表示m整除a－b ）的正整数解.明朝程大位用歌谣给出了该题的解法：“三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知.”即解为x≡2×70＋3×21＋2×15≡233≡23(mod105）.此定理的一般形式是设m = m1 ,… ,mk 为两两互素的正整数,m＝m1,…mk ,m＝miMi,i＝1,2,… ,k .则同余式组x≡b1(modm1),…,x≡bk(modmk)的解为x≡M'1M1b1＋…＋M'kMkbk （modm）.式中M'iMi≡1 （modmi）,i＝1,2,…,k .直至18世纪 C.F.高斯才给出这一定理.孙子定理对近代数学如环论,赋值论都有重要影响.
解法
解法中的三个关键数70,21,15,有何妙用,有何性质呢?首先70是3除余1而5与7都除得尽的数,所以70a是3除余a,而5与7都除得尽的数,21是5除余1,而3与7都除得尽的数,所以21b是5除余b,而3与7除得尽的数.同理,15c是7除余c,3与5除得尽的数,总加起来 70a+21b+15c 是3除余a,5除余b ,7除余c的数,也就是可能答案之一,但可能不是最小的,这数加减105(105=3*5*7)仍有这样性质,可以多次减去105而得到最小的正数解.附：如70,其实是要找余2的,但只要找到了余1的再乘2即余二了.孙子问题的解法,以现代的说法,是找出三个关键数70,21,15.解法的意思就是用70乘3除所得的余数,21乘5除所得的余数,15乘7除所得的余数,然后总加起来,除以105的余数就是答案.即题目的答案为 70×2+21×3+15×2 =140+63+30 =233 233-2×105=23 公式：70a+21b+15c-105n
数学公式
（中国剩余定理CRT）设m1,m2,...,mk是两两互素的正整数,即gcd(mi,mj) =1,i≠j,i,j = 1,2,...,k 则同余方程组：x≡b1 mod m1 x≡b2 mod m2 ...x≡bk mod mk 模[m1,m2,...,mk]有唯一解,即在[m1,m2,...,mk]的意义下,存在唯一的x,满足：x≡bi mod [m1,m2,...,mk],i = 1,2,...,k