同余的-概念与性质

第三章

同余与同余式

第一部分同余概念与性质§3.1

同余的概念§3.2

同余的性质§3.3同余的应用第三章同余与同余式

在日常生活中,有时我们注意的常常不是某些整数,而是这些整数用某一个固定的整数去除所得到的余数.例如本月2日是星期3,那么9日,16日,…都是星期3,这是因为它们用7除后得到的余数都是2.在我国古代的干支纪年也是这样的,它是以60作为除数的纪年法.这样,在数学中就产生了同余的概念.同余概念是Gauss在1800年前后创立的.§3.1同余的概念定义假定两个整数a,b对于正整数m，有a＝mq1+r1,(0≤r1<m)，b＝mq2+r2，(0≤r2<m)，并且r1＝r2,那么我们就称a与b对(关)于模m同余,用符号表示为

a

≡b(modm)或a

≡b(m).假定上面的r1≠r2,我们就说两个整数a与b关于模m不同余,用符号a

≡b(modm)或a

≡b(m)表示.

例如,31≡9(mod11),31≡9(mod10).由上例可知，同样的两个数关于不同的模同余关系可能不相同．例3.2

求证：(1)如果a除以m的余数为r(0≤r<m),那么a≡r(modm);

(2)如果a≡r(modm)，0≤r<m，那么a除以m的余数为r。

证明(1)由题意得可设，a＝mq+r

(0≤r<m)．由于0≤r<m，所以r除以m的不完全商为0，余数为r，即r＝m·０+r

(0≤r<m)．根据同余概念，可得a≡r(modm);(2)因为a≡

r(modm)，所以由同余概念可得·

a＝mq1+R

,

r＝mq2+R，(0≤R<m)，又因为０≤r<m，所以q2＝0，即R＝r.因此得

a＝mq1+r(0≤r<m)．即a被m除，所得的余数为r．a的对于模m的最小非负剩余注意：例3．2(1)的结果说明每一整数a恰与0，1，…，m－1中的一个数对于模m同余．通常称余数r(0≤r<m)为a的对于模m的最小非负剩余．而0，1，…，m－1则称为模m的最小非负剩余系．例3．2(2)的结果是我们以后利用同余知识解决求余数问题的依据．

例3．3

求证；如果a

≡b(modm)，那么a+km≡b(modm)，这里k为整数．证明：由a

≡b(modm)，得a＝mq1+r

，

b＝mq2+r，(0≤r<m)，∴a+km

＝mq1+r+km＝m(q1+k)+r

，∴a+km≡b

(modm)。两个整数同余的充分必要条件定理3.1

两个整数a,b对于模m同余的必要且充分条件是这两个数的差a－b

能够被正整数m整除,即a

≡b(modm)

m|(a－b)。证明：∵

a

≡b(modm)∴

a＝mq1+r

，

b＝mq2+r，(0≤r<m)，∴a－b＝mq1+r

－（mq2+r）＝m(q1－q2)，从而由整除的定义得m|(a－b)。

设a＝mq1+r1,(0≤r1<m),b＝mq2+r2

,(0≤r2<m)，则a－b＝m(q1－q2)+(r1－r2)，

因为m|(a－b).所以m|(r1－

r2)，而0≤r1<m，0≤r2<m故|r1－r2|<m,又因为|r1－r2|≥0，所以只有r1－r2

＝0，即r1＝r2所以a

≡b(modm)

推论

推论1如果m|(a－b)，那么a

≡b(modm)

推论2

a

≡b(modm)的必要且充分条件是存在整数k，使得a

＝

b+km(modm)．(这里是等号不是同余号)定理3.1及推论2都是同余的必要且充分条件，因此也可以把它们作为同余的定义:

如果a－b

能被m整除，我们就说a与b对于模m同余．同余的这个定义与前一个定义是等价的，也就是说，既能从前面一个定义推出这个定义，也能从这个定义推出前一个定义(读者可自行证明)．今后讨论与同余定义有关的问题时，灵活选用其中一个，可以使讨论简便．例3.4用同余式表示下面的说法：

