初等数论(第三版)

同余概念的定义十分简单.

定义1（同余）设m≠0.若m|a-b，即a-b=km，则称m为模，a同余于b模m以及b是a对模m的剩余，记做

a≡b（mod m）；（1）

不然，则称a不同余于b模m，b不是a对模m的剩余，记做

a≢b（mod m）.

关系式（1）称为模m的同余式，或简称同余式.

由于m|a-b等价于-m|a-b，所以同余式（1）等价于

a≡b（mod（-m）），

因此，以后总假定模m≥1.在同余式（1）中，若0≤b＜m，则称b是a对模m的最小非负剩余；若1≤b≤m，则称b是a对模m的最小正剩余；若-m/2＜b≤m/2（或-m/2≤b＜m/2），则称b是a对模m的绝对最小剩余.

这样，当b=0时，式（1）就是m|a，它就可记为a≡0（mod m），所以，所有的偶数可以表为a≡0（mod2）.由于奇数a满足2|a-1，所以，所有的奇数可以表为a≡1（mod2）.对给定的b和模m，所有同余于b模m的数就是算术数列

b+km，k=0，±1，±2，….

定理1a同余于b模m的充分必要条件是a和b被m除后所得的最小非负余数相等，即若

a=q1m+r1，0≤r1＜m，

b=q2m+r2，0≤r2＜m，

则r1=r2.

证我们有a-b=（q1-q2）m+（r1-r2）.因此，m|a-b的充分必要条件是m|r1-r2.由此及0≤|r1-r2|＜m即得r1=r2.证毕.

“同余”按其词意来说，就是“余数相同”，定理1正好说明了这一点.显见，a对模m的最小非负剩余、最小正剩余、及绝对最小剩余正好分别是a被m除后所得的最小非负余数、最小正余数、及绝对最小余数（见第一章3定理2后）.同余式（1）就是一般的a被m除的带余数除法

a=km+b（2）

中的a与余数b的关系的另一种表达形式.由第一章2例4知，若式（2）成立，那么在讨论一个a的整系数多项式f被m去除的问题时，b与a是一样的，即m|f（a）⇔m|f（b），所以a可用b代替，而其中的“部分商”k不起作用.同余的概念及同余式符号（1）正是抓住了这一关键：把除法算式（2）中的k隐藏起来，保留了b，突出了a与其余数b在讨论被m整除的问题中两者起相同的作用.应用同余式的符号在讨论整除问题时，由于它具有与等式符号的类似作用，确实比应用整除符号及除法算式方便、有效，能起到旧有符号起不到的作用.这将在以后的讨论，及与第一章中的论证的比较来看出.为了学会应用这一新的概念与符号，首先要来讨论它的基本性质.

对固定的模m，同余、同余式和相等、等式有以下同样的性质：

性质Ⅰ同余是一种等价关系，即有

a≡a（mod m），

a≡b（mod m）⇔b≡a（mod m），

a≡b（mod m），b≡c（mod m）⇒a≡c（mod m）.

证由m|a-a=0，m|a-b⇔m|b-a，以及

m|a-b，m|b-c⇒m|（a-b）+（b-c）=a-c，

就推出这三个性质.

性质Ⅱ同余式可以相加，即若有

a≡b（mod m），c≡d（mod m），（3）

则a+c≡b+d（mod m）.

证由m|a-b，m|c-d⇒m|（a-b）+（c-d）=（a+c）-（b+d），就证明了所要结论.

性质Ⅲ同余式可以相乘，即若式（3）成立，则有

ac≡bd（mod m）.

证由a=b+k1m，c=d+k2m推出

ac=bd+（bk2+dk1+k1k2m）m，

这就证明了所要的结论.

由性质Ⅰ，性质Ⅱ，性质Ⅲ立即推出（证明留给读者）：

性质Ⅳ设f（x）=anxn+…+a0，g（x）=bnxn+…+b0是两个整系数多项式（注：本书中的多项式无特别说明都是整系数的.），满足

aj≡bj（mod m），0≤j≤n.（4）

那么，若a≡b（mod m），则

f（a）≡g（b）（mod m）.

特别地，对所有整数x有

f（x）≡g（x）（mod m）（注：容易证明，这和上式是等价的，且并不需要条件（4）.）.（5）

由性质Ⅳ可引进

