1.整除的概念和性质.ppt

第一章整数的整除性第一节整除的概念,一、基本概念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的任意一个排列，证明必是偶数。,例3将正方形ABCD分割成个相等的小方格（n是正整数），把相对的顶点A,C染成红色，B,D染成蓝色，其他交点任意染成红蓝两色中的一种颜色，证明：恰有三个顶点同颜色的小方格的数目必是偶数。,例4设正整数d不等于2,5,13，证明集合中可以找到两个数a，b，使得ab-1不是完全平方数。,二、整除,1、定义：设a，b是整数，b0。如果存在一个整数q使得等式：a=bq成立，则称b能整除a或a能被b整除，记ba；如果这样的q不存在，则称b不能整除a，记为ba。,注：显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。,素数：定义设整数n0，1.如果除了显然因数1，n以外，n没有其他因数，那么，n叫做素数（或质数或不可约数），否则，n叫做合数.规定：若没有特殊说明，素数总是指正整数，通常写成p或p1，p2，pn.例整数2，3，5，7都是素数，而整数4，6，8，10，21都是合数.,2、整除的性质,设a，b，c是整数（1）aa（2）如果ab，bc，则ac（3）如果ab，ac,则对任意整数m，n有amb+cn.,（4）如果ac，则对任何整数b，abc.（5）若（a，b）=1，且abc，则ac（6）若（a，b）=1，且ac，bc则abc（7）若（a，b）=1，且abc，则ac，bc,（8）若在等式中，除某一项外，其余各项都能被c整除，则这一项也能被c整除。,（3）素数判定法则：设n是一个正整数，如果对所有的素数p，都有pn，则n一定是素数.,（1）设p为素数，若pba，则pa或pb.（2）p|a或(p，a)=1.ppa,常用结论：,（4）任何大于1的整数a都至少有一个素约数。,推论任何大于1的合数a必有一个不超过的素约数。,例6证明：121，nZ。,10以内的素数是2,3,5,7，用它们除100以内大于10的数，删去所有能被它们整除的数，剩下的(含2,3,5,7在内)就是100以内的所有素数,表19.2筛法,最后剩下2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89和97.这25个数就是100以内的全部素数再用这25个素数除100210000以内大于100的数，删去所有能被它们整除的数，可以得到10000以内的所有素数重复这个做法可以得到任意给定的正整数以内的所有素数这个方法叫做埃拉托斯特尼(Eratosthene)筛法,人们一直在寻找更大的素数。近代已知的最大素数差不多总是形如2n1的数。当n是合数时，2n1一定是合数设n=ab，其中a1,b1，有,当n为素数时,221=3,2317,24131,271=127都是素数,而2111=2047=23x89是合数,设P为素数,称如2p1的数为梅森(MatinMerdenne)数.到2002年为止找到的最大梅森素数是2134669171,这个数有4百万位,可除性判别方法,判别方法1：（整数被2整除）如果一个整数的末尾数字能被2整除，则该数能被2整除。即：若2a0，则2N.判别方法2：（整数被5整除）如果一个整数的末尾数字能被5整除，则该数能被5整除。即：若5a0，则5N.判别方法3：（整数被3整除）如果一个整数的各位数字之和能被3整除，则该数能被3整除。即：若3an+an-1+a1+a0，则3N.判别方法4：（整数被9整除）如果一个整数的各位数字之和能被9整除，则该数能被9整除。即：若9an+an-1+a1+a0，则9N.,例6有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？,12345679,判别方法5：（整数被4或25整除）如果一个数的末两位数能被4或25整除，那么，这个数就一定能被4或25整除判别方法6：（整数被8或125整除）如果一个数的末三位数能被8或125整除，那么，这个数就一定能被8或125整除,可除性判别方法,可除性判别方法,判别方法7：（整数被11整除）(1)如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被11整除，则该整数能11整除.即如果，则11N.(2)把一个数由右边向左边数,将奇位上的数字与偶位上的数字分别加起来,再求它们的差,如果这个差是11的倍数(包括0),那么,原来这个数就一定能被11整除。例如：判断491678能不能被11整除。奇位数字的和9+6+8=23，偶位数位的和4+1+7=12，23-12=11因此,491678能被11整除。这种方法叫“奇偶位差法”。,可除性判别方法,判别方法8：（整数被13整除）如果一个整数将其最后三位数字去掉后得到的位数少3位的新整数与该整数末三位数字组成的数之差能被13整除，则该整数能13整除.即如果，则13N.判别方法9：（整数被7整除）（适用于数字位数少时）一个数割去末位数字，再从留下来的数中减去所割去数字的2倍，这样，一次次减下去，如果最后的结果是7的倍数（包括0），那么，原来的这个数就一定能被7整除例如：判断133是否7的倍数的过程如下：13327，所以133是7的倍数,例7设a，b，c是三个互不相等的正整数，求证：三数中至少有一个能被10整除。,例8设n为自然数，求证：能被1985整除。,例9设p为大于5的素数，求证：240,例10p5是素数，且2p+1也是素数，证明：4p+1必是合数。,例11请确定最小正整数A，其末位数为6，若将末位的6移至首位，其余数字不变，则为原数的4倍。,例12一个正整数，如果用7进位制表示，则为，如果用5进位制表示为，请用10进位制表示此数。,例13证明：对任何自然数n和k，数都不能分解成若干个连续的自然数之积。,例14设r是正奇数，证明：对任意的正整数n，有,例15设A=是n的所有约数的集合，则B=也是n的所有约数的集合。,例16以d(n)表示n的正约数的个数，例