孙子定理

孙子定理

中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国剩余定理。公元前后的《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？”答为“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除所得的馀数，21乘5除所得的馀数，15乘7除所得的馀数，然後总加起来，除以105的余数就是答案。

即题目的答案为 70×2+21×3+15×2

=140+63+30

=233

233-2×105=23

公式：70a+21b+15c-105n

解法中的三个关键数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而得到最小的正数解。