【初中竞赛资料】初中数学同余式.pdf

【初中竞赛资料】初中数学同余式

同余式

数论有它自己的代数,称为同余理论．最先引进同余的概念与记号的

是数学王子高斯．

先看一个游戏：有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(modm),

并读作a同余b,模m．

若a与b对模m同余,由定义1,有

a=mq＋r,b=mq+r．

12

所以a-b=m(q-q),

12

即m｜a-b．

反之,若m｜a-b,设

a=mq＋r,b=mq＋r,0≤r,r≤m-1,

112212

则有m｜r-r．因｜r-r｜≤m-1,故r-r=0,即r＝r．

12121212

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

定义2若a与b是两个整数,并且它们的差a-b能被一正整数m整除,那

么,就称a与b对模m同余．

同余式的写法,使我们联想起等式．其实同余式和代数等式有一些相同的

性质,最简单的就是下面的定理1．

第1页共8页

【初中竞赛资料】初中数学同余式

定理1(1)a≡a(modm)．

(2)若a≡b(modm),则b≡a(modm)．

(3)若a≡b(modm),b≡c(modm),则a≡c(modm)．

在代数中,等式可以相加、相减和相乘,同样的规则对同余式也成

立．

定理2若a≡b(modm),c≡d(modm),则

a±c≡b±d(modm),ac≡bd(modm)．

证由假设得m｜a-b,m｜c-d,所以

m｜(a±c)-(b±d),m｜c(a-b)＋b(c-d),

即

a±c≡b±d(modm),ac≡bd(modm)．

由此我们还可以得到：若a≡b(modm),k是整数,n是自然数,则

a±k≡b±k(modm),

nn

ak≡bk(modm),a≡b(modm)．

对于同余式ac≡bc(modm),我们是否能约去公约数c,得到一个正确的同

余式a≡b(modm)?

在这个问题上,同余式与等式是不同的．例如

25≡5(mod10),

约去5得

5≡1(mod10)．

这显然是不正确的．但下面这种情形,相约是可以的．

定