第一节 同余

1 初等数论 第二章 同 余

同余的概念是高斯（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；即mqba，亦即)(|bam

(ⅲ) 存在整数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，

则niiiniiiybxa00(mod m)。 (2) 2 证明 留作习题。

定理5 下面的结论成立：

(6) 若ac  bc (mod m)，则(mod)(,)macbcmc ；

由此推出若(c, m) = 1  a  b (mod m)（即在,cm互素时，可在原同余式两边约去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.说明1252是否被641整除．

【解答】依次计算同余式

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

因此1252  0 (mod 641)，即6411252．

注：一般地，计算ab (mod m)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化．

2.今天是星期天，再过20032003天是星期几？

【解答】)7(mod1)12867(2003200320032003

故再过20032003天是星期一.

变式.今天是星期天，再过20152015天是星期几？

【解答】)7(mod6)62877(2015201520152015

)7(mod1)7(mod)1()7(mod)17(20152015

故再过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)。

4.确定所有的自然数n使得12n能被7整除. 3 【解答】就是要找出所有的自然数n，使得)7(mod12n

由于)7(mod128

故)7(mod123m，)7(mod2213m，)7(mod4223m

又知自然数均可表示为23,13,3mmm的形式之一，故符合条件的Nmmn,3

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 =777的个位数字．

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

则n =777 r7 (mod 10)。 (3)

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

n =777 73  (3)3  7  3 (mod 10)，

即n的个位数是3．

注：一般地，若求cba对模m的同余，可分以下步骤进行：

(ⅰ) 求出整数k，使ak  1 (mod m)；

(ⅱ) 求出正整数r，r < k，使得cb  r (mod k)；

(ⅲ) cba a r (mod m)。

7.设N =01aaann是整数N的十进制表示，即

N = an10n  an  110n  1    a110  a0 ，

则 (ⅰ) 3│N  3niia0|；

(ⅱ) 9│N  9niia0|；

(ⅲ) 11│N  11niiia0)1(|；

(ⅳ) 13│N  13│345012aaaaaa

【证明】 4 (ⅰ) 由100  1，101  1，102  1， (mod 3)及式(2)可知N =niiniiiaa0010(mod 3)，

由上式可得到结论(ⅰ)。结论(ⅱ)，

(ⅲ)100  1，101  1，102 1，103  1， (mod 11)

所以N =niiiniiiaa00)1(10(mod 11)，

(ⅳ)只需利用式(2)及)13mod(,410,310,110,410,310,110443210

和N =3345001201211010aaaaaaaaaann 。

【注】

一般地，在考虑使N =0121aaaann被m除的余数时，首先是求出正整数k，使

得10k  1或1 (mod m)，

再将N =0121aaaann写成N =kkhkkkaaaaaaa1010221200121

的形式，再利用式(2)。

8.设n的十进制表示是zxy4513，若792n，求x，y，z

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

792n  8n，9n及11n。

及n= an10n  an  110n  1    a110  a0 ，kkkM28)28(10

我们有8n  8z45  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。

这样得到四个方程组：

bxyayx31，

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

9.求N =0121aaaann被7整除的条件，并说明1123456789能否被7整除。

【解答】)7mod(,310,110,210,310,11043210

N = an10n  an  110n  1    a110  a0 ，

因此 5 ，)7(mod1010678345012334500120121aaaaaaaaaaaaaaaaaaaNnn

即7N  7678345012aaaaaaaaa。

由于789  456  123  1 = 455，7455，

所以71123456789.

10. 证明：若2|a，n是正整数，则na2 1 (mod 2n + 2)。 (4)

【证明】【我们运用数学归纳法】

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

a2 = (2k  1)2 = 4k(k  1)  1  1 (mod 23)，

即式(4)成立。

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

ka2 1 (mod 2k + 2) ka2= 1  q2k + 2，

其中qZ，所以

12ka= (1  q2k + 2)2 = 1  q 2k + 3  1 (mod 2k + 3)，

其中q 是某个整数。这说明式(4)当n = k  1也成立。

由归纳法知式(4)对所有正整数n成立.

11. 设素数p满足)8(mod7p，证明:p必不能表作三个平方数之和.

【分析】 我们利用平方数模8的性质进行处理

【证明】设存在三个整数cba,,使.222cbap其中cba,,或为偶数，或为奇数。

因此下式8(mod02a),8(mod02a),8(mod12a),8(mod42a必居其一.

事实上，当a是奇数14ma或34ma时，有)8(mod12a,

当a是偶数ma4或24ma时，有),8(mod02a或);8(mod42a