3　带余数除法

3.1　带余数除法及其基本应用

整数集合最重要的特性是在其中可以实现下面的带余数除法（也称为带余除法或除法算法），它是初等数论的证明中最重要、最基本、最直接的工具.

定理1（带余数除法）设a，b是两个给定的整数，a≠0，那么，一定存在唯一的一对整数q与r，满足

b=qa+r，0≤r＜|a|.（1）

此外，a|b的充分必要条件是r=0.

证唯一性若还有整数q′与r′满足

b=q′a+r′，0≤r′＜|a|，（2）

不妨设r′≥r.由式（1）和（2）得：0≤r′-r＜|a|及r′-r=（q-q′）a.

若r′-r＞0，则由上式及2定理1（vi）推出|a|≤r′-r.这和r′-r＜|a|矛盾.所以，必有r′=r，进而得q′=q.

存在性当a|b时，可取q=b/a，r=0.当a｜/b时，考虑集合

T=｛b-ka，k=0，±1，±2，…｝.

容易看出，集合T中必有正整数（例如，取k=-2|b|a），所以由最小自然数原理知，T中必有一个最小正整数，设为t₀=b-k₀a＞0.我们来证明必有t₀＜|a|.因为a｜/b，所以t₀≠|a|.若t₀＞|a|，则t₁=t₀-|a|＞0，显见，t₁∈T，t₁＜t₀.这和t₀的最小性矛盾.取q=k₀，r=t₀就满足要求.

最后，显见当b=qa+r时，a|b的充分必要条件是ar.当满足0≤r＜|a|时，由2定理1（vi）就推出a|r的充分必要条件是r=0.这就证明了定理的最后一部分.证毕.

在具体应用带余数除法时，常取以下更灵活的形式：

定理2设a，b是两个给定的整数，a≠0；再设d是一给定的整数.那么，一定存在唯一的一对整数q₁与r₁，满足

b=q₁a+r₁，d≤r₁＜|a|+d.（3）

此外，a|b的充分必要条件是a|r₁.

只要对a和b-d用定理1就可推出定理2，详细论证留给读者.特别有用的是取d=-|a|/2，当2|a；d=-（|a|-1）/2，当2｜/a.这时式（3）变为b=q₁a+r₁，其中

合起来可写为

b=q₁a+r₁，-|a|/2≤r₁＜|a|/2.（3′）

适当选取d（如何选？）也可使式（3）变为以下两种形式：

b=q₁a+r₁，-|a|/2＜r₁≤|a|/2（注：当a为奇数时式（3′）和（3″）是一样的.）；（3″）

b=q₁a+r₁，1≤r₁≤|a|.（3‴）

通常把式（1）中的r称为b被a除后的最小非负余数，式（3′）和（3″）中的r₁都称为绝对最小余数，式（3）中的r₁称为最小正余数，而式（3）中的r₁统称为余数.

推论3设a＞0.（i）任一整数被a除后所得的最小非负余数是且仅是0，1，…，a-1这a个数中的一个.

（ii）相邻的a个整数被a除后，恰好取到这a个余数.特别地，一定有且仅有一个数被a整除.

这是定理1的直接推论，证明留给读者.它是常用的整数分类及进位制表示法的基础.先来讨论整数分类，这就是第三章2将讨论的同余类.

例1设a≥2是给定的正整数，j=0，1，…，a-1.对给定的j，被a除后余数等于j的全体整数是

ka+j，k=0，±1，±2，….

这些整数组成的集合记为j mod a.当0≤j≠j′≤a-1时集合j mod a和j′mod a不相交，以及并集

0mod a∪1mod a∪…∪（a-1）mod a=Z，

即全体整数按被a除后所得的最小非负余数来分类，分成了两两不相交的a个类.例如：a=2时，全体整数分为两类：

0mod2=｛2k：k∈Z｝，1mod2=｛2k+1：k∈Z｝；

a=3时全体整数分为三类：

0mod3=｛3k：k∈Z｝，1mod3=｛3k+1：k∈Z｝，

2mod3=｛3k+2：k∈Z｝；

a=6时全体整数分为六类：

0mod6=｛6k：k∈Z｝，1mod6=｛6k+1：k∈Z｝，2mod6=｛6k+2：k∈Z｝，3mod6=｛6k+3：k∈Z｝，4mod6=｛6k+4：k∈Z｝，5mod6=｛6k+5：k∈Z｝.

例2（i）0mod2∩0mod3=0mod6；（ii）1mod2∩1mod3=1mod6；（iii）0mod2∩1mod3=4mod6.

证先来证（i）.即要证a=2k且a=3h的充分必要条件是a=6d.充分性显然.由2k=3h知h=2（k-h），所以a=6（k-h）.这就证明了必要性.

（ii）就是要证：a=2k+1且a=3h+1的充分必要条件是a=6d+1，即a-1=2k且a-1=3h的充分必要条件是a-1=6d.而这正是（i）所证明的.

