第7讲 同余的概念及基本性质
数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯.
先看一个游戏：有n+1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子,每步可前移1，2或3格,以先到最后一格者为胜.问是先走者胜还是后走者胜？应该怎样走才能取胜？
取胜之道是：你只要设法使余下的空格数是4的倍数,以后你的对手若走i格（ｉ=1，２,3),你走4-i格,即每一次交替,共走了4格．最后只剩4个空格时,你的对手就必输无疑了．因此，若n除以４的余数是1，2或３时,那么先走者甲胜;若ｎ除以4的余数是0的话，那么后走者乙胜.
在这个游戏里，我们可以看出,有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么．又例如,1999年元旦是星期五,1999年有365天,3６5＝７×5２＋1，所以2０00年的元旦是星期六.这里我们关心的也是余数．这一讲中,我们将介绍同余的概念、性质及一些简单的应用.
同余，顾名思义,就是余数相同．
一、基础知识
定义1 给定一个正整数ｍ,如果用m去除ａ，ｂ所得的余数相同,则称a与b对模ｍ同余,记作
a≡b(ｍｏdｍ），
并读作a同余b,模m.
否则,就称a与b对于模m不同余，记作ａ≡b（ｍod m),
根据定义,ａ与ｂ是否同余，不仅与a、b有关,还与模m有关,同一对数a和b,对于模ｍ同余,而对于模ｎ也许就不同余,例如,5≡8（moｄ 3),而5≡８（mｏｄ 4),
若a与b对模m同余,由定义１,有
a=mq１＋r，ｂ＝mｑ2+ｒ.
所以 ａ－b＝m(q１-q2)，
即 m|a-b.
反之，若m｜a-ｂ，设
ａ=mq1+r1，b＝mq2＋ｒ2，0≤r1,r2≤m-1,
则有m|r1-r2.因｜r1-r2|≤ｍ-1,故r1－r２=0，即r1＝r2.
于是，我们得到同余的另一个等价定义：
定义2 若a与ｂ是两个整数,并且它们的差a-b能被一正整数m整除,那么，就称a与b对模m同余.
另外，根据同余的定义,显然有以下几种关系是成立的:
⑴a≡ａ(mod ｎ)
⑵a≡ｂ(moｄ m）b≡a（mod ｎ)
⑶a≡ｂ（mod n)
b≡c（moｄ ｍ)
由此可见,同余是一种等价关系，以上这三条分别叫做同余的反射性，对称性和传递性,而等式也具有这几条性质．
二、典型例题；
例1.如果a≡b（ｍｏd m),以下命题正确的有哪些?请说明理由?
⑴ｍ | a-b
⑵ａ = b＋mt
⑶ａ ＝ k1m+ ｒ1,b = k2ｍ+ r2(0≤ｒ1,r2＜m)r１= ｒ２
解:⑴因a≡b（moｄ ｍ）,所以可得a = ｋ1m＋ r，b = ｋ２m+ r，那么ａ－ｂ=(k1－k2)m，由于k1－ｋ2是整数,因此ｍ ｜ a－b是正确的．
⑵根据⑴可得a－b= ｍt，即a= b+ｍt
⑶根据⑴可得，ｍ ｜ r1-r2,又因为0≤| ｒ1-r2 |＜ｍ，所以| ｒ1－r2 |=０，故r1= ｒ2．
例２.判断正误，并说明理由.
⑴如果a≡b(mｏd m）那么ka≡ kb（ｍod m)
⑵如果a≡b（mod ｍ），c是整数，那么ａ±c≡b±ｃ (mod m)
⑶如果a1≡ｂ１（ｍod m)，a2≡b2(mod m)，那么ａ1±a2≡b１±b2 (mｏｄ m),
a１a2≡b1b2 (mod m）.
⑷如果3a≡3ｂ(mod 6 ),那么a≡b (ｍod 6 )
解：⑴∵a≡b（moｄ m），∴m | a－b，∴m ｜ k (a-b)即ｍ ｜ (ka－kb)
∴ｋa≡kb（mｏd m) ⑴ 成正确
⑵∵a≡ｂ（ｍod m)，∴m | a－b
又因为c是整数,所以ｍ | a-c－b＋c,即m | (ａ－c) －（b-c)即a－ｃ≡b-c(mod m）
同理可得,ａ+c≡b+ｃ（mod m)
⑶仿照上面的两个小题的方汪，可以判定这个命题也是正确的
⑷显然６≡１2(ｍod 6)，而２≡ ４ （ｍod 6),因此，这个命题不正确
说明：⑶的结论可以得到同余的另一条性质，即a≡ｂ（mod m)an≡bn（mod ｍ)
此题说明两个同余式能够象等式一样进行加、减、乘、乘方,但同余式两边却不能除以同一数,那么,同余式的两边在什么情况下可以同除以一个数呢？我们先看下面的例题．
例3.由下面的哪些同余式可以得到同余式a≡b（moｄ ５）
①3a≡3b（moｄ 5） ②10a≡10b(ｍｏd 5）
③6ａ≡６ｂ（mod １0） ④10a≡10b(ｍod 20)
解：①因3a≡3b(mod ５），所以5 | ３(a-ｂ),而5 | ３ ,
因此5 ｜ ａ－ｂ,故a≡ｂ（mod 5）
②由１０ａ≡10b（moｄ 5)可以得到5 | 10(a－b)，而5 ｜ 10，因此5不一定整除a-b,故a
≡b(mod 5）就成立
③由６ａ≡6b(mod 1０)可得10 | ６（a－b），而10=2×5，6=２×3，因此5 | a－b,
故ａ≡ｂ(mｏd ５）成立
④由10a≡10b(moｄ ２０)可得到20 | １0(ａ-b),而2０＝ 4×5,４ | 10，因此5 | (ａ－b)
故ａ≡b(mod ５)不成立
综上所述,由3a≡3b(mｏd 5)或６a≡６b（mod 1０）都可以得到a≡b（ｍｏd 5）
说明:在①中，因为(３,５)＝1，因此由5 | 3(a－b)一定可以得到5 ｜ ａ－b，进而得到a≡b（mod 5)，一般地，如果(k,ｍ）=1,ka≡kb（moｄ ｍ）,那么ａ≡b（mod m）
在③中，因（6，10）=2，因此由10| 6(ａ-ｂ）一定可以得到5 | a-b，进而得a≡ｂ（moｄ 5)，一般地，如果（k，m）= d，ka≡kb（ｍｏd m）,那么a≡b.
例4．如果a≡ｂ（mod １２）且a≡b（ｍod 8)，那么以下同余式一定成立的是哪些？
①a≡ｂ（mod 4) ②a≡ｂ(mod 24) ③a≡ｂ（mｏd 2０） ④ａ≡b（mｏｄ ４8）
解:正确的有①和②
①由题中的条件可得１2 | a-ｂ,又因4 | 12，所以4 | a－b,故a≡b(mod 4).
②因1２ ｜ a-b，8| a－b,所以a－b是12和８的公倍数，又因为［8,1２]=24,因此
a-b必是24的倍数，即２4 | a－b，故a≡b（mod 24).
③显然,当ａ= 26,ｂ = ２时满足条件a≡b(mod 12）和a≡b(moｄ ８），但却不满足
ａ≡b（ｍｏd 20).
④同③，用a = 26，b = 2验证即可.
【说明】:
⑴一般地，若a≡b(mod m）且n | m，那么ａ≡b（moｄ ｎ)
⑵若a≡b（mｏd m），a≡b(mod n）,那么a≡b(mod [m,n]),它的一个特殊情况就是:
如果a≡b（ｍｏd m），a≡b（moｄ n）且（m，n）＝1，那么a≡b（mod ｍ n)
【一些结论】
1.同余定义的等价形式
①a≡ｂ(ｍod m）ｍ ｜ ａ-b
②a≡b(mod m）ａ = ｂ+mt
2．同余式的同加、同乘性
如果a１≡ｂ１(mｏd m）,a２≡b2（mod m)那么
⑴a1±a2≡b1±b２（mod ｍ)
⑵ka1≡kb1(mod ｍ)(k∈Z)
⑶a1a2≡b１b2（mｏd ｍ）
⑷a1n≡b1n（mｏd ｍ）（ｎ是整数)．
３．如果（k，m）=d,ka≡ｋb(mod m）,那么a≡b．
这条性质的直接推论就是：
如果(k,ｍ）=1，kａ≡kb(ｍod m）,那么a≡b(moｄ m）
4.如果a≡b（moｄ m)且n | m，那么a≡ｂ(mod n）
５．如果ａ≡b(mｏd ｍ)，ａ≡b（moｄ ｎ）,那么a≡b（mod [ｍ,n])
这条性质的一个推论就是：
如果a≡ｂ(mｏd m），ａ≡b(mｏd n)且(m,n）=１，那么a≡b(mｏd ｍ n)
例5．⑴求19992002除以9的余数;⑵求1010除以7的余数
解：⑴∵9 ｜ 1999－10０0,∴1999≡１０00≡1（ｍod 9)
∴1９９92000≡１２０02≡１（mod 9）,∴19992００0除以9的余数是1
⑵∵10≡3（ｍod 7),∴１0３≡3３≡－1（mod 7)
∴１06≡(-1）2≡１(mｏｄ ７），∴1０10≡10４(ｍod 7）
又∵102≡9≡2（mod 7),∴１０2≡１0 4≡22≡４(mod 7）
所以1010除以７的余数是4．
说明:求较大数的余数时,可先设法找到与±1同余的数,然后利用同余式的性质，求出所求数的余数.
例6．求1４5８9+３2００2除以13的余数．
解：∵145≡2(mod 13），∴1４５6≡26≡－１(mod 13)
∴（1456)14≡(－１)１4≡1(mod 1３)即14584≡1(ｍｏd 1３)
又∵145５≡２5≡6（ｍod 13）
所以1458９≡1４584·１４55≡6×１≡6（mod 13）
又∵３3≡1(mod １3)，∴(３3)66７≡32０0１≡1(ｍoｄ 1３)，∴3２0０2≡3（mod 13）
所以，14589+32002≡6+3≡9(mod 13）
即14５8９+32０02除以13的余数是9
例７.求1998２0０2的十位数字
分析：此题可以通过１998２00２的末两位数来求解，与前面的方法类似
解：∵199８98≡-２（mｏd 100),∴１99８２0０2≡（-2)２002≡22002≡41001(ｍｏd 100)
因为４≡4(mｏd 1０0)，42≡16（mｏd 100)，4３≡6４(mｏd １０0)，44≡５6(ｍod 100），４5≡24（mｏd 10０）,４6≡96(mod 10０）,47≡８4（ｍod １00)，４8≡36(mod 100）,
49≡44（moｄ 100),41０≡7６(mｏd 10０)，４１1≡4(mod １0０）…
👁️ 阅读量：0
© 版权声明：本文《初中数学竞赛讲座——数论部分7(同余)》内容均为本站精心整理或网友自愿分享，如需转载请注明原文出处：https://www.zastudy.cn/jiangzuo/1686217027a208303.html。