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為指定的整數），都可作同樣的討論.在應用中靈活地運用這一點是很重要的.