搜索
第1章整除在日常生活中，我们会过到许多有趣而又耐人寻味的问题：某同学到文具店买了七个一角二分钱的本子、五个六分钱的铅笔和三个活页夹子。售货员收了他三元钱，并找还三角七分钱。这个同学马上对售货员说：“您的账算错了！”你能知道他为什么这样快就知道“算错了账”吗？排练团体操时，要求队伍变成10行、15行、18行、24行时，队形都能成为矩形，问最少需要多少人参加团体操的排练？§1.1十进制整数在小学数学中，我们主要学习的是整数的运算，思考整数是怎样表示的？“逢十进一”是什么意思？我们通常接触到整数都是十进制的整数。十进制计数法就是采取逢十进一的法则进行计数的方法。例如，1995就是由1个一千，9个一百，9个十和1个五组成，因此1995这个数就可以写成1995=1×1000+9×100+9×10+5.那么对于任意一个n+1位的正整数怎样用这种形式表示？为了表示方便，我们经常把用字母表示数字的多位数，在这个多位数上面加一个横线，以避免和乘法混淆，例如，37a56就表示一个五位数。§1.2数的整除设有两个整数a，b（b≠0），若有另一整数q，使得a=b×q，则称a被b整除；或b能整除a；若a被b整除，也成a是b的倍数；b是a的约数，并记作b|a.若a不能被b整除，则记作b∤a.我们曾经学过下述有关整除的判别法则：1、被2或5整除的数的特征是末位数字能被2或5整除；2、被4或25整除的数的特征是末两位数字能被4或25整除；3、被8或125整除的数字的特征是末三位数字能被8或125整除；4、被3或9整除的数的特征是个位数字的和能被3或9整除；5、被11整除的数的特征是其奇数位数字之和与偶数位数字之和的差能被11整除；解题过程中我们常用的性质：1、若a|b，b|c，则a|c；2、若a|b，a|c，则a|(b±c)；3、若a|b，则a|nb(n是正整数)；4、若a、b互质，且a|bc，则a|c；5、若a、b互质，且a|c，b|c，则ab|c；6、n个连续整数中，必有一个能被n整除；§1.3~1.4奇数和偶数把全体整数分成奇数类和偶数类是一种最常用的分类方法；奇数就是通常所述的单数，偶数就是通常所说的双数；一般的，一个整数如果能被2整除就叫做偶数，如果不能被2整除（即被2除余1）就叫做奇数；偶数可以记作2n，奇数可以记作2n-1或2n+1（n为整数）；奇数和偶数有一些十分简单又明显的性质：1、奇数不等于偶数；2、奇数±奇数=偶数，偶数±偶数=偶数，奇数±偶数=奇数；3、奇数个奇数的和是奇数，偶数个奇数的和是偶数，任意多个偶数的和都是偶数；4、奇数×奇数=奇数，偶数×整数=偶数，偶数×偶数=4的倍数；5、两个整数的和与这两个整数的差具有相同的奇偶性；6、奇数的平方为4k+1型的数，偶数的平方为4k型的数（k为整数）；7、任意两个整数的平方和被4除一定不余3；8、任意两个整数的平方差被4除一定不余2；§1.5质数与合数对于正整数可以依照它们的正约数的个数分为三类：一类是只有一个正约数的数，它就是1；一类是只有两个正约数的数，这两个正约数只能是1和它本身，例如5,7,11，这样的数叫做质数（也叫做素数）；第三类是有两个以上的正约数的数，例如6就有4个正约数：1,2,3,6，这样的数叫做合数。因此，正整数是由1，质数，合数三部分组成的。关于质数、合数有下列性质：1、质数有无限多个；2、除2以外的全体质数都是正奇数，除2以外的全体正偶数都是合数；3、大于1的整数的所有约数中，1以外的最小正约数一定是质数；4、如果a是合数，那么a的最小质因数一定不大于√a；§1.6算术基本定理每一个合数都可以写成几个质数相乘的形式，这几个质数叫做这个合数的质因数。把一个合数用质因数的连乘的形式来表示，叫做分解质因数。分解质因数有下面一个重要的定理：算术基本定理：任何一个正整数N1，都能分解成质因数的连乘积，即：𝐍=𝐏𝟏𝛂𝟏∙𝐏𝟐𝛂𝟐∙⋯∙𝐏𝐧𝛂𝐧，（n≥1）其中p1，p2，⋯，pn为互不相等的质数，α1，α2，⋯，αn是正整数；如果不考虑顺序，则这个分解式是唯一的。§1.7最大公约数与最小公倍数对于4、8、12这一组数，显然1、2、4都能整除它们中的每一个数，所以1、2、4都是它们的公约数，其中4是这些公约数中的最大的。把这个概念推广到一般情形，有如下定义：如果a1，a2，⋯，an和d都是正整数，且d|a1，d|a2，⋯，d|an，那么d叫做a1，a2，⋯，an的公约数。公约数中最大的叫做a1，a2，⋯，an的最大公约数，记作（a1，a2，⋯，an）。当（a，b）=1时，我们称a，b互质a1，a2，⋯，an的最大公约数（a1，a2，⋯，an）表示的是一个正数，是一个能够整除a1，a2，⋯，an并且能被a1，a2，⋯，an的每一个约数整除的数；常用的有关最大约数的性质有：1、若a|b，则（a，b）=a；2、若（a，b）=d，且n是正整数，则（na，nb）=nd；3、若n|a，n|b，则（a/n，b/n）=（a，b）/n；其中，性质3表明，若（a，b）=d，则（a/d，b/d）=1；4、若a=bq+r（0≤r𝑏），则（a，b）=（b，r）；对于4、8、12这一组数，24、48和72等都能被它们中的每一个数整除，24、48和72都叫他们的公倍数，而24是公倍数中最小的，把这个概念推广到一般形式，有如下的定义：如果a1，a2，⋯，an和m都是正整数，且a1|m，a2|m，⋯，an|m，那么m叫做a1，a2，⋯，an的公倍数。公倍数中最小的数叫做a1，a2，⋯，an的最小公倍数，记作[a1，a2，⋯，an]。5、若b|a，则[a，b]=a；6、若[a，b]=m，且n为正整数，则[na，nb]=mn；7、若n|a，n|b，则[a/n，b/n]=[a，b]/n；8、若[a，b]=m，则（m/a，m/b）=1；9、（a，b）=ab/[a，b]；第2章同余我们在解决一些有关整数的问题时，并不关心具体的数字是多少，而是关心被某个整数所除而得到的余数是多少。例如，2004年的元旦是星期四，2005年的元旦时星期几？因为2004年全年共有366天，而366除以7的余数是2，所以2005念得元旦是星期六，再如，今天是星期六，101010天后是星期几？这也是同余的问题；我国古代对同于问题有比较深入的研究，其中比较著名的有《孙子算经》中的“物不知数”问题，秦九韶的“大衍求一术”的解同余方程的方法，以及中国剩余定理。其实，有关同余的记载最早的是“韩信点兵”的故事。据说韩信在点兵的时候，为了军事保密，不让敌人知道自己的兵力，先让士兵从1到3报数，然后记住最后一个士兵所报的数；再让士兵从1到5报数，也记住最后一个士兵所报的数；最后让士兵从1到7报数报数，又记下最后一个士兵所报的数。这样，他很快算出了自己士兵的总人数，而敌人却无法弄清他的兵力，这都是利用同余方程解决的。然而，创立同余论的并不是我国古代的数学家，而是大数学家高斯，高斯最早使用了“同余”的概念，并创立了同余理论。下面我们就同余论做一个简单的介绍。§2.1同余的概念和性质顾名思义，同于就是余数相同，是指被一个正整数所除，得到的余数相同。定义：设a、b是两个整数，如果a和b被正整数m除所得余数相同，则称a与b对于模m同余，记作：𝑎≡𝑏（mod𝑚），否则，就称a与b对于模m不同余，记作𝑎≢𝑏（mod𝑚）。根据定义，a与b是否同于，不仅与a、b有关，还与模m有关，对一对数a和b，对于模m同余，而对于模n也许就不同余。根据同余的定义，显然有以下几种关系是成立的：（1）𝑎≡𝑎（mod𝑚）；（2）𝑎≡𝑏（mod𝑚）⟺𝑏≡𝑎（mod𝑚）；（3）𝑎≡𝑏（mod𝑚）𝑏≡𝑐（mod𝑚）}𝑎≡𝑐（mod𝑚）；由此可见，同余是一种等价关系，以上这三条分别叫做同余的反身性，对称性和传递性，而等式也具有这几条性质。§2.2剩余类与完全平方数一、剩余类一个整数被2除时，余数只能是0或1两种可能，因此可以把所有的整数按照被2除的余数分成两类，一类是被2除余数为0，另一类是被2除余数为1。也就是我们常说的偶数和奇数。同样的道理，一个整数被3除时，余数只能是0、1、2这三种可能的某一种，因此所有的整数按照被3除可以分成余数为0、1、2三类。一般地，任何一个整数。被一个非零的整数m除，可以得到商q和余数r，即a=mq+r。这里的r只能取O,l,2,…,m-1这m个值。全体整数可按对模m是否同余分为若干个两两不相交的集合，使得在同一个集合申的任意两个数对模m一定同余，而属于不同集合中的两个数对模m一定不同余。每下个这样的集合称为模m的同余类，或模m的剩余类。由模m的每个同余类中取定一个数作为代表构成一组数，这组数就称为模m的一个完全剩余系。根据剩余类的概念，很容易得到以下几条有关剩余类的性质：1、每一个整数一定包括在而且仅包含在模m的一个剩余类中；2、整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数；3、整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。实际上，同余式就是剩余类等式的一个特殊情况，是集合中一个元素，前面有关同余的一些性质对剩余类仍然成立。4、在任意取定的m+1个整数中，必有两个整数对模m同余；根据同余式的性质，我们很容易得到剩余系的其他一些性质：5、m个整数a1，a2，⋯，am是模m的一组完全剩余系的充要条件是a1，a2，⋯，am中的任意两个数对模m都不同余；6、如果a1，a2，⋯，am是模m的一组完全剩余系，那么对任意的整数c，c+a1，c+a2，⋯，c+am也是模m的一组完全剩余系；二、完全平方数若a为整数，则a2叫做完全平方数。例如1、4、9、16……等，下面我们利用同余式来研究完全平方数。完全平方数的个位数字只能是0、1、4、5、6、9；具有一下性质的数一定是非完全平方数：（1）个位数字是2、3、7、8的数；（2）𝑎≡2（mod3）；（3）𝑎≡2,3（mod4）；（4）𝑎≡2,3（mod5）；（5）𝑎≡2,3,5,6,7（mod8）；§2.3简单的同余方程《孙子算经》中的“物不知数”问题开创了一次同余式研究的先河，但遗憾的是没有上升到一套完整的计算程序和理论高度。南宋时期的数学家秦九韶在他的《数学九章》中提出了“大衍求一术”的算术方法，比较系统的论述一次同余方程组的解法的一般原理和一般程序。他的计算程序的核心是求一个数的多少倍除以另一个数所得的余数为1。对于n次整系数多项式𝑓(𝑥)=𝑎𝑛𝑥𝑛+𝑎𝑛−1𝑥𝑛−1+⋯+𝑎1𝑥+𝑎0𝑓(𝑥)≡0（mod𝑚）叫做模m的同余方程。是同余方程成立的x的值叫做同余方程的解。显然，若x=c是同余方程𝑓(𝑥)≡0（mod𝑚）的一个解，则剩余类cmodm中的每一个数都是这个方程的解。