定义2设f（x）=anxn+…+a0和g（x）=bnxn+…+b0是两个整系数多项式.当满足条件（4）时，称多项式f（x）同余于多项式g（x）模m，记做

当满足式（5）时，称多项式f（x）等价于多项式g（x）模m，式（5）称为模m的恒等同余式.

应该指出的是，式（5）成立时，并不一定有式（4）成立.例如，对所有整数x有恒等同余式

x（x-1）…（x-m+1）≡0（mod m）

成立；由第一章4例1（ii）知，当m=素数p时，对所有整数x有恒等同余式

xp-x≡0（mod p）

成立.但是，显然有

虽然，多项式模m等价并不一定模m同余，但当m是素数p，多项式次数小于p时，这两者是一样的（见第四章8推论3及9推论2，也可见习题一第25题）.

下面是涉及模的两个简单性质.

性质V设d≥1，d|m，那么，若同余式（1）成立，则

a≡b（mod d）.

证这由d|m，m|a-b⇒d|a-b即得.

性质Ⅵ设d≠0，那么同余式（1）等价于

da≡db（mod|d|m）.

证这由|d|m|da-db⇔m|a-b推出.

一般说来，在模不变的条件下，同余式两边不能相约，即由d≠0，da≡db（mod m）.不能推出必有a≡b（mod m）.例如：

6·3≡6·8（mod10），但3≢8（mod10）.

以上的性质仅是最简单的整除性质（第一章2定理1）用同余符号来表示.由进一步的整除性质可得到相应的同余式的性质，这些性质和等式性质不同.

性质Ⅶ同余式

ca≡cb（mod m）（7）

等价于

a≡b（mod m/（c，m））.

特别地，当（c，m）=1时，同余式（7）等价于

a≡b（mod m），

即同余式（7）两边可约去c.

证同余式（7）即m|c（a-b），这等价于

这就证明了所要的结论.

性质Ⅷ若m≥1，（a，m）=1，则存在c使得

ca≡1（mod m）.（8）

我们把c称为a对模m的逆，记做a-1（mod m）或a-1.

证由第一章4定理8（k=2）知，存在x0，y0，使得ax0+my0=1.取c=x0即满足要求.

例如：

显见，a对模m的逆c不是唯一的.当c是a对模m的逆时，任一c′≡c（mod m）也一定是a对模m的逆.由性质Ⅶ知，a对模m的任意两个逆c1，c2必有c1≡c2（mod m）.以后我们写a-1（mod m）或a-1时是指任一取定的满足式（8）的c.此外，显见

（a-1，m）=1及（a-1）-1≡a（mod m）.

性质Ⅸ同余式组

a≡b（mod mj），j=1，2，…，k，

同时成立的充分必要条件是

a≡b（mod［m1，…，mk］）.

证由第一章4定理1知，mj|a-b（j=1，…，k）同时成立的充分必要条件是［m1，…，mk］|a-b.这就是要证的结论.

由于同余式有以上这些性质，特别是有类似于等式的性质使得我们在讨论整除问题时，利用同余符号及其性质要比利用整除符号方便得多，在不整除的情形还可求出其余数.下面来举几个例子.请读者指出，以下解题的每一步用到了什么性质.为了解法尽可能地简单，利用这些性质是需要技巧的.读者应该用不同的方法与技巧来解题，通过比较，可深入理解和熟练掌握同余概念及其性质.

例1求3406写成十进位数时的个位数.

解按题意是要求3406被10除后的最小非负余数a，即a满足

3406≡a（mod10），0≤a≤9.

显然，有32≡9≡-1（mod10），34≡1（mod10），进而有

3404≡1（mod10）.

因此3406≡3404·32≡9（mod10）.所以个位数是9.

例2求3406写成十进位数时的最后两位数.

解这就是要求出3406被100除后的最小非负余数b，即b满足

3406≡b（mod100），0≤b≤99.

注意到100=4·25，（4，25）=1.显然有32≡1（mod4），34≡1（mod5）.注意到4是最小的方次，由第一章4例5知，使3d≡1（mod25）成立的d，必有4|d.因此计算：

34≡81≡6（mod25），38≡36≡11（mod25），

312≡66≡-9（mod25），316≡-54≡-4（mod25），

320≡-24≡1（mod25）.

