第五讲 同余的概念和性质.doc

第五讲 同余的概念和性质你会解答下面的问题吗？问题1：假设今天是星期日，再过15天就是“六一”儿童节了，问“六一”儿童节是星期几？这个问题并不难答.因为，一个星期有7天，而157=21，即1572+1，所以“六一”儿童节是星期一。问题2：1993年的元旦是星期五，1994年的元旦是星期几？这个问题也难不倒我们.因为，1993年有365天，而365=752+1，所以1994年的元旦应该是星期六。 问题1、2的实质是求用7去除某一总的天数后所得的余数.在日常生活中，时常要注意两个整数用某一固定的自然数去除，所得的余数问题.这样就产生了“同余”的概念.如问题1、2中的15与365除以7后，余数都是1，那么我们就说15与365对于模7同余。同余定义：若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：ab（modm）. （*）上式可读作：a同余于b，模m。同余式（*）意味着（我们假设ab）：a-b=mk，k是整数，即m（a-b）.例如：15365（mod7），因为365-15=350=750。5620（mod9），因为56-20=3694。900（mod10），因为90-090=109。由例我们得到启发，a可被m整除，可用同余式表示为：a0（mod m）。例如，表示a是一个偶数，可以写a0（mod 2）表示b是一个奇数，可以写b1（mod 2） 我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似.同余式有如下一些性质（其中a、b、c、d是整数，而m是自然数）。性质1：aa（mod m），（反身性）这个性质很显然.因为a-a=0=m0。性质2：若ab（mod m），那么ba（mod m），（对称性）。性质3：若ab（mod m），bc（mod m），那么ac（mod m），（传递性）。性质4：若ab（mod m），cd（mod m），那么acbd（mod m），（可加减性）。性质5：若ab（mod m），cd（mod m），那么acbd（mod m）（可乘性）。性质6：若ab（mod m），那么anbn（mod m），（其中n为自然数）。性质7：若acbc（mod m），（c，m）=1，那么ab（mod m），（记号（c，m）表示c与m的最大公约数）。注意同余式性质7的条件（c，m）1，否则像普通等式一样，两边约去，就是错的。例如610（mod 4），而35（mod 2），因为（2，4）1。请你自己举些例子验证上面的性质。同余是研究自然数的性质的基本概念，是可除性的符号语言。例1 判定288和214对于模37是否同余？解：288-214=74=372。288214（mod37）。例2 求乘积4188141616除以13所得的余数。分析 若先求乘积，再求余数，计算量太大.利用同余的性质可以使“大数化小”，减少计算量。解：4182（mod13），8148（mod13），16164（mod13）， 根据同余的性质5可得：41881416162846412（mod13）。答：乘积4188141616除以13余数是12。例3 求14389除以7的余数。分析 同余的性质能使“大数化小”，凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方，找找有什么规律。解法1：1433（mod7）14389389（mod 7）8964+16+8+1而322（mod 7），344（mod7），38162（mod 7），3164（mod 7），332162（mod 7），3644（mod 7）。38936431638344235（mod 7），143895（mod 7）。答：14389除以7的余数是5。解法2：证得14389389（mod 7）后，363234241（mod 7），384（36）141（mod 7）。3893843431435（mod 7）。143895（mod 7）。例4 四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？分析 与解答经观察试验我们可以发现，每经过4次互换，四盏灯的颜色排列重复一次，而1小时=60分钟=12030秒，所以这道题实质是求120除以4的余数，因为1200（mod 4），所以开灯1小时四盏灯的颜色排列刚好同一开始一样。十位，上的数码，再设M=a0a1an，求证：NM（mod 9）。分析 首先把整数N改写成关于10的幂的形式，然后利用101（mod 9）。又 11（mod 9），101（mod 9），1021（mod 9），10n1（mod 9），上面这些同余式两边分别同乘以a0、a1、a2、an，再相加得：a0a110+a2102+an10na0a1a2an（mod 9），即 NM（mod 9）.这道例题证明了十进制数的一个特有的性质：任何一个整数模9同余于它的各数位上数字之和。以后我们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可。例如，求1827496被9除的余数，只要先求（1+827496），再求和被9除的余数。再观察一下上面求和式.我们可以发现，和不一定要求出.因为和式中18，2+7，9被9除都余0，求余数时可不予考虑.这样只需求46被9除的余数.因此，1827496被9除余数是1。有人时常利用十进制数的这个特性检验几个数相加、相减、相乘的结果对不对，这种检查方法叫：弃九法。弃九法最经常地是用于乘法.我们来看一个例子。用弃九法检验乘式5483911749888511是否正确？因为 54835483112（mod 9），911791170（mod 9），所以 54839117200（mod 9）。但是 498885114+98+8+85+1+18（mod9），所以 5483911749888511，即乘积不正确。要注意的是弃九法只能知道原题错误或有可能正确，但不能保证一定正确。例如，987598+7+52（mod 9），487348734（mod 9），324756893+2+4+75+6+8+98（mod 9），这时，987548732432475689（mod 9）。但观察个位数字立刻可以判定9875487332475689.因为末位数字5和3相乘不可能等于9。弃九法也可以用来检验除法和乘方的结果。巩固练习1、某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？2、70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个数的和，这一行最左边的几个数是这样的：0，1，3，8，21，问这一行数最右边的一个数被6除的余数是几？3、判断427843968267=1697598942346 计算是否正确4. 甲、乙两数的和是1088，甲数除以乙数商11余32，求甲、乙两数5. 三个不同的自然数的和为2001，它们分别除以19,23,31所得的商相同，所得的余数也相同，这三个数是_，_，_。6. 在除13511，13903及14589时能剩下相同余数的最大整数是_7、一个家庭，有父、母、兄、妹四人，他们任意三人的岁数之和都是3的整数倍，每人的岁数都是一个质数，四人岁数之和是100，父亲岁数最大，问：母亲是多少岁? 8、有48本书分给两组小朋友，已知第二组比第一组多5人如果把书全部分给第一组，那么每人4本，有剩余；每人5本，书不够如果把书全分给第二组，那么每人3本，有剩余；每人4本，书不够问：第二组有多少人? 9、 学校新买来118个乒乓球，67个乒乓球拍和33个乒乓球网，如果将这三种物品平分给每个班级，那么这三种物品剩下的数量相同请问学校共有多少个班？10、六名小学生分别带着14元、17元、18元、21元、26元、37元钱，一起到新华书店购买成语大词典一看定价才发现有5个人带的钱不够，但是其中甲、乙、丙3人的钱凑在一起恰好可买2本，丁、戊2人的钱凑在一起恰好可买1本这种成语大词典的定价是_元11、求除以17的余数12、已知n是正整数，规定，令，则整数m除以2008的余数为多少？答案1、假设有一名学生不参加演出，则结果一定是不管每列站8人或9人或10人都将刚好站齐。因此此时学生人数应是8、9、10公倍数，而8、9、10的最小公倍数是360，因此可知该年级共有361人。2、思路分析：如果将这70个数一一列出，得到第70个数后，再用它去除以6得余数，总是可以的，但计算量太大。即然这70个数中：中间的一个数的3倍是它两边的数的和，那么它们被6除以后的余数是否有类似的规律呢？0，1，3，8，21，55，144，被6除的余数依次是0，1，3，2，3，1，0，结果余数有类似的规律，继续观察，可以得到：0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，可以看出余数前12个数一段，将重复出现。702=510，第六段的第十个数为4，这便是原来数中第70个数被6除的余数。3、思路分析：若直接将右边算出，就可判断417843968267=169778335328，可知以上两结果均是错的；但是计算量太大。如果右式和左式相等，则它们除以某一个数余数一定相同。因为求一个数除以9的余数只需要先求这个数数字之和除以9的余数，便是原数除以9的余数。我考虑上式除以9的余数，如果余数不相同，则上式一定不成立。（1）从个位数字可知，右式的个位数字只能是8，而右式个位为6，因此上式不成立。以上是用除9取余数来验证结果是否正确，常被称为弃九法。不过应该注意，用弃九法可发现错误，但用弃九法没找出错误却不能保证原题一定正确。4、(法1)因为 甲乙，所以 甲乙乙乙乙；则乙，甲乙(法2)将余数先去掉变成整除性问题，利用倍数关系来做：从中减掉以后，就应当是乙数的倍，所以得到乙数，甲数5、 设所得的商为，除数为，由，可求得，所以，这三个数分别是，。6、因为, ，由于13511，13903，14589要被同一个数除时，余数相同，那么，它们两两之差必能被同一个数整除，所以所求的最大整数是987、从任意三人岁数之和是3的倍数，100除以3余1，就知四个岁数都是型的数，又是质数只有7，13，19，31，37，43，就容易看出：父43岁，母37岁，兄13岁，妹7岁8、由，知，一组是10或11人同理可知，知，二组是13、14或15人，因为二组比一组多5人，所以二组只能是15人，一组1