初等数论 第三章 同余

第三章 同余

第三章 同 余

§1 同余的概念及其基本性质

定义1设m?Z?，称之为模。若用m去除两个整数a与b所得的余数相同，则称a,b对模m同余，记作：a?b(modm)；若所得的余数不同，则称a,b对模m不同余，记作：a??b(modm)。例如，8?1(mod7)，；所有偶数a?0(mod2)，所有奇数a?1(mod2)。同余是整数之间的一种关系，它具有下列性质：1、a?a(modm)；（反身性）2、若a?b(modm)，则b?a(modm)；（对称性）

3、若a?b(modm)，b?c(modm)，则a?c(modm)；（传递性）故同余关系是等价关系。定理1整数a,b对模m同余的充分必要条件是m|(a?b)，即a?b?mt，t?Z。

证明设a?mq1?r1，b?mq2?r2，0?r1,r2?m，则a?b(modm)?r1?r2?a?b?m(q1?q2)?m|(a?b)。性质1(1)若a1?b1(modm)，a2?b2(modm)，则a1?a2?b1?b2(modm)；

(2)若a?b?c(modm)，则a?c?b(modm)。性质2若a1?b1(modm)，a2?b2(modm)，则a1a2?b1b2(modm)；

特别地，若a?b(modm)，则ka?kb(modm)。定理2若A?1??k?B?1??k(modm)，xi?yi(modm)，i?1,2,?,k，则?1??k?A?1??k?k?1x1?xk??1??k?B?1??k?k?1y1?yk(modm)；特别地，若ai?bi(modm)，i?0,1,2,?,n，则anxn?an?1xn?1???a0?bnxn?bn?1xn?1???b0(modm)。性质3若a?a1d，b?b1d，(d,m)?1，a?b(modm)，则a1?b1(modm)。

- 1 -

第三章 同余

性质4(1)若a?b(modm)，k?0，则ak?bk(modmk)；(2)若a?b(modm)，d是a,b及m的任一公因数，则abm ?(mod)。ddd性质5若a?b(modmi)，i?1,2,?,k，则a?b(mod[m1,m2,?,mk])。

反之亦然。性质6若a?b(modm)，d|m，d?0，则a?b(modd)。

性质7若a?b(modm)，则(a,m)?(b,m)，因而若d能整除a,b及m两数之一，则d必能整除a,b中的另一数。例1求3406写成十进位数时的个位数码。解事实上，只需求满足3406?a(mod10)，0?a?9的数a。因为3?9??1(mod10)，所以3即个位数码是9。2406

?(3)2203?(?1)203

