第5讲同余的概念和性质.docx

第5讲同余的概念和性质.docx

《第5讲同余的概念和性质.docx》由会员分享，可在线阅读，更多相关《第5讲同余的概念和性质.docx（11页珍藏版）》请在冰点文库上搜索。

第5讲同余的概念和性质

第5讲同余的概念和性质

解题思路：

理解并熟记同余的性质，运用同余性质把数化小、化易。

同余定义：

若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：

　　a≡b（modm）.

性质1：

若a≡b（modm），b≡c（modm），那么a≡c（modm），（传递性）。

　★性质2：

若a≡b（modm），c≡d（modm），那么a±c≡b±d（modm），（可加减性）。

　★性质3：

若a≡b（modm），c≡d（modm），那么ac≡bd（modm）（可乘性）。

　　性质4：

若a≡b（modm），那么an≡bn（modm），（其中n为自然数）。

　　性质5：

若ac≡bc（modm），（c，m）=1，那么a≡b（modm），（记号（c，m）表示c与m的最大公约数）。

例1判定288和214对于模37是否同余，74与20呢？

例2求乘积418×814×1616除以13所得的余数。

例3求14389除以7的余数。

例4四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，…，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？

十位，…上的数码，再设M=

＋

＋…＋

，求证：

N≡M（mod9）

例6求自然数

＋

＋

的个位数字。

习题

1.验证对于任意整数a、b，式子a≡b（mod1）成立，并说出它的含义。

2.已知自然数a、b、c，其中c≥3，a除以c余1，b除以c余2，则ab除以c余多少？

3.1993年的六月一日是星期二，这一年的十月一日是星期几？

4.求33335555＋55553333被7除的余数。

5.所有自然数如下图排列.问300位于哪个字母下面？

6.数

，被13除余多少？

7.求1993100的个位数字.

第五讲同余的概念和性质

　　你会解答下面的问题吗？

　　问题1：

今天是星期日，再过15天就是“六·一”儿童节了，问“六·一”儿童节是星期几？

　　这个问题并不难答.因为，一个星期有7天，而15÷7=2…1，即15＝7×2+1，所以“六·一”儿童节是星期一。

　　问题2：

1993年的元旦是星期五，1994年的元旦是星期几？

　　这个问题也难不倒我们.因为，1993年有365天，而365=7×52+1，所以1994年的元旦应该是星期六。

　　问题1、2的实质是求用7去除某一总的天数后所得的余数.在日常生活中，时常要注意两个整数用某一固定的自然数去除，所得的余数问题.这样就产生了“同余”的概念.如问题1、2中的15与365除以7后，余数都是1，那么我们就说15与365对于模7同余。

　　同余定义：

若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：

　　a≡b（modm）.（*）

　　上式可读作：

　　a同余于b，模m。

　　同余式（*）意味着（我们假设a≥b）：

　　a-b=mk，k是整数，即m｜（a-b）.

　　例如：

①15≡365（mod7），因为365-15=350=7×50。

　　②56≡20（mod9），因为56-20=36＝9×4。

　　③90≡0（mod10），因为90-0＝90=10×9。

　　由例③我们得到启发，a可被m整除，可用同余式表示为：

a≡0（modm）。

　　例如，表示a是一个偶数，可以写

　　a≡0（mod2）

　　表示b是一个奇数，可以写

　　b≡1（mod2）

　　补充定义：

若m

（a-b），就说a、b对模m不同余，用式子表示是：

　　a

b（modm）

　　我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似.同余式有如下一些性质（其中a、b、c、d是整数，而m是自然数）。

　　性质1：

a≡a（modm），（反身性）

　　这个性质很显然.因为a-a=0=m·0。

　　性质2：

若a≡b（modm），那么b≡a（modm），（对称性）。

　　性质3：

若a≡b（modm），b≡c（modm），那么a≡c（modm），（传递性）。

　　性质4：

若a≡b（modm），c≡d（modm），那么a±c≡b±d（modm），（可加减性）。

　　性质5：

若a≡b（modm），c≡d（modm），那么ac≡bd（modm）（可乘性）。

　　性质6：

若a≡b（modm），那么an≡bn（modm），（其中n为自然数）。

　　性质7：

若ac≡bc（modm），（c，m）=1，那么a≡b（modm），（记号（c，m）表示c与m的最大公约数）。

　　注意同余式性质7的条件（c，m）＝1，否则像普通等式一样，两边约去，就是错的。

　　例如6≡10（mod4），而3

5（mod4），因为（2，4）≠1。

　　请你自己举些例子验证上面的性质。

　　同余是研究自然数的性质的基本概念，是可除性的符号语言。

例1判定288和214对于模37是否同余，74与20呢？

　　解：

∵288-214=74=37×2。

　　∴288≡214（mod37）。

　　∵74-20=54，而37

54，

　　∴74

20（mod37）。

例2求乘积418×814×1616除以13所得的余数。

分析若先求乘积，再求余数，计算量太大.利用同余的性质可以使“大数化小”，减少计算量。

　　解：

∵418≡2（mod13），

　　814≡8（mod13），1616≡4（mod13），

　　∴根据同余的性质5可得：

　　418×814×1616≡2×8×4≡64≡12（mod13）。

　　答：

乘积418×814×1616除以13余数是12。

例3求14389除以7的余数。

分析同余的性质能使“大数化小”，凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方，找找有什么规律。

　　解法1：

∵143≡3（mod7）

　　∴14389≡389（mod7）

　　∵89＝64+16+8+1

　　而32≡2（mod7），

　　34≡4（mod7），

　　38≡16≡2（mod7），

　　316≡4（mod7），

　　332≡16≡2（mod7），

　　364≡4（mod7）。