由此及320≡1（mod4），从性质Ⅸ推出320≡1（mod100），3400≡1（mod100）.因此3406≡3400·36≡36≡29（mod100）.所以，个位数为9，十位数为2.

如果不利用性质4|d，就要逐个计算3j对模25的剩余bj（为便于计算bj应取绝对最小剩余），具体做法如下表：

由这里得到的310≡-1（mod25）就推出320≡1（mod25）.

例3证明641|225+1.

证由于数目很大要直接用除法做是很繁的.利用同余式就是要证232≡-1（mod641）.641是素数，由逐步计算得

29≡512≡-129（mod641），211≡-516≡125（mod641），213≡500≡-141（mod641），215≡-564≡77（mod641），218≡616≡-25（mod641），222≡-400≡241（mod641），223≡482≡-159（mod641），225≡-636≡5（mod641），232≡640≡-1（mod641）.

这就证明了所要结论.本题也可以通过计算28，216，232对模641的剩余来算，这时数目要大些.

例4证明不定方程x2+2y2=203无解.

证用反证法.由203=7·29知，若有解x0，y0，则有（x0y0，203）=1（为什么）.显见有x20≡-2y20（mod7）.由于（y0，7）=1，由性质Ⅷ知y0对模7有逆y-10.在同余式两边乘（y-10）2得

（x0y-10）2≡x20（y-10）2≡-2y20（y-10）2≡-2（y0y-10）2≡-2（mod7）.

但n2对模7的剩余仅可能是：0，1，-3，2，不可能是-2，所以原方程无解.本题实际上是给出了一个证明不定方程无解的方法.这就是，从没有整数x，y使得x2+2y2≡0（mod7）成立，即从同余方程（见第四章）x2+2y2≡0（mod7）无解，推出不定方程x2+2y2=203无解，这里7是203的一个除数.这个方法是十分有用的.

例5设n≥1，b的素因数都大于n.证明：对任意正整数a必有

n！|a（a+b）（a+2b）…（a+（n-1）b）.

证由条件知（b，n！）=1.由性质Ⅷ知，b对模n！有逆b-1.我们有

（b-1）n·a（a+b）…（a+（n-1）b）≡ab-1（ab-1+bb-1）…（ab-1+（n-1）bb-1）≡ab-1（ab-1+1）…（ab-1+（n-1））（mod n！）.

上式右端是n个相邻整数乘积，因此，由第一章7推论4得到

（b-1）n·a（a+b）…（a+（n-1）b≡0（mod n！）.

由于（b-1，n！）=1，由此从性质Ⅵ就推出

a（a+b）…（a+（n-1）b）≡0（mod n！）.

这就证明了所要的结论.当然，本题可不用同余符号来证，读者可这样做一下，通过比较可发现，用同余符号做较为简洁且思路清晰.

例6设m＞n≥1.求最小的m+n，使得

1000|1978m-1978n.

解利用同余符号，本问题就是要求最小的m+n，使得

1978m-1978n≡0（mod1000）（9）

成立.先来讨论使上式成立的m，n要满足什么条件.记k=m-n.式（9）就变为

2n·989n（1978k-1）≡0（mod23·53）.

由性质Ⅶ，性质Ⅸ知，它等价于

由（10）知n≥3.下面来求使（11）成立的k.先求使

1978l-1≡0（mod5）

成立的最小的l，记做d1.由于

1978≡3（mod5），

所以d1=4.再求使

1978h-1≡0（mod52）

成立的最小的h，记做d2.由第一章4例5知4|d2，注意到

1978≡3（mod52），

由例2的计算知，d2=20.最后求使

1978k-1≡0（mod53）

成立的最小的k，记做d3.由第一章4例5知20|d3.注意到

1978≡-22（mod53），（-22）20≡（25-3）20≡320≡（243）4≡74≡（50-1）2≡26（mod53）.

通过计算得

197820≡26（mod53），197840≡（25+1）2≡51（mod53），

197860≡（25+1）（50+1）≡76（mod53），197880≡（50+1）2≡101（mod53），1978100≡（100+1）（25+1）≡1（mod53）.

因此，d3=100.所以由第一章4例5知必有100|k，最小的k=100.由此推出为使式（10）和（11），即式（9）成立的充分必要条件是

n≥3，100|m-n.

所以，最小的m+n=（m-n）+2n=106.如果不用同余概念及其性质来解本题，将是很繁的.