(第十一节同余问题.docVIP

第三章 第十一节 同余问题 093数教 黄欢 01号 在整数除法运算中，被除数与除数可能是整除关系，也可能不是整除关系。而许多问题，只需要知道余数。由此形成了专门研究余数的问题，即同余问题。 一、带余除法的定义 如果a，b是两个整数，b0，那么一定有而且只有两个整数q，r使 a=bq+r，（0≤rb）. 我们称r为a除以b的余数，q为a除以b的不完全商。 整数集合是可按余数分类。一个整数被正整数b除时，余数只有0，1，2，…，b-1这b种情况。我们把被b除同时都余r (0≤r＜b)的一类数，叫做b的剩余类。因此，数b的剩余类共有b个。这样整数就被分成b类。 比如，一个整数被2除时的余数只能是0和1，所以整数可分为两类，即余数为0的偶数，记为2k，余数为1的奇数，记为2k+1，其中k为任意整数。 一个整数被3除时的余数只能是0和1，2，所以整数可分为三类，即被3整除的一类，记为3k，被3除余1的一类，记为3k+1，被3除余2的一类，记为3k+2，其中k取任意整数。 二、同余的概念 两个整数a与b除以整数m（m0），如果余数相同，则称a与b关于模m同余。并用下面的同余式表示 a≡b(mod m). a≡b(mod m) ?a=b+km,(k∈N) ?m|(a-b). 同余的概念和记号都是德国数学家高斯在他的名著《算术研究》（1801年）中引进的，是研究数论的重要工具。 三、同余的性质 1.（反身性）a≡a(mod m)； 2.(对称性) 如果a≡b(mod m)；那么b≡a(mod m)； 3.（传递性）如果a≡b(mod m),b≡c(mod m),那么a≡c(mod m)； 4.如果a≡b(mod m),c≡d(mod m),那么a±b≡c±d(mod m)； 5.a+b≡c(mod m)当且仅当a≡c-b(mod m)； 6.如果a≡b(mod m),c≡d(mod m),那么ac≡bd(mod m),an≡bn(mod m),(n为正整数)，ak≡bk(mod m) (k为正整数)。 例1 从自然数1，2，3，…，1000中，最多可取出多少个数使得所取出的数中任意三个数之和能被18整除？ 【解】设a,b,c,d是所取出的数中的任意4个数，依题意任意三个数之和能被18整除，则a+b+c,a+b+d也能被18整除。 设a+b+c=18q1,a+b+d=18q2（q1,q2∈N）相减得c-d=18(q1-q2),所以18|（c-d）,所以c≡d(mod m). 由于c,d的任意性，说明所取的每一个数除以18所得的余数均想同。设 a=18a1+r,b=18b1+r,c=18c1+r, 其中a1,b1,c1∈N,0≤r＜18, a+b+c=18(a1+b1+c1)+3r. 因为18|（a+b+c）,所以18|(3r),即6|r,所以r=0,6,12. 因此，需要从1，2，3，…，1000这1000个数中把被18整除的数和被18除余6，余12的数全部取出来。因为 1000÷18=55……10 所以，最多取出55+1=56个符合要求的数，它们分别是6，24，42，…，996. 如果取被18整除的数或被18除余12的数，则只能取出55个. 例2 证明任意平方数除以8的余数为0，1，或4.（这是平方数的重要特征） 【证明】对整数分类讨论： （1）若n=2k+1,k∈N,则n2=(2k+1)2=4k2+4k(k+1)+1.因为k(k+1)为偶数，所以8|4k（k+1）,所以n2≡1(mod 8). (2)若n=2k,k∈N,则n2=4k2. ①当k=2t,t∈N时，n2=4k2=4(2t)2=16t2≡0(mod 8) ②当k=2t+1,t∈N时，n2=4k2=4(2t+1)2=4(4t2+4t+1) =16(t2+t)+4≡4(mod 8).所以 n2≡0(mod 8)，或n2≡1(mod 8)，或n2≡4(mod 8)。 例3（1）求32003除以13的余数；（2）今天是星期四，再过4737天是星期几？（3）求4735+5281×27924的末尾数字。 【解】（1）∵ 33=27≡1（mod 13）, ∴32003=33×667+2=(33)667×32≡1667×32≡9(mod 13), 所以32003除以13余9.