一个题根从小学讲到高中.从带余除法到中国剩余定理选编.docx

 PAGE \* MERGEFORMAT 23 一个题根从小学讲到高中 由带余除法到中国剩余定理 （一）什么是带余除法？ 顾名思义,带余除法就是两个整数相除,除不尽而带有余数. 例如:7÷3=2…1. 这个式子的含义是：7除以3是除不尽的,运算的结果是商2余1. 这个式子带有省略号,不算太清楚,所以一般将其改写为; 7=3×2+1. 一般地,如果被除数是b,除以除数后商数是q,余数是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种可能. 一般地说,任一整数除以正整数n,其余数有且只有0,1,2,…,n-1共n种可能. 特别提醒,余数必须是自然数而且比除数要小. 即 在式子中,必定有0≤r＜. 2.同余 问题2.写出100以内除以15余数是5的所有整数. 【解析】根据公式b=15+5. 依次令=0,1,2,3,4,5,6得:b=5,20,35,50,65,80,95. 同余的字面含义就是余数相等. 定义1:如果两个整数,除以另一个整数所得余数相等,就称这两个整数关于除数同余. （在一些关于整除研究的书籍里,用符号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整除, 所以, 任意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除以整数没有剩余（即在式中,余数r=0）,则称整数能为整数b整除. 定义3.如果整数b能为整数整除,则称b为的倍数, 为b的约数（或因数）如果是质数,则称为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.最大公约数与最小公倍数. 问题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有公约数吗?为什么? 【解析】∴25与16除1以外,再无其他公约数. 定义6.两个整数的公约数除1以外,再无其他,则称这两个整数互质.