（iii）就是要证：a=2k且a=3h+1的充分必要条件是a=6d+4.充分性显然.由2k=3h+1知h=2（k-h）-1，所以a=6（k-h）-2=6（k-h-1）+4，这就证明了必要性.请读者解释这些等式的含意.

例31mod2=1mod6∪3mod6∪5mod6.

证n∈1mod2即n=2k+1，k∈Z.而由例1知：必有k=3h，3h+1或3h+2，h∈Z，因而必有n=6h+1，6h+3或6h+5.反过来显然成立.请读者解释等式的含意.

下面来讨论a进位制.

例4设a≥2是给定的正整数，那么任一正整数n必可唯一表示为

n=r_ka^k+r_k-1a^k-1+…+r₁a+r₀，（4）

其中整数k≥0，0≤r_j≤a-1（0≤j≤k），r_k≠0.这就是正整数的a进位表示.

证对正整数n必有唯一的k≥0，使a^k≤n＜a^k+1（为什么）.由带余数除法知，必有唯一的q₀，r₀满足

n=q₀a+r₀，0≤r₀＜a.

若k=0，则必有q₀=0，1≤r₀＜a，所以结论成立.设结论对k=m≥0成立.那么，当k=m+1时，上式中的q₀必满足

a^m≤q₀＜a^m+1.

由假设知

q₀=s_ma^m+…+s₀，

其中0≤s_j≤a-1（0≤j≤m-1），1≤s_m≤a-1，因而有

n=s_ma^m+1+…+s₀a+r₀，

即结论对m+1也成立.证毕.

现在来讨论特殊数列被某一正整数除后所得的余数的特殊性.

例5设a＞2是奇数.证明：

（i）一定存在正整数d≤a-1，使得a|2^d-1；

（ii）设d₀是满足（i）的最小正整数d，那么a|2^h-1（h∈N）的充分必要条件是d₀|h.

（iii）必有正整数d，使得（2^d-3，a）=1.

证先证（i）.考虑以下a个数：

2⁰，2¹，2²，…，2^α-1.

由2例2知，a｜/2^j（0≤j＜a）.由此及定理1可得：对每个j，0≤j＜a，

2^j=q_ja+r_j，0＜r_j＜a.

所以a个余数r₀，r₁，…，r_a-1仅可能取a-1个值.因此其中必有两个相等，设为r_i，r_k，不妨设0≤i＜k＜a，因而有

a（q_k-q_i）=2^k-2ⁱ=2ⁱ（2^k-i-1）.

利用2的例2，由此推出a2^k-i-1.取d=k-i≤a-1就满足要求.

下面来证（ii）.充分性是显然的，只要证必要性.同样由定理1得

h=qd₀+r，0≤r＜d₀，

因而有

最后来证（iii）.取d满足（i），利用2定理8（iv）我们有（2^d-3，a）=（2^d-1-2，a）=（-2，a）=1.

在例5中取a=11，我们有

2=0·11+2，2²=0·11+4，2³=0·11+8，2⁴=1·11+5，

2⁵=2·11+10，2⁶=5·11+9，2⁷=11·11+7，2⁸=23·11+3，

2⁹=46·11+6，2¹⁰=93·11+1.

因此，使11|2^d-1的最小正整数d=10，所有能使11|2^d-1的正整数d=10·k，k=1，2，….由以上计算也可以看出，2^d被11除后可能取到的最小非负余数是：1，2，3，4，5，6，7，8，9，10.

在例5中取a=15，则有

2=0·15+2，2²=0·15+4，2³=0·15+8，2⁴=1·15+1.

因此，使15|2^d-1的最小正整数d=4，所有能使15|2^d-1的d=4·k，k=1，2，3，….由以上计算知，2^d被15除后可能取到的最小非负余数是：1，2，4，8.

推论3是对全体整数被一个固定的正整数a除后所得的最小非负余数的情况来说的.在例5中已经看到，特殊的整数或特殊的整数列被一个固定的正整数a除后所得的最小非负余数会有更特殊的性质，这一点在初等数论的论证中有重要作用.例如：

（i）两个4k+3形式的数（即被4除余3的数）的乘积一定是4k+1形式的数（即被4除余1的数）；

（ii）x²被4除后所得的非负最小余数只可能是0，1；

（iii）x²被8除后所得的非负最小余数只可能是0，4（当x为偶数）及1（当x为奇数）；

（iv）x²被3除后所得的非负最小余数是0，1；

（v）x³被9除后所得的非负最小余数是0，1，8.

请读者自己验证这些结论.这样，对任意的整数x，y，从（ii）可推出：x²+y²≠4k+3；从（iii）推出：x²+y²≠8k+3，8k+6，8k+7；从（v）推出：x³+y³≠9k+3，9k+4，9k+5，9k+6（请读者自己验证）.

以上证明的结论和所举例子都是对非负最小余数来说的.对绝对最小余数，以及一般指定的余数d≤r₁＜|a|+d（d为指定的整数），都可作同样的讨论.在应用中灵活地运用这一点是很重要的.