??1?9(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?1?0(mod3)，故3|2?1，当n为偶数时，2n?1?(?1)n?1?1?1?2(mod3)，故3?|2n?1。

同余性质在算术中的一些应用。 一、检查因数的方法

1、一整数能被3（或9）整除的充分必要条件是它的十进位数码之和能被3（或9）整除。

证明 只需讨论正整数即可。任取a?Z?，则a可以写成十进位的形式：

- 2 -

第三章 同余

a?an10n?an?110n?1???a0，0?ai?10，于是，由10?1(mod3)可知a?an?an?1???a0(mod3)，从而3|a?3|an?an?1???a0。对于9同理可证。2、设正整数a?an1000n?an?11000n?1???a0，0?ai?1000，则7（或11或13）|a的充分必要条件是7（或11或13）|(a0?a2??)?(a1?a3??)。

证明 因为7×11×13=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，检查计算是否正确。 解 令 a?an10n?an?110n?1???a0，0?ai?10

b?bm10m?bm?110m?1???b0，0?bj?10 P?cl10l?cl?110l?1???c0，0?ck?10

则 (?ai)(?bj)??ck(mod9) （*）

i?0j?0k?0nml若（*）不成立，则P≠ab，故在本题中，计算不正确。

注 (1) 若（*）不成立，则计算不正确；但否命题不成立。 (2) 利用同样的方法可以用来验证整数的加、减运算的正确性。

- 3 -

第三章 同余

§2 剩余类及完全剩余系

定理1设m?0，则全体整数可分成m个集合，记作：K0,K1,?,Km?1，其中Kr?{qm?r|q?Z}，r?0,1,?,m?1，这些集合具有下列性质：(1)每个整数必包含在而且仅在上述的一个集合中；(2)两个整数同在一个集合的充分必要条件是对模m同余。证(1)设a是任一整数，则必有于是由ra的存在性可知a?mq?ra，0?ra?m，

a?Kra，由ra的唯一性可知a只能在Kra中。(2)设整数a,b?Kr，则a?mq1?r，b?mq2?r，故a?b(modm)。反之，若a?b(modm)，则a,b必处于同一Kr中。定义1定理1中的K0,K1,?,Km?1称为模m的剩余类，一个剩余类中的任一数称为它同类数的剩余。若m个整数a0,a1,?,am?1中任何两个数都不在同一剩余类，则a0,a1,?,am?1称为模m的一个完全剩余系。 推论 m个整数作成模m的一个完全剩余系的充分必要条件是它们对模m两两不同余。

例如，下列序列都是模m的完全剩余系： (1)0,1,2,?,m?1；（最小非负完全剩余系）(2)0,m?1,?,am?a,?,(m?1)m?(m?1)；(3)0,?m?1,?,(?1)am?a,?,(?1)m?1m?(m?1)；(4)当m为偶数时，1??2??当m为奇数时，?mmm,??1,?,?1,0,1,?,?1；222mmm?1,?,?1,0,1,?,?1,；222

m?1m?1,?,?1,0,1,?,。（绝对最小完全剩余系）22- 4 -

第三章 同余

定理2设m?Z?，(a,m)?1，b?Z，若x通过模m的一个完全剩余系，则ax?b也通过模m的一个完全剩余系，即若a0,a1,?,am?1是模m的完全剩余系，则aa0?b,aa1?b,?,aam?1?b也是模m的完全剩余系。 证只需证明aa0?b,aa1?b,?,aam?1?b两两不同余即可，采用反证法。设aai?b?aaj?b(modm)(i?j)，则aai?aaj(modm)，又(a,m)?1，于是ai?aj(modm)(i?j)，与已知矛盾，故aa0?b,aa1?b,?,aam?1?b也是模m的完全剩余系。定理3设m1,m2?Z?，(m1,m2)?1，而x1,x2分别通过模m1,m2的完全剩余系，则m2x1?m1x2也通过模m1m2的完全剩余系。证因为x1,x2分别通过m1,m2个整数，所以m2x1?m1x2通过m1m2个整数，下证这m1m2个整数对模m1m2两两不同余。设m2x1'?m1x2'?m2x1''?m1x2''(modm1m2)，其中x1',x1'',x2',x2''分别是x1,x2所通过的完全剩余系中的数，则m2x1'?m2x1''(modm1)，m1x2'?m1x2''(modm2)，又(m1,m2)?1，故x1'?x1''(modm1)，x2'?x2''(modm2)，这说明m2x1?m1x2所通过的数两两不同余，因此，m2x1?m1x2也通过模m1m2的完全剩余系。例1设m?0(mod2)，a1,?,am及b1,?,bm都是模m的完全剩余系，则a1?b1,?,am?bm不是模m的完全剩余系。证：因为a1,?,am及b1,?,bm都是模m的完全剩余系，mm(m?1)mm所以?ai??i??(modm)，同理?bi?(modm)，222i?1i?1i?1mm从而?(ai?bi)??ai??bi?i?1i?1i?1mmmmm??0(modm)，22若a1?b1,?,am?bm是模m的完全剩余系，则?(ai?1mi?bi)?m(modm)，矛盾。2因此，a1?b1,?,am?bm不是模m的完全剩余系。- 5 -

第三章 同余

例2证明：对任何正整数n，存在着仅有数字1,0组成的数a，使得n|a。证：考察n?1个数：1,11,?,11?1，它们对模n至少有两个在同一同余类中， ???n?1个1设b?c，b?11?1，c?11?1，b?c(modn)，则n|(b?c)?11?100?0?a。????????????k个1s个1k?s个1s个0例3设m?Z?，(a,m)?1，b?Z，x通过模m的一个完全剩余系，则???x?ax?b?1??(m?1)。m?2因为x通过模m的一个完全剩余系，所以ax?b通过模m的一个完全

证01m?1?ax?b?剩余系，从而?，?通过,,?,mmmm??故???xm?11?ax?b?01?(m?1)。??????m?mmm2

- 6 -

第三章 同余

§3 简化剩余系与欧拉函数

定义1欧拉函数?(a)是定义在正整数集上的函数，它的值等于序列0,1,2,?,a?1中与a互质的数的个数。注若a是质数，则?(a)?a?1；若a是合数，则?(a)?a?1。定义2如果一个模m的剩余类中的数与m互质，则称它为一个与模m互质的剩余类。在与模m互质的全部剩余类中，从每一类各取一数所作成的数的集合称为模m的一个简化剩余系。

定理1模m的剩余类与模m互质的充分必要条件是此类中有一数与m互质。因此，与模m互质的剩余类的个数为?(m)，模m的每一简化剩余系是由与m互质的?(m)个对模m不同余的整数组成的。证设K0,K1,?,Km?1是模m的全部剩余类，若Kr与模m互质，则(r,m)?1；反之，若有kr?Kr，(kr,m)?1，则对于Kr中任一数kr'?qm?kr，有(kr',m)?1，即Kr与模m互质。定理2若a1,a2,?,a?(m)是?(m)个与m互质的整数，并且两两对模m不同余，则a1,a2,?,a?(m)是模m的一个简化剩余系。定理3若(a,m)?1，x通过模m的简化剩余系，则ax也通过模m的简化剩余系。证ax通过?(m)个整数，而且由(a,m)?1，(x,m)?1可知(ax,m)?1，若axi?axj(modm)(i?j)，则xi?xj(modm)(i?j)，与已知矛盾，故ax通过模m的简化剩余系。

