同余的概念和性质

同余的概念和性质
你会解答下面的问题吗？
　　问题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（mod 2）
　　表示b是一个奇数，可以写
　　b≡1（mod 2）
　　补充定义：若m（a-b），就说a、b对模m不同余，用式子表示是：
　　ab（modm）
　　我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似.同余式有如下一些性质（其中a、b、c、d是整数，而m是自然数）。
　　性质1：a≡a（mod m），（反身性）
　　这个性质很显然.因为a-a=0=m•0。
　　性质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±c≡b±d（mod m），（可加减性）。
　　性质5：若a≡b（mod m），c≡d（mod m），那么ac≡bd（mod m）（可乘性）。
　　性质6：若a≡b（mod m），那么an≡bn（mod m），（其中n为自然数）。
　　性质7：若ac≡bc（mod m），（c，m）=1，那么a≡b（mod m），（记号（c，m）表示c与m的最大公约数）。
　　注意同余式性质7的条件（c，m）＝1，否则像普通等式一样，两边约去，就是错的。
　　例如6≡10（mod 4），而35（mod 4），因为（2，4）≠1。
　　请你自己举些例子验证上面的性质。
　　同余是研究自然数的性质的基本概念，是可除性的符号语言。
例1 判定288和214对于模37是否同余，74与20呢？
　　解：∵288-214=74=37×2。
　　∴288≡214（mod37）。
　　∵74-20=54，而3754，
　　∴7420（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（mod 7）
　　∵89＝64+16+8+1
　　而32≡2（mod 7），
　　34≡4（mod7），
　　38≡16≡2（mod 7），
　　316≡4（mod 7），
　　332≡16≡2（mod 7），
　　364≡4（mod 7）。
　　∵389≡364•316•38•3≡4×4×2×3≡5（mod 7），
　　∴14389≡5（mod 7）。
　　答：14389除以7的余数是5。
　　解法2：证得14389≡389（mod 7）后，
　　36≡32×34≡2×4≡1（mod 7），
　　∴384≡（36）14≡1（mod 7）。
　　∴389≡384•34•3≡1×4×3≡5（mod 7）。
　　∴14389≡5（mod 7）。