第一章整数的整除性第一节整除的概念•一、基本概念1、自然数、整数2、正整数、负整数3、奇数、偶数•一个性质：整数+整数=整数整数-整数=整数整数*整数=整数关于奇数和偶数性质：1.奇数+奇数=偶数；奇数+偶数=奇数；偶数+偶数=偶数；2.两个数之和是奇（偶）数，则这两个数的奇偶性相反（同）。3.若干个整数之和为奇数，则这些数中必有奇数，且奇数的个数为奇数个；若干个整数之和为偶数，则这些数中若有奇数，奇数的个数必为偶数个。关于奇数和偶数性质：4.奇数×奇数=奇数；奇数×偶数=偶数；偶数×偶数=偶数；5.若干个整数之积为奇数，则这些数必为奇数；若干个整数之积为偶数，则这些数中至少有一个是偶数。6.若a是整数，则|a|与a有相同的奇偶性。7.若a，b是整数，则a+b与a-b奇偶性相同。例1在1,2,3，，1998,1999这1999个数的前面任意添加一个正号或负号，问它们的代数和是奇数还是偶数？例2设n为奇数，是1,2，，n的任意一个排列，证明必是偶数。12,,,naaa12(1)(2)()naaan例3将正方形ABCD分割成个相等的小方格（n是正整数），把相对的顶点A,C染成红色，B,D染成蓝色，其他交点任意染成红蓝两色中的一种颜色，证明：恰有三个顶点同颜色的小方格的数目必是偶数。2n例4设正整数d不等于2,5,13，证明集合中可以找到两个数a，b，使得ab-1不是完全平方数。2,5,13.d二、整除•1、定义：设a，b是整数，b≠0。如果存在一个整数q使得等式：a=bq成立，则称b能整除a或a能被b整除，记ba∣；如果这样的q不存在，则称b不能整除a，记为ba。注：显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。|•素数：–定义设整数n≠0，±1.如果除了显然因数±1，±n以外，n没有其他因数，那么，n叫做素数（或质数或不可约数），否则，n叫做合数.–规定：若没有特殊说明，素数总是指正整数，通常写成p或p1，p2，…，pn.–例整数2，3，5，7都是素数，而整数4，6，8，10，21都是合数.2、整除的性质设a，b，c是整数（1）a∣a（2）如果a∣b，b∣c，则a∣c（3）如果a∣b，a∣c,则对任意整数m，n有amb+cn.∣（4）如果a∣c，则对任何整数b，a∣bc.（5）若（a，b）=1，且a∣bc，则a∣c（6）若（a，b）=1，且a∣c，b∣c则ab∣c（7）若（a，b）=1，且ab∣c，则a∣c，b∣c（8）若在等式中，除某一项外，其余各项都能被c整除，则这一项也能被c整除。11mnijijab（3）素数判定法则：设n是一个正整数，如果对所有的素数p≤，都有pn，则n一定是素数.n（1）设p为素数，若p∣ba，则p∣a或p∣b.（2）p|a或(p，a)=1.ppa常用结论：（4）任何大于1的整数a都至少有一个素约数。推论任何大于1的合数a必有一个不超过的素约数。a2a例6证明：121，nZ。2212nn1010以内的素数是以内的素数是2,3,5,72,3,5,7，用它们除，用它们除100100以内大于以内大于1010的数，删去所有能被它们整除的数，剩下的的数，删去所有能被它们整除的数，剩下的((含含2,3,5,72,3,5,7在内在内))就是就是100100以内的所有素数．以内的所有素数．123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888980919293949596979899100表表19.219.2筛法筛法最后剩下最后剩下2,3,5,7,11,13,17,19,23,29,31,37,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,8941,43,47,53,59,61,67,71,73,79,83,89和和97.97.这这2525个数就是个数就是100100以内的全部素数．以内的全部素数．再用这再用这2525个素数除个素数除10010022＝＝1000010000以内大于以内大于100100的的数，删去所有能被它们整除的数，可以得到数，删去所有能被它们整除的数，可以得到1000010000以内的所有素数以内的所有素数．．重复这个做法可以得到任意给定的正整数以内的所有重复这个做法可以得到任意给定的正整数以内的所有素数．这个方法叫做素数．这个方法叫做埃拉托斯特尼埃拉托斯特尼(Eratosthene)(Eratosthene)筛筛法．法．人们一直在人们一直在寻找更大的素数寻找更大的...