定理4设m1,m2?Z?，(m1,m2)?1，而x1,x2分别通过模m1,m2的简化剩余系，则m2x1?m1x2也通过模m1m2的简化剩余系。- 7 -

第三章 同余

证由上一节定理3可知，若x1,x2分别通过模m1,m2的完全剩余系，则m2x1?m1x2也通过模m1m2的完全剩余系。下证当x1,x2分别通过模m1,m2的简化剩余系时，m2x1?m1x2通过模m1m2的一个完全剩余系中一切与m1m2互质的整数。一方面，由(x1,m1)?(x2,m2)?(m1,m2)?1可知(m2x1,m1)?1，(m1x2,m2)?1，于是(m2x1?m1x2,m1)?1，(m1x2?m2x1,m2)?1，从而(m2x1?m1x2,m1m2)?1，另一方面，由(m2x1?m1x2,m1m2)?1可知(m2x1?m1x2,m1)?(m1x2?m2x1,m2)?1，于是(m2x1,m1)?(m1x2,m2)?1，从而(x1,m1)?(x2,m2)?1。推论设m1,m2?Z?，(m1,m2)?1，则?(m1m2)??(m1)?(m2)。证由定理4可知，若x1,x2分别通过模m1,m2的简化剩余系，则m2x1?m1x2通过模m1m2的简化剩余系，即m2x1?m1x2通过?(m1m2)个整数。另一方面，由于x1通过?(m1)个整数，x2通过?(m2)个整数，因此，m2x1?m1x2通过?(m1)?(m2)个整数。故?(m1m2)??(m1)?(m2)。?1??1??1??k?1?2??。???定理5设a?p1p2?pk，则?(a)?a?1?1??1??????p1??p2??pk???证先证?(p?)?p??p??1。在模p?的完全剩余系1,2,?,p?中，与p?不互质的数为p,2p,?,p??1p，共有p??1个，故?(p?)?p??p??1。?k?k?k?1?1?2?1?1?1?1?2?1因此，?(a)??(p1)?(p2)??(pk)?(p1?p1)(p2?p2)?(pk?pk)?1??1??1???。????a?1?1??1??????p1??p2??pk???

- 8 -

第三章 同余

§4 欧拉定理·费马定理

定理1(Euler)设m?Z，m?1，(a,m)?1，则a?(m)?1(modm)。证设r1,r2,?,r?(m)是模m的简化剩余系，则ar1,ar2,?,ar?(m)也是模m的简化剩余系，于是(ar1)(ar2)?(ar?(m))?r1r2?r?(m)(modm)，即a?(m)(r1r2?r?(m))?r1r2?r?(m)(modm)，又(r1,m)?(r2,m)??(r?(m),m)?1，故(r1r2?r?(m),m)?1，从而a?(m)?1(modm)。推论(Fermat定理)若p是质数，则ap?a(modp)。证若(a,p)?1，则由定理1可知ap?1?1(modp)，从而ap?a(modp)。 若(a,p)?1，则p|a，故ap?a(modp)。例1设p是奇质数，证明：(1)1p?1?2p?1???(p?1)p?1??1(modp)；(2)1p?2p???(p?1)p?0(modp)；mmm(3)若2m??1(modp)，则1?2???(p?1)?0(modp)。证(1)由费马定理可知ip?1?1(modp)，i?1,2,?,p?1，故1p?1?2p?1???(p?1)p?1?1?1???1?p?1??1(modp)。(2)由费马定理可知ip?i(modp)，i?1,2,?,p?1，p(p?1)?0(modp)。2故1p?2p???(p?1)p?1?2???(p?1)?(3)因为1,2,?,p?1是模p的简化剩余系，所以2,4,?,2(p?1)也是模p的简化剩余系，于是1m?2m???(p?1)m?2m?2m2m???2m(p?1)m?2m[1m?2m???(p?1)m](modp)，mmm又2m??1(modp)，故1?2???(p?1)?0(modp)。- 9 -

第三章 同余

例2设p是除2与5外的任一质数，k?Z?，证明：p|99?9。???k(p?1)个证因为由费马定理可知p?2,5，所以(10k,p)?1，(10k)p?1?1(modp)，故k(p?1)个

p|(10k)p?1?1?99?9。???

- 10 -

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