第一节 同余

初等数论 第二章 同 余

同余的概念是高斯（Gauss）在1800年左右给出的.同余是数论中的一个基本概念。本章除介绍同余的基础知识外，还要介绍它的一些应用。

第一节 同余的基本性质与应用(一)

定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a

与b同余，模m，记为

a ? b (mod m)，

此时也称b是a对模m的同余。

如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为a??b (mod m)。

定理1 下面的三个叙述是等价的：

(ⅰ) a ? b (mod m)；

(ⅱ) 存在整数q，使得a = b ? qm；即a?b?mq，亦即m|(a?b)

(ⅲ) 存在整数q1，q2，使得a = q1m ? r，b = q2m ? r，0 ? r < m。 证明 留作习题。

定理2 同余具有下面的性质：

(1) （反身性） a ? a (mod m)；

(2) （对称性） a ? b (mod m) ? b ? a (mod m)； (3) （传递性） a ? b，b ? c (mod m) ? a ? c (mod m)

定理3 设a，b，c，d是整数，并且a ? b (mod m)，c ? d (mod m)， (1)

则

(4) （同余式相加） a ? c ? b ? d (mod m)； (5) （同余式相乘）ac ? bd (mod m)。 【证明】 (4) 由式(1)及定义1可知

m?a ? b，m?c ? d，

因此

m?(a ? c) ? (b ? d)，

此即结论(ⅰ)；

(5) 由式(1)及定理1可知，存在整数q1与q2使得

a = b ? q1m，c = d ? q2m，

因此ac = bd ? (q1q2m ? q1d ? q2b)m， 再利用定理1，推出结论(ⅱ)。证毕。

定理4 设ai，bi（0 ? i ? n）以及x，y都是整数，并且 x ? y (mod m)，ai ? bi (mod m)，0 ? i ? n，

则?aixi??biyi(mod m)。 (2)

i?0i?0nn 1

证明 留作习题。 定理5 下面的结论成立：

(6) 若ac ? bc (mod m)，则ac?bc(modm) ； (m,c)由此推出若(c, m) = 1 ? a ? b (mod m)（即在c,m互素时，可在原同余式两边

约去c而不改变模，这里再次表明互素的重要性） 【证明】 由ac ? bc (mod m)

得到m│c(a ? b)，再由(c, m) = 1和第一章第三节定理4得到m│a ? b，即

a ? b (mod m)。证毕。

(7) a ? b (mod m)，d?m，d > 0 ? a ? b (mod d)； (8) a ? b (mod m)，k > 0，k?N ? ak ? bk (mod mk)； (9) a ? b (mod mi )，1 ? i ? k ? a ? b (mod [m1, m2, ?, mk])； (10) a ? b (mod m) ? (a, m) = (b, m)； 二、例题分析

1.说明22?1是否被641整除．

【解答】依次计算同余式

22 ? 4，24 ? 16，28 ? 256，216 ? 154，232 ? ?1 (mod 641)

因此22?1 ? 0 (mod 641)，即641?22?1．

注：一般地，计算ab (mod m)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化． 2.今天是星期天，再过2003【解答】200320032003555天是星期几？

?(7?286?1)2003?12003(mod7)

2003 故再过2003天是星期一.

2015 变式.今天是星期天，再过2015 【解答】20152015天是星期几？

?(7?287?6)2015?62015(mod7)

?(7?1)2015(mod7)2015?(?1)(mod7)??1(mod7)

故再过20152015天是星期六.

3.设p是素数，a是整数，则由a2 ? 1(mod p)可以推出

a ? 1或a ? ?1 (mod p)。

解 由a2 ? 1 (mod p) ? p?a2 ? 1 = (a ? 1)(a ? 1)，

所以必是p?a ? 1或p?a ? 1，即a ? ?1 (mod p)或a ?1 (mod p)。

n4.确定所有的自然数n使得2?1能被7整除.

2

【解答】就是要找出所有的自然数n，使得2n?1(mod7) 由于28?1(mod7)

故23m?1(mod7)，23m?1?2(mod7)，23m?2?4(mod7)

又知自然数均可表示为3m,3m?1,3m?2的形式之一，故符合条件的n?3m,m?N? 5 求(25733 ? 46)26被50除的余数. 【解答】利用定理4有

(25733 ? 46)26 ? (733 ? 4)26 = [7?(72)16 ? 4]26

? [7?( ?1)16 ? 4]26 = (7 ? 4)26

? 326 = 3?(35)5 ? 3?(?7)5 = ?3?7?(72)2

? ?21 ? 29 (mod 50)，即所求的余数是29． 6. 求n =7的个位数字．

【解答】 我们有71 ? ?3，72 ? ?1，74 ?1 (mod 10)，因此，若77 ? r (mod 4)，

r7

则n =7? 7 (mod 10)。 (3)

7

77

现在7 ? (?1)7 ? ?1 ? 3 (mod 4)，所以由式(3)得到

n =77? 73 ? (?3)3 ? ?7 ? 3 (mod 10)，

即n的个位数是3．

