第二章同余 §2.1同余的定义和基本性质 定义1给定一个正整数m,如果m|(a-b),则称整数a,b 对模m同余,记作a≡b(modm);如果mk(a-b),则称整 数a,b对模m不同余,记作a≠b(modm)。 从定义可以看出,任意的两个整数a,b,要么a≡b(modm), 要么a≠b(modm)。结合整除的性质,我们很容易得到同余 的两个等价定义 (1)整数a,b对模m同余的充要条件是存在一个整数k使得 a=6+km (2)整数a,b对模m同余的充要条件是用m去除整数a和b 所得的最小非负余数相同 在同余式a≡b(modm)中,若0≤b<m,则称b是a对 模m的最小非负剩余,一般用b= amod n来表示;若 l≤b≤m,则称b是a对模m的最小正剩余;若 m/2<b≤m/2(或-m/2≤b<m/2),0≤b<m,则称 b是a对模m的绝对值最小剩余 从关系的角度出发,我们很容易证明同余是一种等价关系, 即同余满足如下性质: 性质1(1)自反性:a≡a(modm); (2)对称性:a= b(mod m)分b≡a(modm); (3)传递性:
第二章 同余 §2.1 同余的定义和基本性质 定义 1 给定一个正整数 m ，如果 m | (a − b) ，则称整数 a,b 对模 m 同余，记作 a b(modm) ；如果 m | (a − b) ，则称整 数 a,b 对模 m 不同余，记作 a b(modm)。 从定义可以看出，任意的两个整数 a,b ，要么 a b(modm)， 要么 a b(modm) 。结合整除的性质，我们很容易得到同余 的两个等价定义： （1）整数 a,b 对模 m 同余的充要条件是存在一个整数 k 使得 a = b + km ； （2）整数 a,b 对模 m 同余的充要条件是用 m 去除整数 a 和 b 所得的最小非负余数相同。 在同余式 a b(modm) 中，若 0 b m ，则称 b 是 a 对 模 m 的最小非负剩余，一般用 b = amodm 来表示；若 1 b m ， 则 称 b 是 a 对 模 m 的 最 小 正 剩 余 ； 若 − m/ 2 b m/ 2(或− m/ 2 b m/ 2)，0 b m ，则称 b 是 a 对模 m 的绝对值最小剩余。 从关系的角度出发，我们很容易证明同余是一种等价关系， 即同余满足如下性质： 性质 1 （1）自反性： a a(mod m) ； （2）对称性： a b(modm) b a(modm) ； （3）传递性：
a= b(mod n),b≡c(modm)→a≡c(modm) 同余其实就是整除的一种符号表示,因此我们在第一章中了 解的整除的一些基本性质都可以用同余符号简单地表示 性质2(1)若a≡b(modm),a"(modn)=b,则 土C≡b±d(modm) ac= bd(mod m) 特别地,对于任意一个整数e,都有 a土e≡b±e(modm),ae≡be(modm); (2)若a≡b(modm),k>0,则 k≡bk( mod mk) (3)若a≡b(modm),d是a,b的公因数,则 (4)若a=b(modm),d|m,d>0,则 ≡b(mod) (5)若aC≡bc(modm),d是c,m的最大公因数,则 a≡b(mod ,进一步,若d=(c,m)=1,则 有a=b(mod (6)若a=b(modm),则a"≡b(modm),进一步 若P(x)=∑Cx是一个整系数多项式(即系数c 是整数,其中Cn≠0),则P(a)=P(b)modm)
a b(mod m),b c(mod m) a c(mod m)。 同余其实就是整除的一种符号表示，因此我们在第一章中了 解的整除的一些基本性质都可以用同余符号简单地表示。 性质 2 （1） 若 a b(modm)， 0 a (mod n) b m = ，则 a c b d(modm) ac bd(mod m) ， 特别地，对于任意一个整数 e ，都有 a e b e(modm)，ae be(mod m) ； （2）若 a b(modm)，k 0 ，则 ak bk(mod mk) ； （3）若 a b(modm)，d是a,b 的公因数，则 (mod ) d m d b d a ； （4）若 a b(modm)，d | m，d 0 ，则 a b(mod d) ； （5）若 ac bc(mod m)，d 是 c,m 的最大公因数，则 (mod ) d m a b ，进一步，若 d = (c,m) =1 ，则 有 a b(modm) ； （6）若 a b(modm) ，则 a b (mod m) n n ，进一步， 若 = = n k k k P x c x 0 ( ) 是一个整系数多项式（即系数 k c 是整数，其中 c n 0 ），则 P(a) P(b)(modm) ；
(7)同余式组a≡b(modm,),j=1,2,…,k同时成 立的充要条件是 a=b(modm,m2,…,m]) (8)(a b)modm=(amod m b mod m)mod m 利用上述关于同余的一些基本性质,我们可以得到检查因数 的两个方法: 例1证明:一个整数能被3或9整除的充要条件是它的十 进位数码的和能被3或9整除 证明:设a是一个正整数。把a写成十进位数的形式: a=a10”+a10″+…+a0≤a<10.i=0.1,n。 因为10≡1(mod3),所以a≡∑a(mod3),由此可知,3|a 当且仅当3|∑a,对于9的情形同理可证。如:a=5783214, ∑a,=5+7+8+3+2+1+4=30,3|30,930,所以3 是a的因数,9不是a的因数。 例2设 a=an1000+a1000″+…+an,0≤a<1000,i=0,1,…,n 证明:a能被7(或11,或13)整除的充要条件是7(或11, 或13)整除∑(-1)a。 证明:因为1001=7×11×13,即1000≡-1(mod7),所以 1000≡(-1)(mod7),即有
（7）同余式组 a b m j k j (mod ), =1,2, , 同时成 立的充要条件是 (mod[ , , , ]) a b m1 m2 mk ； （8） (a b)mod m = (amod mbmod m)mod m。 利用上述关于同余的一些基本性质，我们可以得到检查因数 的两个方法： 例 1 证明：一个整数能被 3 或 9 整除的充要条件是它的十 进位数码的和能被 3 或 9 整除。 证明：设 a 是一个正整数。把 a 写成十进位数的形式： a a a a ai i n n n n n 10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 因为 10 1(mod3) ，所以 (mod3) 0 = n i a ai ，由此可知， 3| a 当且仅当 = n i ai 0 3 | ，对于 9 的情形同理可证。如： a = 5783214， 5 7 8 3 2 1 4 30 0 = + + + + + + = = n i ai ，3 | 30,9 | 30 ，所以 3 是 a 的因数，9 不是 a 的因数。 例 2 设 a a a a ai i n n n n n 1000 1000 ,0 1000, 0,1, , 0 1 = + −1 − ++ = 证明： a 能被 7（或 11，或 13）整除的充要条件是 7（或 11， 或 13）整除 − = n i i i a 0 ( 1) 。 证明：因为 1001 = 71113 ，即 1000 −1(mod 7) ，所以 1000 ( 1) (mod 7) i i − ，即有
a=∑(-1)a(mod7),于是7|a当且仅当7∑(-1)a,对 于11、13的情形同理可证。 因为100≡l(md11),所以在判断一个整数是否被11整除 时用百进制更简单。 下面我们介绍一个很有名的称作弃九法的方法,它利用同余 的性质来验算整数计算结果是否错误。这个方法对于加、减、 乘都适用,为了简便,我们只给出普通乘法的证明。假设我 们由普通乘法运算求出整数a,b的乘积为c,并且设 a=a10"+a10″+…+a1,0≤a<10,i=0,1,…,m b=b10°+b10″+…+b0≤b<10,i=0,1…,n。 C=c10+c-10-+…+c0≤c.<10,i=0,1,…,l。 如果有 a心b≠∑cmod9) 则所计算的结果是错误的。 按照例1,a≡∑a(mod9) ∑b,(mod9) C≡∑c(mod9),由同余的性质当然可以得到 E)b=(0m9y,所以,若bmd9),则 1b≠C 例3设a=17891,b=253786,如果按照普通乘法计算 得到a,b的乘积是c=4540485226,那么按照上面的方法
− = n i i i a a 0 ( 1) (mod7) ，于是 7 | a 当且仅当 − = n i i i a 0 7 | ( 1) ，对 于 11、13 的情形同理可证。 因为 100 1(mod11) ，所以在判断一个整数是否被 11 整除 时用百进制更简单。 下面我们介绍一个很有名的称作弃九法的方法，它利用同余 的性质来验算整数计算结果是否错误。这个方法对于加、减、 乘都适用，为了简便，我们只给出普通乘法的证明。假设我 们由普通乘法运算求出整数 a,b 的乘积为 c ，并且设 a a a a ai i m m m m m 10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 b b b b b i n i n n n n 10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 c c c c c i l i l l l l10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 如果有 ( )( ) (mod 9) 0 0 0 = = = l k k n j j m i i a b c 则所计算的结果是错误的。 按照例 1 ， (mod9) 0 = m i a ai ， (mod9) 0 = n j b bj ， (mod9) 0 = l k k c c ，由同余的性质当然可以得到 ( )( ) (mod 9) 0 0 0 = = = l k k n j j m i i a b c ，所以，若 ab c(mod9) ，则 ab c。 例 3 设 a =17891，b = 253786 ，如果按照普通乘法计算 得到 a,b 的乘积是 c = 4540485226 ，那么按照上面的方法
a≡26(mod9),b≡3l(mod9),c≡40(mod9),但是 26·31≠40mod9),所以计算有误 从上面的证明我们可以看出这种方法有一个缺陷,当使用弃 九法时,得到的结果虽然是(a)b)=c(md9,也不 能完全肯定原计算是正确的。如在上面例子中,如果有人计 算出来的结果为4540485362,那么用弃九法得到 26.31=41md9),而并未检査出错误来,实际的乘积结果为 4540485326。 例42005年7月26日是星期二,问此天后第2天是星期 几? 解依题意,我们需要求2°mod7,即整数2模7的最小 非负剩余。 因为2mod7=1,所以 2 mod 7=(2%.2)mod7=((2)mod. 2 mod 7)mod7=2 因此,第2天是星期四 现在我们利用同余的理论来计算某一特定的日子是星 期几。例如,香港回归日1997年7月1日是星期几,或者 中华人民共和国成立日是星期几?如果一年的天数可被7整 除,那么所有的日期在每一年中总有相同的星期数,这样日 历的编制将大大简化。但是,目前一年的天数是 365≡1(mod7),而闰年的天数是366≡2mod7),这表明, 在平年一个给定日期的星期数在下一年要加1,碰到闰年这
a 26(mod9) ， b 31(mod9) ， c 40(mod9) ，但是 26 31 40(mod9) ，所以计算有误。 从上面的证明我们可以看出这种方法有一个缺陷，当使用弃 九法时，得到的结果虽然是 ( )( ) (mod 9) 0 0 0 = = = l k k n j j m i i a b c ，也不 能完全肯定原计算是正确的。如在上面例子中，如果有人计 算 出 来 的 结 果 为 4540485362 ， 那 么 用 弃 九 法 得 到 26 31 41(mod 9) ，而并未检查出错误来，实际的乘积结果为 4540485326。 例4 2005 年 7 月 26 日是星期二，问此天后第 1000 2 天是星期 几？ 解 依题意，我们需要求 2 mod 7 1000 ，即整数 1000 2 模 7 的最小 非负剩余。 因为 2 mod 7 1 3 = ，所以 2 mod 7 (2 2)mod 7 ((2 ) mod 7 2mod 7)mod 7 2 1000 999 3 333 = = = 因此，第 1000 2 天是星期四。 现在我们利用同余的理论来计算某一特定的日子是星 期几。例如，香港回归日 1997 年 7 月 1 日是星期几，或者 中华人民共和国成立日是星期几？如果一年的天数可被 7 整 除，那么所有的日期在每一年中总有相同的星期数，这样日 历 的 编 制 将 大 大 简 化 。 但 是 ， 目 前 一 年 的 天 数 是 365 1(mod7) ，而闰年的天数是 366 2(mod 7) ，这表明， 在平年一个给定日期的星期数在下一年要加 1，碰到闰年这