初中数学竞赛讲座数论部分7同余

第7讲同余的概念及基本性质

数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯．

先看一个游戏：有n＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？

取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格．最后只剩4个空格时，你的对手就必输无疑了．因此，若n除以4的余数是1，2或3时，那么先走者甲胜；若n除以4的余数是0的话，那么后走者乙胜．

在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么．又例如，1999年元旦是星期五，1999年有365天，365=7×52＋1，所以2000年的元旦是星期六．这里我们关心的也是余数．这一讲中，我们将介绍同余的概念、性质及一些简单的应用．

同余，顾名思义，就是余数相同．

一、基础知识

定义1 给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作

a≡b(mod m)，

并读作a同余b，模m．

否则，就称a与b对于模m不同余，记作a≡b（mod m），

根据定义，a与b是否同余，不仅与a、b有关，还与模m有关，同一对数a和b，对于模m同余，而对于模n也许就不同余，例如，5≡8（mod 3），而5≡8（mod 4），若a与b对模m同余，由定义1，有

a=mq1＋r，b=mq2+r．

所以a-b=m(q1-q2)，

即m｜a-b．

反之，若m｜a-b，设

a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，

则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2．

于是，我们得到同余的另一个等价定义：

定义2 若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a 与b对模m同余．

另外，根据同余的定义，显然有以下几种关系是成立的：

⑴a≡a（mod n）

⑵a≡b（mod m）⇔b≡a（mod n）

⑶a≡b（mod n）

⇒a≡c（mod m）

b≡c（mod m）

由此可见，同余是一种等价关系，以上这三条分别叫做同余的反射性，对称性和传递性，而等式也具有这几条性质．

二、典型例题;

例1．如果a≡b（mod m），以下命题正确的有哪些？请说明理由？

⑴m | a－b

⑵a = b+mt

⑶a = k1m+ r1，b = k2m+ r2（0≤r1，r2＜m）⇔r1= r2

解：⑴因a≡b（mod m），所以可得a = k1m+ r，b = k2m+ r，那么a－b=（k1－k2）m，由于k1－k2是整数，因此m | a－b是正确的．

⑵根据⑴可得a－b= mt，即a= b+mt

⑶根据⑴可得，m | r1－r2，又因为0≤| r1－r2 |＜m，所以| r1－r2 |=0，故r1= r2．

例2．判断正误，并说明理由．

⑴如果a≡b（mod m）那么ka≡kb（mod m）

⑵如果a≡b（mod m），c是整数，那么a±c≡b±c (mod m)

⑶如果a1≡b1（mod m），a2≡b2（mod m），那么a1±a2≡b1±b2 (mod m)，

a1a2≡b1b2 (mod m)．

⑷如果3a≡3b(mod 6 )，那么a≡b (mod 6 )

解：⑴∵a≡b（mod m），∴m | a－b，∴m | k (a－b)即m | (ka－kb)

∴ka≡kb（mod m）⑴成正确

⑵∵a≡b（mod m），∴m | a－b

又因为c是整数，所以m | a－c－b+c，即m | (a－c) －(b－c)即a－c≡b－c（mod m）同理可得，a+c≡b+c（mod m）

⑶仿照上面的两个小题的方汪，可以判定这个命题也是正确的

⑷显然6≡12(mod 6)，而2≡ 4 (mod 6)，因此，这个命题不正确

说明：⑶的结论可以得到同余的另一条性质，即a≡b（mod m）⇒a n≡b n（mod m）此题说明两个同余式能够象等式一样进行加、减、乘、乘方，但同余式两边却不能除以同一数，那么，同余式的两边在什么情况下可以同除以一个数呢？我们先看下面的例题．

例3．由下面的哪些同余式可以得到同余式a≡b（mod 5）

①3a ≡3b （mod 5） ②10a ≡10b （mod 5）

③6a ≡6b （mod 10） ④10a ≡10b （mod 20）

解：①因3a ≡3b （mod 5），所以5 | 3（a －b ），而5 | 3 ，

因此5 | a －b ，故a ≡b （mod 5）

②由10a ≡10b （mod 5）可以得到5 | 10（a －b ），而5 | 10，因此5不一定整除a －b ，故a ≡b （mod 5）就成立

③由6a ≡6b （mod 10）可得10 | 6（a －b ），而10=2×5，6=2×3，因此5 | a －b ， 故a ≡b （mod 5）成立

④由10a ≡10b （mod 20）可得到20 | 10（a －b ），而20= 4×5，4 | 10，因此5 | (a －b )

故a ≡b （mod 5）不成立

综上所述，由3a ≡3b （mod 5）或6a ≡6b （mod 10）都可以得到a ≡b （mod 5）

说明：在①中，因为（3，5）=1，因此由5 | 3（a －b ）一定可以得到5 | a －b ，进而得到a ≡b （mod 5），一般地，如果（k ，m ）=1，ka ≡kb （mod m ），那么a ≡b （mod m ）

在③中，因（6，10）=2，因此由10| 6（a －b ）一定可以得到5 | a －b ，进而得a ≡b （mod 5），一般地，如果（k ，m ）= d ，ka ≡kb （mod m ），那么a ≡b )(mod d

m ．

例4．如果a ≡b （mod 12）且a ≡b （mod 8），那么以下同余式一定成立的是哪些？

①a ≡b （mod 4） ②a ≡b （mod 24） ③a ≡b （mod 20） ④a ≡b （mod 48） 解：正确的有①和②

①由题中的条件可得12 | a －b ，又因4 | 12，所以4 | a －b ，故a ≡b （mod 4）． ②因12 | a －b ，8| a －b ，所以a －b 是12和8的公倍数，又因为[8，12]=24，因此 a －b 必是24的倍数，即24 | a －b ，故a ≡b （mod 24）．

③显然，当a = 26，b = 2时满足条件a ≡b （mod 12）和a ≡b （mod 8），但却不满足 a ≡b （mod 20）．

④同③，用a = 26，b = 2验证即可．

【说明】：

⑴一般地，若a ≡b （mod m ）且n | m ，那么a ≡b （mod n ）

⑵若a ≡b （mod m ），a ≡b （mod n ），那么a ≡b （mod [m ，n ]），它的一个特殊情况就是：

如果a ≡b （mod m ），a ≡b （mod n ）且（m ，n ）=1，那么a ≡b （mod m n ）

【一些结论】

1.同余定义的等价形式

①a ≡b （mod m ）⇔m | a －b

②a ≡b （mod m ）⇔a = b +mt

2．同余式的同加、同乘性