注：一般地，若求ab对模m的同余，可分以下步骤进行： (ⅰ) 求出整数k，使ak ? 1 (mod m)；

(ⅱ) 求出正整数r，r < k，使得b ? r (mod k)； (ⅲ) ab? a r (mod m)。

7.设N =anan?1?a0是整数N的十进制表示，即

N = an10n ? an ? 110n ? 1 ? ? ? a110 ? a0 ，

则 (ⅰ) 3│N ? 3|?ai；

i?0nncc7

7c(ⅱ) 9│N ? 9|?ai；

i?0(ⅲ) 11│N ? 11|?(?1)iai；

i?0n(ⅳ) 13│N ? 13│a2a1a0?a5a4a3?? 【证明】

3

(ⅰ) 由100 ? 1，101 ? 1，102 ? 1，? (mod 3)及式(2)可知N =?ai10i??ai(mod 3)，

i?0i?0nn由上式可得到结论(ⅰ)。结论(ⅱ)，

(ⅲ)100 ? 1，101 ? ?1，102 ?1，103 ? ?1，? (mod 11)

所以N =

nn?a10??(?1)a(mod 11)，

iiiii?0i?0(ⅳ)只需利用式(2)及100?1,101??3,102??4,103??1,104?3,104?4,???mod(13) 和N =an?1an?2?a1a0?a2a1a0?100?a5a4a3?103?? 。 【注】

一般地，在考虑使N =an?1an?2?a1a0被m除的余数时，首先是求出正整数k，使 得10k ? ?1或1 (mod m)，

再将N =an?1an?2?a1a0写成N =ak?1ak?2?a1a0?100?a2k?1a2h?2?ak?10k?? 的形式，再利用式(2)。

8.设n的十进制表示是13xy45z，若792?n，求x，y，z

解 因为792 = 8?9?11，故

792?n ? 8?n，9?n及11?n。

及n= an10n ? an ? 110n ? 1 ? ? ? a110 ? a0 ，10?(8?2)?8M?2

我们有8?n ? 8?45z? z = 6，（8要整除后三位）

以及9?n ? 9?1 ? 3 ? x ? y ? 4 ? 5 ? z = 19 ? x ? y ? 9?x ? y ? 1， (5) 11?n ? 11?z ? 5 ? 4 ? y ? x ? 3 ? 1 = 3 ? y ? x ? 11?3 ? y ? x。 (6) 由于0 ? x, y ? 9，所以由式(5)与式(6)分别得出

x ? y ? 1 = 9或18， 3 ? y ? x = 0或11。

这样得到四个方程组：

?x?y?1?a， ?3?y?x?b?kkk其中a取值9或18，b取值0或11。在0 ? x, y ? 9的条件下解这四个方程组，得到x = 8，

y = 0，z = 6。

9.求N =an?1an?2?a1a0被7整除的条件，并说明1123456789能否被7整除。

【解答】10?1,10?3,10?2,10??1,10??3,???mod(7) N = an10n ? an ? 110n ? 1 ? ? ? a110 ? a0 ，

因此

01234 4

N?an?1an?2?a1a0?a2a1a0?100?a5a4a3?103???a2a1a0?a5a4a3?a8a7a6??(mod7)，即7?N ? 7?a2a1a0?a5a4a3?a8a7a6??。 由于789 ? 456 ? 123 ? 1 = 455，7?455， 所以7?1123456789.

|a，n是正整数，则a2? 1 (mod 2n + 2)。 (4) 10. 证明：若2?【证明】【我们运用数学归纳法】

设a = 2k ? 1，当n = 1时，有

a2 = (2k ? 1)2 = 4k(k ? 1) ? 1 ? 1 (mod 23)，

即式(4)成立。

假设式(4)对于n = k成立，则有

a2? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，

kkn其中q?Z，所以

a2k?1= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)，

其中q ?是某个整数。这说明式(4)当n = k ? 1也成立。 由归纳法知式(4)对所有正整数n成立.

11. 设素数p满足p?7(mod8)，证明:p必不能表作三个平方数之和. 【分析】 我们利用平方数模8的性质进行处理

【证明】设存在三个整数a,b,c使p?a?b?c.其中a,b,c或为偶数，或为奇数。

2228因此下式aa2??00(mod(mod8),a2?1(mod8),a2?4(mod8),必居其一.

2事实上，当a是奇数a?4m?1或a?4m?3时，有a?1(mod8),

22 当a是偶数a?4m或a?4m?2时，有a?0(mod8),或a?4(mod8);

2同样b和c也必居下式之一：

b?0(mod8),b?1(mod8),b?4(mod8), c?0(mod8),c?1(mod8),c(mod8), c2??44(mod8将a,b,c所有可能满足的式子任意组合，只能得到a?b?c?0,1,2,3,4,5,6(mod8),而得

222不到a?b?c?7(mod8).因此形如p?7(mod8)的素数不能表作三个平方数之和。

222222222【评注】 选择合适的模是处理平方数问题的技巧之一 12.（2004年韩国数学竞赛）

5

本文来源：https://www.bwwdw.com/article/egg7.html