《初等数论 第三章 同余.docx》由会员分享，可在线阅读，更多相关《初等数论 第三章 同余.docx（14页珍藏版）》请在三一办公上搜索。
1、初等数论 第三章 同余第三章 同余 第三章 同 余 1 同余的概念及其基本性质 定义1设mZ+，称之为模。若用m去除两个整数a与b所得的余数相同，则称a,b对模m同余，记作：ab(modm)；若所得的余数不同，则称a,b对模m不同余，记作：a/b(modm)。例如，81(mod7)，；所有偶数a0(mod2)，所有奇数a1(mod2)。同余是整数之间的一种关系，它具有下列性质：1、aa(modm)；2、若ab(modm)，则ba(modm)；3、若ab(modm)，bc(modm)，则ac(modm)；故同余关系是等价关系。定理1整数a,b对模m同余的充分必要条件是m|(a-b)，即a=b+m
2、t，tZ。证明设a=mq1+r1，b=mq2+r2，0r1,r20，则akbk(modmk)；(2)若ab(modm)，d是a,b及m的任一公因数，则abm (mod)。ddd性质5若ab(modmi)，i=1,2,L,k，则ab(modm1,m2,L,mk)。反之亦然。性质6若ab(modm)，d|m，d0，则ab(modd)。 性质7若ab(modm)，则(a,m)=(b,m)，因而若d能整除a,b及m两数之一，则d必能整除a,b中的另一数。例1求3406写成十进位数时的个位数码。解事实上，只需求满足3406a(mod10)，0a9的数a。因为39-1(mod10)，所以3即个位数码是9。
3、2406(3)2203(-1)203-19(mod10)，例2证明：当n为奇数时，3|2n+1，当n为偶数时，3/|2n+1。证明因为n2-1(mod3)，所以2n+1(-1)n+1(mod3)，nn当n为奇数时，2+1(-1)+1-1+10(mod3)，故3|2+1，当n为偶数时，2n+1(-1)n+11+12(mod3)，故3/|2n+1。同余性质在算术中的一些应用。 一、检查因数的方法 1、一整数能被3整除的充分必要条件是它的十进位数码之和能被3整除。 证明 只需讨论正整数即可。任取aZ+，则a可以写成十进位的形式： - 2 - 第三章 同余 a=an10n+an-110n-1+L+a0
4、，0ai10，于是，由101(mod3)可知aan+an-1+L+a0(mod3)，从而3|a3|an+an-1+L+a0。对于9同理可证。2、设正整数a=an1000n+an-11000n-1+L+a0，0ai1000，则7|a的充分必要条件是7|(a0+a2+L)-(a1+a3+L)。 证明 因为71113=1001。 例3 a=5874192能被3和9整除。 例4 a=435693能被3整除，但不能被9整除。 例5 a=637693能被7整除；a=75312289能被13整除。 二、弃九法 例6 设a=28997，b=39495，P=ab=1145236415，检查计算是否正确。 解 令
5、 a=an10n+an-110n-1+L+a0，0ai10 b=bm10m+bm-110m-1+L+b0，0bj10 P=cl10l+cl-110l-1+L+c0，0ck0，则全体整数可分成m个集合，记作：K0,K1,L,Km-1，其中Kr=qm+r|qZ，r=0,1,L,m-1，这些集合具有下列性质：(1)每个整数必包含在而且仅在上述的一个集合中；(2)两个整数同在一个集合的充分必要条件是对模m同余。证(1)设a是任一整数，则必有于是由ra的存在性可知a=mq+ra，0rac，b=11L1，c=11L1，bc(modn)，则n|(b-c)=11L100L0=a。123123123123k个1
6、s个1k-s个1s个0例3设mZ+，(a,m)=1，bZ，x通过模m的一个完全剩余系，则xax+b1=(m-1)。m2因为x通过模m的一个完全剩余系，所以ax+b通过模m的一个完全 证01m-1ax+b剩余系，从而，通过,L,mmmm故xm-11ax+b01=(m-1)。=+L+mmmm2- 6 - 第三章 同余 3 简化剩余系与欧拉函数 定义1欧拉函数j(a)是定义在正整数集上的函数，它的值等于序列0,1,2,L,a-1中与a互质的数的个数。注若a是质数，则j(a)=a-1；若a是合数，则j(a)1，(a,m)=1，则aj(m)1(modm)。证设r1,r2,L,rj(m)是模m的简化剩余系
7、，则ar1,ar2,L,arj(m)也是模m的简化剩余系，于是(ar1)(ar2)L(arj(m)r1r2Lrj(m)(modm)，即aj(m)(r1r2Lrj(m)r1r2Lrj(m)(modm)，又(r1,m)=(r2,m)=L(rj(m),m)=1，故(r1r2Lrj(m),m)=1，从而aj(m)1(modm)。推论(Fermat定理)若p是质数，则apa(modp)。证若(a,p)=1，则由定理1可知ap-11(modp)，从而apa(modp)。 若(a,p)1，则p|a，故apa(modp)。例1设p是奇质数，证明：(1)1p-1+2p-1+L+(p-1)p-1-1(modp)；
8、(2)1p+2p+L+(p-1)p0(modp)；mmm(3)若2m/1(modp)，则1+2+L+(p-1)0(modp)。证(1)由费马定理可知ip-11(modp)，i=1,2,L,p-1，故1p-1+2p-1+L+(p-1)p-11+1+L+1p-1-1(modp)。(2)由费马定理可知ipi(modp)，i=1,2,L,p-1，p(p-1)0(modp)。2故1p+2p+L+(p-1)p1+2+L+(p-1)(3)因为1,2,L,p-1是模p的简化剩余系，所以2,4,L,2(p-1)也是模p的简化剩余系，于是1m+2m+L+(p-1)m2m+2m2m+L+2m(p-1)m2m1m+2m+L+(p-1)m(modp)，mmm又2m/1(modp)，故1+2+L+(p-1)0(modp)。- 9 - 第三章 同余 例2设p是除2与5外的任一质数，kZ+，证明：p|99L9。123k(p-1)个证因为由费马定理可知p2,5，所以(10k,p)=1，(10k)p-11(modp)，故k(p-1)个p|(10k)p-1-1=99L9。123- 10 -