　　∵389≡364·316·38·3≡4×4×2×3≡5（mod7），

　　∴14389≡5（mod7）。

　　答：

14389除以7的余数是5。

　　解法2：

证得14389≡389（mod7）后，

　　36≡32×34≡2×4≡1（mod7），

　　∴384≡（36）14≡1（mod7）。

　　∴389≡384·34·3≡1×4×3≡5（mod7）。

　　∴14389≡5（mod7）。

例4四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，…，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？

分析与解答经观察试验我们可以发现，每经过4次互换，四盏灯的颜色排列重复一次，而1小时=60分钟=120×30秒，所以这道题实质是求120除以4的余数，因为120≡0（mod4），所以开灯1小时四盏灯的颜色排列刚好同一开始一样。

十位，…上的数码，再设M=a0＋a1＋…＋an，求证：

N≡M（mod9）。

分析首先把整数N改写成关于10的幂的形式，然后利用10≡1（mod9）。

　　又∵1≡1（mod9），

　　10≡1（mod9），

　　102≡1（mod9），

　　…

　　10n≡1（mod9），

　　上面这些同余式两边分别同乘以a0、a1、a2、…、an，再相加得：

　　a0＋a1×10+a2×102+…+an×10n

　　≡a0＋a1＋a2＋…＋an（mod9），

　　即N≡M（mod9）.

　　这道例题证明了十进制数的一个特有的性质：

　　任何一个整数模9同余于它的各数位上数字之和。

　　以后我们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可。

　　例如，求1827496被9除的余数，只要先求（1+8＋2＋7＋4＋9＋6），再求和被9除的余数。

　　再观察一下上面求和式.我们可以发现，和不一定要求出.因为和式中1＋8，2+7，9被9除都余0，求余数时可不予考虑.这样只需求4＋6被9除的余数.因此，1827496被9除余数是1。

　　有人时常利用十进制数的这个特性检验几个数相加、相减、相乘的结果对不对，这种检查方法叫：

弃九法。

　　弃九法最经常地是用于乘法.我们来看一个例子。

　　用弃九法检验乘式5483×9117≡49888511是否正确？

　　因为5483≡5＋4＋8＋3≡11≡2（mod9），

　　9117≡9＋1＋1＋7≡0（mod9），

　　所以5483×9117≡2×0≡0（mod9）。

　　但是49888511≡4+9＋8+8+8＋5+1+1

　　≡8（mod9），

　　所以5483×9117≠49888511，即乘积不正确。

　　要注意的是弃九法只能知道原题错误或有可能正确，但不能保证一定正确。

　　例如，9875≡9＋8+7+5≡2（mod9），

　　4873≡4＋8＋7＋3≡4（mod9），

　　32475689≡3+2+4+7＋5+6+8+9

　　≡8（mod9），

　　这时，9875×4873≡2×4≡32475689（mod9）。

　　但观察个位数字立刻可以判定9875×4873≠32475689.因为末位数字5和3相乘不可能等于9。

　　弃九法也可以用来检验除法和乘方的结果。

例6用弃九法检验下面的计算是否正确：

　　23372458÷7312＝3544。

　　解：

把除式转化为：

　　3544×7312＝23372458。

　　∵3544≡3＋5＋4＋4≡7（mod9），

　　7312≡7＋3＋1＋2≡4（mod9），

　　∴3544×7312≡7×4≡1（mod9），

　　但23372458≡2＋3＋3＋8≡7（mod9）。

　　而1

7（mod9）

　　∴3544×7312≠23372458，

　　即23372458÷7312≠3544。

例7求自然数2100＋3101＋4102的个位数字。

分析求自然数的个位数字即是求这个自然数除以10的余数问题。

　　解：

∵2100≡24×25≡625≡6（mod10），

　　3101≡34×25·31≡125·31≡3（mod10），

　　4102≡（22）100·42≡6·6≡6（mod10），

　　∴2100＋3101＋4102≡6＋3＋6≡5（mod10），

　　即自然数2100＋3101＋4102的个位数字是5.

习题五

　　1.验证对于任意整数a、b，式子a≡b（mod1）成立，并说出它的含义。

　　2.已知自然数a、b、c，其中c≥3，a除以c余1，b除以c余2，则ab除以c余多少？

　　3.1993年的六月一日是星期二，这一年的十月一日是星期几？

　　4.求33335555＋55553333被7除的余数。

　　5.所有自然数如下图排列.问300位于哪个字母下面？

　　6.

数，被13除余多少？

（提示：

先试除，可知13|111111，而1993≡1（mod6））。

　　7.用弃九法检验下面运算是否正确：

　　①845×372=315340；

　　②12345×67891=838114385；

　　③1144192613÷28997＝39459。

　　8.求1993100的个位数字.

习题五解答

　　1.例：

∵1|a-b，2≡3（mod1），7≡15（mod1），式子a≡b（mod1）的含义是：

任意整数a、b对模1同余.整数是模1的同余类。

　　2.解：

∵a≡1（modc），b≡2（modc），

　　∴ab＝2（modc）

　　即ab除以c余2。

　　3.1993年的十月一日是星期五。

　　4.解：

∵3333≡1（mod7），

　　∴33335555≡1（mod7）。

　　又∵5555≡4（mod7），

　　∴55553333＝43333（mod7）。

　　而43≡1（mod7），

　　∵43333≡（43）1111≡1（mod7），

　　∴33335555+55553333≡1+1≡2（mod7），

　　即33335555＋55553333被7除余2。

　　5.解：

∵300≡6（mod7）。

　　∴300与6在同一列，在D下面。

　　6.答：

余1。

　　7.①不正确；

　　②不正确；

　　③不正确。

　　8.1.