1　同余的定义及基本性质

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

定义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=q₁m+r₁，0≤r₁＜m，

b=q₂m+r₂，0≤r₂＜m，

则r₁=r₂.

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

“同余”按其词意来说，就是“余数相同”，定理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+k₁m，c=d+k₂m推出

ac=bd+（bk₂+dk₁+k₁k₂m）m，

这就证明了所要的结论.

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

性质Ⅳ设f（x）=a_nxⁿ+…+a₀，g（x）=b_nxⁿ+…+b₀是两个整系数多项式（注：本书中的多项式无特别说明都是整系数的.），满足

a_j≡b_j（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）=a_nxⁿ+…+a₀和g（x）=b_nxⁿ+…+b₀是两个整系数多项式.当满足条件（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有恒等同余式

x^p-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）知，存在x₀，y₀，使得ax₀+my₀=1.取c=x₀即满足要求.

例如：

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

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

性质Ⅸ同余式组

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

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

a≡b（mod［m₁，…，m_k］）.

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

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

例1求3⁴⁰⁶写成十进位数时的个位数.

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

3⁴⁰⁶≡a（mod10），0≤a≤9.

显然，有3²≡9≡-1（mod10），3⁴≡1（mod10），进而有

3⁴⁰⁴≡1（mod10）.

因此3⁴⁰⁶≡3⁴⁰⁴·3²≡9（mod10）.所以个位数是9.

例2求3⁴⁰⁶写成十进位数时的最后两位数.

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

3⁴⁰⁶≡b（mod100），0≤b≤99.

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

3⁴≡81≡6（mod25），3⁸≡36≡11（mod25），

3¹²≡66≡-9（mod25），3¹⁶≡-54≡-4（mod25），

3²⁰≡-24≡1（mod25）.

由此及3²⁰≡1（mod4），从性质Ⅸ推出3²⁰≡1（mod100），3⁴⁰⁰≡1（mod100）.因此3⁴⁰⁶≡3⁴⁰⁰·3⁶≡3⁶≡29（mod100）.所以，个位数为9，十位数为2.

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

由这里得到的3¹⁰≡-1（mod25）就推出3²⁰≡1（mod25）.

例3证明641|2²⁵+1.

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

2⁹≡512≡-129（mod641），2¹¹≡-516≡125（mod641），2¹³≡500≡-141（mod641），2¹⁵≡-564≡77（mod641），2¹⁸≡616≡-25（mod641），2²²≡-400≡241（mod641），2²³≡482≡-159（mod641），2²⁵≡-636≡5（mod641），2³²≡640≡-1（mod641）.

这就证明了所要结论.本题也可以通过计算2⁸，2¹⁶，2³²对模641的剩余来算，这时数目要大些.

例4证明不定方程x²+2y²=203无解.

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

（x₀y^-1₀）²≡x²₀（y^-1₀）²≡-2y²₀（y^-1₀）²≡-2（y₀y^-1₀）²≡-2（mod7）.

但n²对模7的剩余仅可能是：0，1，-3，2，不可能是-2，所以原方程无解.本题实际上是给出了一个证明不定方程无解的方法.这就是，从没有整数x，y使得x²+2y²≡0（mod7）成立，即从同余方程（见第四章）x²+2y²≡0（mod7）无解，推出不定方程x²+2y²=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）ⁿ·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）ⁿ·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|1978^m-1978ⁿ.

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

1978^m-1978ⁿ≡0（mod1000）（9）

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

2ⁿ·989ⁿ（1978^k-1）≡0（mod2³·5³）.

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

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

1978^l-1≡0（mod5）

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

1978≡3（mod5），

所以d₁=4.再求使

1978^h-1≡0（mod5²）

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

1978≡3（mod5²），

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

1978^k-1≡0（mod5³）

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

1978≡-22（mod5³），（-22）²⁰≡（25-3）²⁰≡3²⁰≡（243）⁴≡7⁴≡（50-1）²≡26（mod5³）.

通过计算得

1978²⁰≡26（mod5³），1978⁴⁰≡（25+1）²≡51（mod5³），

1978⁶⁰≡（25+1）（50+1）≡76（mod5³），1978⁸⁰≡（50+1）²≡101（mod5³），1978¹⁰⁰≡（100+1）（25+1）≡1（mod5³）.

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

n≥3，100|m-n.

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