一个题根从小学讲到高中
----------由带余除法到中国剩余定理
（一）什么是带余除法？
顾名思义,带余除法就是两个整数相除,除不尽而带有余数. 例如:7÷3=2…1.
这个式子的含义是：7除以3是除不尽的,运算的结果是商2余1. 这个式子带有省略号,不算太清楚,所以一般将其改写为;
7=3×2+1.
一般地,如果被除数是b,除以除数a后商数是q,余数是r,则有;
b?aq?r这个式子
题,就主要讲解并消化这个公式.
???
???,是带余除法的基本公式,也是研究整除问题的题根.我们这个专
千万别不屑一顾:无非是带余除法么？有什么高深莫测的？ 那么我且问你,以下几个问题你真的清楚吗？ 1.余数的基本性质.
问题1.如果除数是5,那么余数有哪几种可能？
【解析】直接举例,5,6,7,8,9除以5,余数分别为0,1,2,3,4; 以下10,11,12,13,14除以5,余数仍为0,1,2,3,4;
可以预见,再往下推理,余数仍然逃不出0,1,2,3,4这5个数的范围. 这就是说,任一整数除以5,其余数只有5种可能.
1
一般地说,任一整数除以正整数n,其余数有且只有0,1,2,…,n-1共n种可能. 特别提醒,余数必须是自然数而且比除数要小. 即 在式子???中,必定有0≤r＜a. 2.同余
问题2.写出100以内除以15余数是5的所有整数. 【解析】根据公式b=15a+5.
依次令a=0,1,2,3,4,5,6得:b=5,20,35,50,65,80,95. 同余的字面含义就是余数相等.
定义1:如果两个整数a,b,除以另一个整数c所得余数相等,就称这两个整数关于除数c同余.
（在一些关于整除研究的书籍里,用符号mod表示同余.例如
20≡35（mod15）,表示20,35这两个整数除以15所得余数相等,它们都是5.）
3.整数按同余分类
问题3.证明:任意3个连续正整数之和一定是3的倍数 【证明】将公式???具体写为:b=3k+r. 这里0≤r＜3,且r为整数,∴r=0,1或2.
于是所有整数按此同余可分为3类,即3k,3k+1和3k+2. 也就是任意3个连续整数,有且仅有3种写法: （1）3k,3k+1,3k+2,其和为9k+3; （2）3k-1,3k,3k+1,其和为9k; （3）3k-2,3k-1,3k,其和为9k-3. 无论哪种情况,其和均能为3整除,
2
所以, 任意3个连续正整数之和一定是3的倍数
评注:一般地,如果除数为n, ∵0≤r＜n,且r为整数,∴r=0,1,2,…,n-1 那么所有整数可分为n类,即nk,nk+1,nk+2,…,nk+（n-1）. 事实上,整数分为奇数与偶数,也还是依照公式???按同余分类. 此时b=2k+r,且只有r=0与1. 4.整除
问题4.证明999999能被13整除.
【解析】∵999999=999×1001,而1001=13×11×7 即999999=999×13×11×7,等式右边含有因数13, 故999999必能为13整除.
定义2.如果整数b除以整数a没有剩余（即在式???中,余数r=0）,则称整数a能为整数b整除.
定义3.如果整数b能为整数a整除,则称b为a的倍数, a为b的约数（或因数）如果a是质数,则称a为b的质因数.
问题5.写出999的所有因数,并指出哪些是质因数 【解析】999=3×3×3×37.
故999的所有约数为1,3, 3×3=9, 3×3×3=27,37,3×37=111, 9×37=333,999.共计8个.
在999的所有约数中,只有3与37是质因数.
注意1既不是质数,也不是合数.所以以上因数中,1不能称为质因数. 定义4.任一整数必定有1和本身两个约数,称它们为该整数的当然约数. 5.最大公约数与最小公倍数.
3
问题5. 写出36与45的所有公约数与公倍数 【解析】36的所有约数是1,2,3,4,6,9,12,18,36, 45的所有约数是1,3,5,9,15,45.
其中1,3,9既是36的约数.又是45的约数.所以1,3,9都是36与45的公约数.其中9是它们公约数中最大的,故称9为36与45的最大公约数.
36的倍数依次为36,72,108,144,180,… 45的倍数依次为45,90,135,180,….
其中180既是36的倍数,又是45的倍数,故称为36与45的公倍数. 这两个数的公倍数还有360,540,720,1440,…等无穷多个.但其中180是最小的,所以称180是36与45的最小公倍数.
定义5.几个整数的公约数中最大的一个,称为最大公约数; 几个整数公倍数中最小的一个叫做最小公倍数. 6.互质整数
问题6.25与16有公约数吗?为什么?
24?25?5,16?2【解析】∴25与16除1以外,再无其他公约数.
定义6.两个整数的公约数除1以外,再无其他,则称这两个整数互质. 反之,如果整数a与b互质,那么它们的最大公约数是1,而最小公倍数为a?b. 特别注意:整数的互质是没有传递性的.例如4与5互质,5与6也互质,由此并不能推出4与6也互质.事实上,4与6存在不是1的公约数2,所以它们不互质.
以上我们对公式
???进行了
6个方面的分析.其中最需要掌握,也是最难的重
点知识就是?同余?,这得从孙子问题说起.
（二）从?孙子问题?到 孙子定理
4
1.什么是?孙子问题?？
?孙子问题?源于我国古代流传下来的《孙子算经》,它是世界级的名题.原文是:?今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？? ①
注意到3,5,7都是质数. ?孙子问题?的实质是：求一个整数N,使它同时满足除以3余2,除以5余3,除以7余2.
假如只需求出这个?孙子问题?的一个答案,倒也简单:
既是这些物品数以3与7除之都余2,那么它最少有3×7+2=23（件） 注意到23正好满足除以5余3,所以所求物品的数量,最少有23件. 可是,23不是本题的唯一解,如果再加上3,5,7的公倍数105的任意整数倍, 即得到这个孙子问题的通解是
N=105k+23 （※）
其中k为非负整数,当k=0,1,2,3…时依次得23, 128,233.338,…等,它们都是这个孙子问题的解.
各位请看:这个公式（1）是不是我们前面提到的带余除法的基本公式？ 我国古人将孙子问题的解法浓缩为如下四句话;
三人同行七十稀，五树梅花廿一枝。 七子团圆正半月，除百零五便得知。
‘三人同行七十稀’,说的是70能够被5与7整除,但是被3除余1;‘五树梅花廿一支’,是说21是3与7的倍数,但被5除余1;‘七子团圆正半月’,是指15能够被3与5除尽,但被7除余1.这3句隐藏着孙子问题的正规解法是：
将70二倍得140,这时它还是5与7的倍数,但符合被3除余2;
5