作业帮孙子定理大概内容及解法
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/28 20:20:35
孙子定理大概内容及解法
孙子定理
大概内容及解法
孙子定理大概内容及解法
中国古代求解一次同余式组（见同余）的方法.是数论中一个重要定理.又称中国剩
1、分别找出能任两个数整除,而满足被第三个整除余几的数. 2、将三个未知数加起来,减去这三个数的最小2倍数. N≡R1(mod d1) ≡R2(mod d2)≡R3(mod d3) 则N=k1d2d3R1+k2d1d3R2+k3d1d2R3±d1d2d3P 其中 P为任意非负整数 k1是满足k1d2d3≡1(mod d1)的最小正整数 k2是满足k2d1d3≡1(mod d2)的最小正整数 k3是满足k3d1d2≡1(mod d3)的最小正 解法中的三个关键数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 题中有三个数,分别为3、5、7,5*7/3余数为2,取35；3*7/5余数为1,要使余数为3,只需将3*7扩大3倍变成63即可；同样3*5/7的余数为1,要使余数为2,则将3*5扩大2倍,变成30.
编辑本段数学公式
（中国剩余定理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