(1)45，94被7除，余数都是3;(2)数a与15之差能被17整除;例3.5求证：若a≡b(modm)，则a≡b+km

(modm)，这里k为任意整数．证明:因为a≡b(modm)，所以m|(a－b)，因此m|[(a－b)－km]，即m|[a－

(b＋km)]，所以a≡b

+km(modm)．

(3)171＝15+13X12;(4)数b被15除余4．例3．3与例3．5的启示在同余式的左右两边中，把一个数换成与这个数同余的数(a换成a+km,b换成b+km),同余式仍成立.例3．3与例3．5的比较:

⑴a+km≡b

(modm)并非理所当然地就有b≡a

+km(modm),仅当关系满足自反律时才能成立.⑵前者根据同余的定义证明的,而后者是应用定理3.1证明的.也就是说,在同余式的左边或右边,可以加上模的任意整数倍km,就象加零一样,即它与等式性质”在等式的左边或右边加上零,等式不变”是类似的.§3.2

同余的性质

1.同余的基本性质:在数学中,具有自反律,

对称律,

传递律的关系称之为等价关系.同余关系就是一种等价关系.也就是说,由同余的定义可以得到证明先证自反律,∵m|(a－a),∴a

≡a(modm).我们再证明传递律.由题可知m|(a－b),m|(b－c),所以由同余的定义,得到m|[(a－b)＋(b－c)],因此m|(a－c),即a

≡c(modm)

.定理3.2

a

≡a(modm)(自反律).

定理3.3

若a

≡b(modm),则b

≡a(modm)(对称律).定理3.4如果a

≡b(modm),b

≡c(modm),那么a

≡c(modm)

(传递律).例3.6

求证若a≡b(modm)，则(a,m)=(b,m)．

证明因为a

≡b(modm)，所以m|(a－b)。即存在整数q，使得a＝mq+b

，设d1是a，m的公约数，则d1|a，d1|m，又因为b=a－mq，所以d1|b；再设d2是b，m的公约数，则d2|b，d2|m,因为a=mq+b，所以d2|a．因此，a，m的公约数集和b，m的公约数集相同，所以(a,m)=(b,m)．从例3．6的证明，还可以得出如下的结论：如果a

≡b(modm)，又d能整除m以及整除a，b两个数中的一个，则d必能整除a，b中的另一个．

例3.7

求证：如果a

≡b(modm),b=

c,c

≡d(modm),那么a

≡d(modm).证明因为a

≡b(modm)，所以m|(a－b)，又b＝c，因此m|(a－c)，所以a

≡c(modm)，又因为c≡d(modm)，由传递性，所以a≡

d(modm)．例3.7告诉我们，在讨论同余的时候，可以把等号混在同余中同时使用，即例3.7的结论可以写成a

≡b=

c

≡d(modm)P134习题3.1第1,4,5题作业

2.同余的运算性质:二个同模的同余式能够象等式一样进行加、减和乘等运算.定理3.5

设a

≡b(modm),c

≡d(modm),则

a＋c

≡b＋d

(modm),a－

c

≡b－

d(modm).证明:由题意,有m|(a－

b),

m|(

c－

d

),所以m|[(a－

b)±(

c－

d

)],即m|[(a±c)－

(

b±d

)],故a＋c

≡b＋d

(modm),a－

c

≡b－

d(modm)

.推论推论1

在同余式的两边同加上(或同减去)一个整数，同余式仍成立。即：若a＋b

≡c

(modm),则a＋b－

c

≡0

(modm),或a≡c－b(modm).推论3

定理3.5可以推广到有限个同余式的情况。推论2

在一个同余式中，一个项可以改变符号后移到同余式的另一边去，定理3.6

设a

≡b(modm),c

≡d(modm)，则ac

≡bd

(modm).推论推论1设a

≡b(modm),c是任意整数.

则ac

≡bc

(modm).推论3设a

≡b(modm),则ak

≡bk(modm),k是任意正整数.推论2设ai≡bi(modm)(i=1,2,…,n,n>2),则a1a2…an

≡b1b2…bn

(modm).例例1

试证明一个整数能被3整除的充分必要条件是它的10进位数码的和能被3整除.用与例1同样的证明方法,我们可以得到:一个整数能被9整除的必要充分条件是它的10进位数码的和能被9整除.因为10≡1(mod3),所以我们得到因此,我们知道当且仅当证明设a是一正整数,并将a写成10进位数的形式:例3.8

已知x+y≡7(mod5),x≡3(mod5)，求对于模5与y同余的整数．解因为x+y≡7(mod5)，x≡3(mod5)，由定理3.5得x+y－x≡7－3=4(mod5)，即y≡4(mod5)．因此对于模数5，与y同余的整数是4+5t(t为任意整数).

例3.9巳知x≡2(mod5)，

求证：2x2－x+3≡4(mod5)

证明因为x≡2(mod5)，所以x2≡22

≡4(mod5)，2x2≡8≡3

(

mod5)，而－x≡－2(mod5)，从例3．9可以看出，应用定理3.5的推论1与定理3.6的推论1与推论3，对同余式可以像等式那样进行代换.因此,2x2－x+3≡2×22－2＋3≡9≡4(mod5).§3.3同余概念、性质的应用利用同余定义与性质，可以解决小学数学中的某些较难的问题，例如确定余数的大小，乘积或乘幂的末位数字问题以及整除的证明问题等等.例3.10

求下列各数被7除后的余数；(1)71427X19，(2)476．解(1)因为7≡14≡0(mod7)，

71427≡6(mod7)，19≡5(mod7)，(2)∵47≡5(mod7),472≡52≡4(mod7),所以476=(472)3≡43=64≡1(mod7),即476被7除的余数为1．所以71427X19≡6X5=30≡2(mod7)，即71427X19≡7除的余数为2；

例3.11

求1350分别被5，11除所得的余数．解因为13≡3(mod5)，34≡1(mod5)，所以350=348X32≡(34)12X9≡4(mod5)．1350≡250=(25)10≡1010=(102)5≡1(mod11);因此所求的余数分别为4与1.又因为13≡2(mod11)，25≡10(mod11)，102≡1(mod11)，所以例3.12把由1开始的自然数依次写下来，直写到第201位为止，就是

12345678910111213…

试问这个数除以3的余数等于几?解因为1～9写在一起构成九位数，10～99写在一起为90X2＝180位数，所以由1开始的自然数依次写到99，合计为189位数，由于201－189=12，因此只需在1写到99后再写上100，101，102，103四个数．即从１开始的自然数依次写到103就构成一个201位数(由103个连续的自然数组成）．因为每三个连续自然数的各位数字之和能被3除，103≡1(mod3)，所以这个数除以3的余数为1．201位大数的余数问题从上面几个例题可以看到，在给定模数的条件下，对于很大的数，尤其是对于以方幂形式给出的数,利用同余的性质，可在同余的意义下使它变小，如果能在运算过程中，出现ak≡1(modm)，那么对于求an被m除的余数就很方便了．乘幂Ak

的末位数字问题对于乘幂Ak

的末位数字问题，即所谓尾数问题，根据整除定义，本质上是求Ak与那个数字对于模10同余问题．实际上，若设Ak=10b+c，这里c是乘幂Ak的个位数字，则Ak≡c(mod10)．由于乘幂Ak的个位数字c只能与底数A的个位数字a有关，所以我们根据0~9这十个数字自乘的规律来解决乘幂Ak的个位数字问题就显得比较简单．数字a(1≤a≤9)自乘后所得幂ak的末位数字变化规律，(见下页)．

从表可以看出，当a为0，1，5，6时,a的任何次幂的个位数字都是它们本身．即a=0，1，5或6时．ak的个位数字呈现周期为1的规律性;当a=2，3，7或8时，ak的个位数字出现的规律也有周期性，其周期为4。当a=4或9时，a3，a5，a7，a9，a11，a1